Quale contenitore STL dovrei usare per un FIFO?

Question

Quale contenitore STL si adatta meglio alle mie esigenze? Fondamentalmente ho un contenitore di 10 elementi in cui continuo a push_back nuovi elementi mentre pop_front l'elemento più vecchio (circa un milione di volte).

Attualmente sto usando un std::deque per il compito, ma chiedevo se un std::list sarebbe più efficiente, in quanto non avrei bisogno di ridistribuire in sé (o forse sto confondendo un std::deque per un std::vector?). O c'è un contenitore ancora più efficiente per il mio bisogno?

P.S. Non ho bisogno di accesso casuale

Answer 1

Dato che ci sono una miriade di risposte, potrebbe essere confuso, ma per riassumere:

Utilizzare un std::queue. La ragione di ciò è semplice: è una struttura FIFO. Vuoi FIFO, usi un std::queue.

Rende chiaro il tuo intento a chiunque altro e persino a te stesso. A std::list o std::deque no. Un elenco può essere inserito e rimosso ovunque, che non è quello che una struttura FIFO suppone di fare, e un deque può aggiungere e rimuovere da entrambe le estremità, che è anche qualcosa che una struttura FIFO non può fare.

Ecco perché è necessario utilizzare uno queue.

Ora, hai chiesto informazioni sulle prestazioni. In primo luogo, ricorda sempre questa importante regola empirica: Prima il codice buono, la prestazione è durata.

La ragione di questo è semplice: le persone che cercano prestazioni prima della pulizia e dell'eleganza finiscono quasi sempre per ultimi. Il loro codice diventa una briciola di follia, perché hanno abbandonato tutto ciò che è buono per non ricavarne nulla.

Scrivendo per la prima volta un codice buono e leggibile, molti dei problemi di prestazioni si risolveranno da soli. E se in seguito trovi che le tue prestazioni mancano, ora è facile aggiungere un profiler al tuo codice bello e pulito e scoprire dove si trova il problema.

Detto questo, std::queue è solo un adattatore. Fornisce l'interfaccia sicura, ma utilizza un contenitore diverso all'interno. È possibile scegliere questo contenitore sottostante e ciò consente una buona dose di flessibilità.

Quindi, quale contenitore sottostante dovresti usare? Sappiamo che std::list e std::deque forniscono entrambe le funzioni necessarie (push_back(), pop_front() e front()), quindi come decidiamo?

Prima di tutto, capire che allocare (e deallocare) la memoria non è una cosa rapida da fare, in generale, perché implica andare al sistema operativo e chiedergli di fare qualcosa. Uno list deve allocare memoria ogni volta che viene aggiunto qualcosa e rilasciarlo quando va via.

A deque, d'altra parte, alloca in blocchi. Assegnerà meno spesso di uno list. Consideralo come una lista, ma ogni blocco di memoria può contenere più nodi. (Naturalmente, ti suggerisco di fare really learn how it works.)

Quindi, con questo solo un deque dovrebbe funzionare meglio, perché non si occupa della memoria come spesso. In combinazione con il fatto che si gestiscono dati di dimensioni costanti, probabilmente non sarà necessario allocare dopo il primo passaggio attraverso i dati, mentre un elenco verrà costantemente assegnato e deallocato.

Una seconda cosa da capire è cache performance. Uscire in RAM è lento, quindi quando la CPU ha davvero bisogno, fa il meglio di questo tempo rimettendo un pezzo di memoria con esso, nella cache. Poiché un deque alloca in blocchi di memoria, è probabile che l'accesso a un elemento in questo contenitore causi il ritorno del resto del contenitore anche alla CPU. Ora qualsiasi ulteriore accesso a deque sarà veloce, perché i dati sono nella cache.

Questo è diverso da un elenco, in cui i dati vengono allocati uno alla volta. Ciò significa che i dati potrebbero essere distribuiti in tutta la posizione in memoria e le prestazioni della cache saranno negative.

Quindi, considerando che, uno deque dovrebbe essere una scelta migliore. Questo è il motivo per cui è il contenitore predefinito quando si utilizza un queue. Detto questo, questa è solo un'ipotesi (molto) istruita: dovrai profilare questo codice, usando uno deque in un test e lo list nell'altro per davvero sapere con certezza.

Ma ricorda: ottenere il codice funzionando con un'interfaccia pulita, quindi preoccuparsi delle prestazioni.

John solleva la preoccupazione che il wrapping di un list o causerà una riduzione delle prestazioni. Ancora una volta, lui o io non possiamo dirlo con certezza, senza profilare noi stessi, ma è probabile che il compilatore inline le chiamate effettuate da queue. Cioè, quando dici queue.push(), in realtà dirà semplicemente queue.container.push_back(), saltando completamente la chiamata di funzione.

Ancora una volta, questa è solo un'ipotesi plausibile, ma l'utilizzo di un queue non ridurrà le prestazioni, se confrontato con l'utilizzo del contenitore sottostante non elaborato. Come ho detto prima, usa lo queue, perché è pulito, facile da usare e sicuro, e se diventa davvero un problema profilo e test.

Answer 2

A queue è probabilmente un'interfaccia più semplice di un deque ma per un elenco così piccolo, la differenza di prestazioni è probabilmente trascurabile.

Lo stesso vale per list. Dipende solo dalla scelta dell'API che desideri.

Answer 3

Controlla std :: queue. Include un tipo di contenitore sottostante e il contenitore predefinito è std :: deque.

Answer 4

Perché non std::queue? Tutto ciò che ha è push_back e pop_front.

Answer 5

I continuamente push_back nuovi elementi mentre pop_front ing l'elemento più antico (circa un milione di tempo).

Un milione non è un gran numero nel settore dell'informatica. Come altri hanno suggerito, utilizzare std::queue come prima soluzione. Nel caso improbabile che sia troppo lento, identificare il collo di bottiglia usando un profiler (non indovinare!) E ri-implementare usando un contenitore diverso con la stessa interfaccia.

Answer 6

Quando le prestazioni sono davvero importanti, controlla lo Boost circular buffer library.