[C++] Implementare un buffer circolare con librerie std

[Ikon O'Cluster]

Devo implementare un buffer circolare. In pratica ho una certa struttura (struct composta da un intero e 2 vector, che quindi può essere anche abbastanza pesante) e devo creare un archivio storico. In sostanza la struttura contiene un campione di una certa informazione che è relativo ad un certo utente. Io per ogni utente (supponiamo N) devo memorizzare gli ultimi (supponiamo K) campioni. Quando memorizzo un nuovo campione lo metto in testa, ma al (K+1)-esimo quello in coda va estratto. Si noti che la dimensione di questo buffer sarà massimo K. Quindi avrò N buffer circolari di K elementi di tipo struct. Quindi usando librerie standard, avrò un std::vector di N elementi che saranno di che tipo??? Non ho una visione complessiva della libreria std del c++, qualcuno ha alternative o consigli a riguardo??? Grazie.

P.S.: L'efficienza negli inserimenti/rimozioni è fondamentale, questa operazione va fatta periodicamente da un simulatore e la frequenza (in tempo simulato) è nell'ordine del millisecondo. Quindi se considerate una simulazione brevissima come può essere 10 secondi (secondi simulati) verranno eseguiti circa 20000 tra inserimenti e rimozioni!!!

P.P.S: L'accesso in lettura x l'elaborazione dei campioni avverrà o in modo sequenziale, scorrendo l'intero buffer, oppure avverrà accedendo solo a quello più recentemente inserito (testa del buffer), questo è da vedere...

[Ikon O'Cluster]

Mi stavo soffermando con l'attenzione sulle std::list e sulle std::deque... dice che hanno complessità costante negli inserimenti/rimozioni... ma qual è la differenza??? Ad entrambe si può accedere sia in coda che in testa!

P.S.: Mi pare però di capire che mantenendo K la dimensione fissa degli elementi contenuti è meglio vector rispetto a deque...

[cionci]

Cerchi le prestazioni ? La dimensione del buffer è costante durante tutta l'esistenza ? L'accesso deve avvenire da più thread ?

[Ikon O'Cluster]

Unico thread, dimensione configurabile ma invariabile, le prestazioni sono fondamentali. In particolare:

1) Accesso casuale sugli utenti
2) Accesso sequenziale sui campioni

Come hai visto nell'altro post, per ora avevo optato per un vector di list!

[cionci]

Io credo che la soluzione più performante sia comunque quella custom, almeno per implementare la coda circolare. Forse è anche la soluzione più semplice da implementare.
Poi magari usi un vector per contenere le varie code.

[cionci]

C'è anche questa volendo: http://www.cplusplus.com/reference/stl/queue/

[Ikon O'Cluster]

Hai ragione... queue non list! :D Cmq mi hanno detto di non fare roba da me ma usare il più possibile le STL! Brutti malfidati...

[Ikon O'Cluster]

Cmq... grazie per le dritte :D Ti stai guadagnando una citazione nei ringraziamenti della tesi :read:

[cionci]

Comunque anche con queue servono o list o deque ;) Io andrei su deque, poi per cambiare ci vuole poco.

[Ikon O'Cluster]

No cionci.... ho fatto un vector di queue! Torna perfettamente... In pratica la queue la gestisco in modo che al push del K+1 esimo elemento faccia una pop e poi di di questa roba qua ne faccio un vettore di N elementi. Se vai nell'altro post in pratica hai che SamplesBase è proprio una classe che implementa la queue a dimensione limitata e cioè un buffer circolare! Poi la specializzo in base agli usi, perchè a metterci dentro campioni si fa sempre uguale. Ma a prelevarli ci sono varie possibilità x questo l'ho fatta classe astratta.

[cionci]

queues are implemented as containers adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access it elements. Elements are pushed into the "back" of the specific container and popped from its "front" ;)
In pratica se la costruisci in questo modo prende un contenitore non specializzato (non so quale sinceramente).
Quindi sarebbe meglio inizializzarla o con una deque o con una list.

[Ikon O'Cluster]

Uhm... non c'ho capito una ceppa :D

[cionci]

Ok, niente, mi sono riguardato lo Stroustrup e queue usa deque come container di default.