La liste est-elle meilleure que le vecteur lorsque nous devons stocker «les n derniers éléments»?

Il y a beaucoup de questions qui suggèrent que l’on devrait toujours utiliser un vecteur, mais il me semble qu’une liste serait meilleure pour le scénario, où nous devons stocker “les n derniers éléments”

Par exemple, disons que nous avons besoin de stocker les 5 derniers éléments vus: Itération 0:

3,24,51,62,37, 

Ensuite, à chaque itération, l’élément à l’index 0 est supprimé et le nouvel élément est ajouté à la fin:

Itération 1:

 24,51,62,37,8 

Itération 2:

 51,62,37,8,12 

Il semble que pour ce cas, pour un vecteur la complexité soit O (n), puisque nous devrions copier n éléments, mais dans une liste, il devrait s’agir de O (1), puisque nous ne faisons que couper le tête, et en ajoutant à la queue chaque itération.

Est-ce que ma compréhension est correcte? Est-ce le comportement réel d’une liste std ::?

Ni. Votre collection a une taille fixe et std::array est suffisant.

La structure de données que vous implémentez est appelée un tampon en anneau. Pour l’implémenter, créez un tableau et suivez le décalage du premier élément en cours.

Lorsque vous ajoutez un élément qui pousserait un élément hors du tampon – c’est-à-dire lorsque vous supprimez le premier élément – vous incrémentez le décalage.

Pour récupérer des éléments dans le tampon, vous ajoutez l’index et le décalage et prenez le modulo de cette valeur et la longueur du tampon.

std :: deque est une bien meilleure option. Ou si vous avez évalué std :: deque et que vous avez constaté que ses performances n’étaient pas adaptées à votre utilisation spécifique, vous pourriez implémenter un tampon circulaire dans un tableau de taille fixe, en stockant l’index du début du tampon. Lorsque vous remplacez un élément dans le tampon, vous écrasez l’élément à l’index de démarrage, puis définissez l’index de démarrage sur sa valeur précédente plus un modulo de la taille du tampon.

La traversée de liste est très lente, car les éléments de liste peuvent être dispersés dans la mémoire et le décalage vectoriel est en fait étonnamment rapide, car les déplacements de mémoire sur un seul bloc de mémoire sont assez rapides, même s’il s’agit d’un gros bloc.

La conférence Taming The Performance Beast de la conférence Meeting C ++ 2015 pourrait vous intéresser.

Si vous pouvez utiliser Boost, essayez boost :: circular_buffer :

Amélioration du tampon circulaire

C’est une sorte de séquence similaire à std::list ou std::deque . Il prend en charge les iterators à access aléatoire, les opérations d’insertion et d’effacement à temps constant au début ou à la fin du tampon et l’interopérabilité avec les algorithmes std.

Il fournit une capacité de stockage fixe: lorsque le tampon est rempli, de nouvelles données sont écrites au début du tampon et remplacent l’ancien

 // Create a circular buffer with a capacity for 5 integers. boost::circular_buffer cb(5); // Insert elements into the buffer. cb.push_back(3); cb.push_back(24); cb.push_back(51); cb.push_back(62); cb.push_back(37); int a = cb[0]; // a == 3 int b = cb[1]; // b == 24 int c = cb[2]; // c == 51 // The buffer is full now, so pushing subsequent // elements will overwrite the front-most elements. cb.push_back(8); // overwrite 3 with 8 cb.push_back(12); // overwrite 24 with 12 // The buffer now contains 51, 62, 37, 8, 12. // Elements can be popped from either the front or the back. cb.pop_back(); // 12 is removed cb.pop_front(); // 51 is removed 

Le circular_buffer stocke ses éléments dans une région contiguë de la mémoire, ce qui permet ensuite une insertion, un retrait et un access aléatoire à temps constant et rapide des éléments.


PS … ou mettre en œuvre le tampon circulaire directement comme suggéré par Taemyr .

Overload Journal # 50 – Août 2002 présente une belle introduction (par Pete Goodliffe) à l’écriture de tampons circulaires de type STL robustes.

Le problème est que O (n) ne parle que du comportement asymptotique lorsque n tend vers l’infini. Si n est petit, les facteurs constants impliqués deviennent significatifs. Le résultat est que pour les “5 derniers éléments entiers”, je serais stupéfait si le vecteur n’a pas dépassé la liste. Je m’attendrais même à ce que std::vector batte std::deque .

Pour les “derniers 500 éléments entiers”, je m’attendrais toujours à ce que std::vector soit plus rapide que std::list – mais std::deque gagnerait probablement maintenant. Pour les “derniers 5 millions d’éléments à copier lentement”, std:vector serait le plus lent de tous.

Un tampon en anneau basé sur std::array ou std::vector serait probablement encore plus rapide.

Comme (presque) toujours avec des problèmes de performance:

  • encapsuler avec une interface fixe
  • écrire le code le plus simple pouvant implémenter cette interface
  • Si le profilage montre que vous avez un problème, optimisez (ce qui complique le code).

En pratique, utiliser un std::deque ou un tampon en anneau pré-construit, si vous en avez un, sera suffisant. (Mais cela ne vaut pas la peine d’écrire un tampon circulaire, à moins que le profilage indique que vous devez le faire.)

Voici un tampon circulaire minimal. Je le poste principalement ici pour obtenir une tonne de commentaires et d’idées d’amélioration.

Mise en œuvre minimale

 #include  template class CircularBuffer { public: using iterator = typename Container::iterator; using value_type = typename Container::value_type; private: Container _container; iterator _pos; public: CircularBuffer() : _pos(std::begin(_container)) {} public: value_type& operator*() const { return *_pos; } CircularBuffer& operator++() { ++_pos ; if (_pos == std::end(_container)) _pos = std::begin(_container); return *this; } CircularBuffer& operator--() { if (_pos == std::begin(_container)) _pos = std::end(_container); --_pos; return *this; } }; 

Usage

 #include  #include  int main() { CircularBuffer> buf; *buf = 1; ++buf; *buf = 2; ++buf; *buf = 3; ++buf; *buf = 4; ++buf; *buf = 5; ++buf; std::cout << *buf << " "; ++buf; std::cout << *buf << " "; ++buf; std::cout << *buf << " "; ++buf; std::cout << *buf << " "; ++buf; std::cout << *buf << " "; ++buf; std::cout << *buf << " "; ++buf; std::cout << *buf << " "; ++buf; std::cout << *buf << " "; --buf; std::cout << *buf << " "; --buf; std::cout << *buf << " "; --buf; std::cout << *buf << " "; --buf; std::cout << *buf << " "; --buf; std::cout << *buf << " "; --buf; std::cout << std::endl; } 

Comstackr avec

 g++ -std=c++17 -O2 -Wall -Wextra -pedantic -Werror 

Démo

Sur Coliru: essayez-le en ligne

Si vous avez besoin de stocker les derniers N éléments, vous faites logiquement une sorte de queue ou un tampon circulaire, std :: stack et std :: deque sont des implémentations des files d’attente LIFO et FIFO .

Vous pouvez utiliser boost :: circular_buffer ou implémenter manuellement un buffer circulaire simple:

 template class cbuffer { public: cbuffer() : sz(0), p(0){} void push_back(int n) { buf[p++] = n; if (sz < Capcity) sz++; if (p >= Capcity) p = 0; } int size() const { return sz; } int operator[](int n) const { assert(n < sz); n = p - sz + n; if (n < 0) n += Capcity; return buf[n]; } int buf[Capcity]; int sz, p; }; 

Exemple d'utilisation d'un tampon circulaire de 5 éléments int:

 int main() { cbuffer<5> buf; // insert random 100 numbers for (int i = 0; i < 100; ++i) buf.push_back(rand()); // output to cout contents of the circular buffer for (int i = 0; i < buf.size(); ++i) cout << buf[i] << ' '; } 

N'oubliez pas que lorsque vous ne disposez que de 5 éléments, la meilleure solution est celle qui est rapide à mettre en œuvre et fonctionne correctement.

Oui. La complexité temporelle du std :: vector pour supprimer des éléments de la fin est linéaire. std :: deque peut être un bon choix pour ce que vous faites, car il offre une insertion et un retrait du temps constant au début, à la fin de la liste et également de meilleures performances que std :: list

La source:

http://www.sgi.com/tech/stl/Vector.html

http://www.sgi.com/tech/stl/Deque.html

Voici les débuts d’une classe de modèle de déstockage basée sur un tampon en anneau que j’ai écrite il y a quelque temps, principalement pour expérimenter l’utilisation de std::allocator (elle n’exige donc pas que T soit construit par défaut). Notez qu’il n’a actuellement pas d’iterators, ni d’ insert / remove , copier / déplacer des constructeurs, etc.

 #ifndef RING_DEQUEUE_H #define RING_DEQUEUE_H #include  #include  #include  template  class ring_dequeue { private: static_assert(N <= std::numeric_limits::max() / 2 && N <= std::numeric_limits::max() / sizeof(T), "size of ring_dequeue is too large"); using alloc_traits = std::allocator_traits>; public: using value_type = T; using reference = T&; using const_reference = const T&; using difference_type = ssize_t; using size_type = size_t; ring_dequeue() = default; // Disable copy and move constructors for now - if iterators are // implemented later, then those could be delegated to the InputIterator // constructor below (using the std::move_iterator adaptor for the move // constructor case). ring_dequeue(const ring_dequeue&) = delete; ring_dequeue(ring_dequeue&&) = delete; ring_dequeue& operator=(const ring_dequeue&) = delete; ring_dequeue& operator=(ring_dequeue&&) = delete; template  ring_dequeue(InputIterator begin, InputIterator end) { while (m_tailIndex < N && begin != end) { alloc_traits::construct(m_alloc, reinterpret_cast(m_buf) + m_tailIndex, *begin); ++m_tailIndex; ++begin; } if (begin != end) throw std::logic_error("Input range too long"); } ring_dequeue(std::initializer_list il) : ring_dequeue(il.begin(), il.end()) { } ~ring_dequeue() noexcept(std::is_nothrow_destructible::value) { while (m_headIndex < m_tailIndex) { alloc_traits::destroy(m_alloc, elemPtr(m_headIndex)); m_headIndex++; } } size_t size() const { return m_tailIndex - m_headIndex; } size_t max_size() const { return N; } bool empty() const { return m_headIndex == m_tailIndex; } bool full() const { return m_headIndex + N == m_tailIndex; } template  void emplace_front(Args&&... args) { if (full()) throw std::logic_error("ring_dequeue full"); bool wasAtZero = (m_headIndex == 0); auto newHeadIndex = wasAtZero ? (N - 1) : (m_headIndex - 1); alloc_traits::construct(m_alloc, elemPtr(newHeadIndex), std::forward(args)...); m_headIndex = newHeadIndex; if (wasAtZero) m_tailIndex += N; } void push_front(const T& x) { emplace_front(x); } void push_front(T&& x) { emplace_front(std::move(x)); } template  void emplace_back(Args&&... args) { if (full()) throw std::logic_error("ring_dequeue full"); alloc_traits::construct(m_alloc, elemPtr(m_tailIndex), std::forward(args)...); ++m_tailIndex; } void push_back(const T& x) { emplace_back(x); } void push_back(T&& x) { emplace_back(std::move(x)); } T& front() { if (empty()) throw std::logic_error("ring_dequeue empty"); return *elemPtr(m_headIndex); } const T& front() const { if (empty()) throw std::logic_error("ring_dequeue empty"); return *elemPtr(m_headIndex); } void remove_front() { if (empty()) throw std::logic_error("ring_dequeue empty"); alloc_traits::destroy(m_alloc, elemPtr(m_headIndex)); ++m_headIndex; if (m_headIndex == N) { m_headIndex = 0; m_tailIndex -= N; } } T pop_front() { T result = std::move(front()); remove_front(); return result; } T& back() { if (empty()) throw std::logic_error("ring_dequeue empty"); return *elemPtr(m_tailIndex - 1); } const T& back() const { if (empty()) throw std::logic_error("ring_dequeue empty"); return *elemPtr(m_tailIndex - 1); } void remove_back() { if (empty()) throw std::logic_error("ring_dequeue empty"); alloc_traits::destroy(m_alloc, elemPtr(m_tailIndex - 1)); --m_tailIndex; } T pop_back() { T result = std::move(back()); remove_back(); return result; } private: alignas(T) char m_buf[N * sizeof(T)]; size_t m_headIndex = 0; size_t m_tailIndex = 0; std::allocator m_alloc; const T* elemPtr(size_t index) const { if (index >= N) index -= N; return reinterpret_cast(m_buf) + index; } T* elemPtr(size_t index) { if (index >= N) index -= N; return reinterpret_cast(m_buf) + index; } }; #endif 

Dites brièvement que std::vector est préférable pour une taille de mémoire sans changement. Dans votre cas, si vous déplacez toutes les données vers l’avant ou ajoutez de nouvelles données dans un vecteur, cela doit être un gaspillage. std::deque est une bonne option, puisque vous pop_head et push_back par exemple. liste à deux voies.

de la référence cplus cplus sur la liste

Par rapport aux autres conteneurs de séquence standard de base (array, vector et deque), les listes sont généralement plus performantes pour insérer, extraire et déplacer des éléments dans n’importe quelle position du conteneur pour laquelle un iterator a déjà été obtenu. de ceux-ci, comme les algorithmes de sorting.

Le principal inconvénient des listes et des forward_lists par rapport à ces autres conteneurs de séquence est qu’ils n’ont pas d’access direct aux éléments par leur position; Par exemple, pour accéder au sixième élément d’une liste, il faut parcourir une position connue (comme le début ou la fin) vers cette position, ce qui prend un temps linéaire dans la distance entre ceux-ci. Ils consumnt également de la mémoire supplémentaire pour conserver les informations de liaison associées à chaque élément (ce qui peut être un facteur important pour les grandes listes d’éléments de petite taille).

à propos de deque

Pour les opérations qui impliquent des insertions ou des retraits fréquents d’éléments à des positions autres que le début ou la fin, les deques sont moins performants et ont des iterators et des références moins cohérents que les listes et les listes directes.

vetor

Par conséquent, par rapport aux baies, les vecteurs consumnt plus de mémoire en échange de la capacité de gérer le stockage et de croître de manière dynamic et efficace.

Par rapport aux autres conteneurs de séquences dynamics (deques, lists et forward_lists), les vecteurs accèdent très efficacement à ses éléments (tout comme les tableaux) et ajoutent ou suppriment relativement efficacement des éléments de sa fin. Pour les opérations qui impliquent l’insertion ou la suppression d’éléments à des positions autres que la fin, elles fonctionnent moins bien que les autres et ont des iterators et des références moins cohérents que les listes et les forward_lists.

Je pense que même utiliser std :: deque, il a également la surcharge des éléments de copie dans certaines conditions, car std :: deque est essentiellement une carte de tableaux, donc std :: list est une bonne idée pour éliminer la surcharge de copie.

Pour augmenter les performances de traverse pour std :: list, vous pouvez implémenter un pool de mémoire afin que std :: list alloue de la mémoire à partir d’un tronc et de sa localisation spatiale pour la mise en cache.