[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! 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 Ti stai guadagnando una citazione nei ringraziamenti della tesi

[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

[cionci]

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