当我们需要存储“最后的n个项目”时，列表是否比向量好？
有很多问题表明，应该总是使用一个向量，但是在我看来，一个列表对于这个场景来说会更好，我们需要存储“最后n个项目”
例如，假设我们需要存储最后看到的5个条目：迭代0：
3,24,51,62,37, 然后在每次迭代中，索引0处的项目被移除，并且在最后添加新项目：
迭代1：
24,51,62,37,8
迭代2：
51,62,37,8,12
似乎对于这个用例来说，对于一个向量，复杂度将是O（n），因为我们将不得不拷贝n个项目，但是在一个列表中，它应该是O（1），因为我们总是斩断头，并添加到尾巴每次迭代。
我的理解是正确的吗？ 这是一个std :: list的实际行为？
都不是。 你的集合有一个固定的大小，而std::array就足够了。
您实现的数据结构称为环形缓冲区。 为了实现它，你创build一个数组并且跟踪当前第一个元素的偏移量。
当你添加一个元素，将一个项目从缓冲区中移出 – 也就是当你删除第一个元素时，你增加了偏移量。
要获取缓冲区中的元素，请添加索引和偏移量，并取模和缓冲区的长度。
std :: deque是一个更好的select。 或者，如果您已经对std :: deque进行了基准testing，并发现其性能不足以满足您的特定用途，则可以在固定大小的数组中实现循环缓冲区，存储缓冲区起始索引。 当replace缓冲区中的元素时，将覆盖开始索引处的元素，然后将开始索引设置为之前的值加上一个以缓冲区大小为模的值。
列表遍历是非常缓慢的，因为列表元素可以散布在整个内存中，并且向量移位实际上是惊人的快，因为即使是大块，内存在单块内存上移动也是非常快的。
来自Meeting C ++ 2015会议的演讲Beast可能会让你感兴趣。
如果你可以使用boost，请尝试boost :: circular_buffer ：
这是一种类似于std::list或std::deque的序列。 它支持随机访问迭代器，在缓冲区的开始或结束处进行恒定时间的插入和擦除操作，以及与stdalgorithm的互操作性。
它提供了固定容量的存储：当缓冲区被填满时，新的数据从缓冲区开始写入并覆盖旧的数据
// Create a circular buffer with a capacity for 5 integers. boost::circular_buffer<int> 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
circular_buffer将它的元素存储在一个连续的内存区域中，从而实现对元素的快速定时插入，删除和随机访问。
PS …或按照Taemyr的build议直接执行循环缓冲区 。
超载日志＃50 – 2002年8月有一个很好的介绍 （由皮特Goodliffe）编写健壮的类STL循环缓冲区。
问题是O（n）只会谈论渐近行为，因为n趋于无穷大。 如果n小，那么所涉及的常数因子变得显着。 结果是，对于“最后5个整数项目”，如果向量没有击败列表，我会被震惊。 我甚至会期望std::vector击败std::deque 。
对于“最后500个整数项目”，我仍然认为std::vector比std::list更快 – 但std::deque现在可能会赢。 对于“最后500万个慢速复制项目”， std:vector将是最慢的。
基于std::array或std::vector的环形缓冲区可能会更快。
（几乎）总会遇到性能问题：
- 封装一个固定的接口
- 编写可以实现该接口的最简单的代码
- 如果分析表明你有问题，优化（这会使代码更复杂）。
实际上，只要使用一个std::deque ，或者一个预先构build的环缓冲区（如果有的话）就足够了。 （但除非分析表明你需要，否则写入环形缓冲区是不值得的。）
这是一个最小的循环缓冲区。 我主要是在这里发表一些评论和改进的想法。
最小的实现
#include <iterator> template<typename Container> 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; } };
用法
#include <iostream> #include <array> int main() { CircularBuffer<std::array<int,5>> 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; }
编译
g++ -std=c++17 -O2 -Wall -Wextra -pedantic -Werror
演示
在Coliru上：在线试用
如果你需要存储最后的N元素，那么逻辑上你正在做某种types的队列或循环缓冲区， std :: stack和std :: deque是LIFO和FIFO队列的实现。
您可以使用boost :: circular_buffer或手动实现简单的循环缓冲区：
template<int Capcity> 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; };
示例使用 5个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] << ' '; }
需要注意的是，当你只有5个元素时，最好的解决scheme是快速实现并正常工作的解决scheme。
是。 std :: vector从时间复杂度中删除元素的结果是线性的。 std :: deque可能是你正在做的一个很好的select，因为它提供了在开始和结束时不断的时间插入和删除，也比std :: list
资源：
下面是我刚刚写的基于环形缓冲区的出队模板类的开始，主要是为了试验使用std::allocator （所以它不要求T是默认的可构造的）。 注意它目前没有迭代器，或者insert / remove ，复制/移动构造函数等。
#ifndef RING_DEQUEUE_H #define RING_DEQUEUE_H #include <memory> #include <type_traits> #include <limits> template <typename T, size_t N> class ring_dequeue { private: static_assert(N <= std::numeric_limits<size_t>::max() / 2 && N <= std::numeric_limits<size_t>::max() / sizeof(T), "size of ring_dequeue is too large"); using alloc_traits = std::allocator_traits<std::allocator<T>>; 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 <typename InputIterator> ring_dequeue(InputIterator begin, InputIterator end) { while (m_tailIndex < N && begin != end) { alloc_traits::construct(m_alloc, reinterpret_cast<T*>(m_buf) + m_tailIndex, *begin); ++m_tailIndex; ++begin; } if (begin != end) throw std::logic_error("Input range too long"); } ring_dequeue(std::initializer_list<T> il) : ring_dequeue(il.begin(), il.end()) { } ~ring_dequeue() noexcept(std::is_nothrow_destructible<T>::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 <typename... Args> 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>(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 <typename... Args> 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>(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<T> m_alloc; const T* elemPtr(size_t index) const { if (index >= N) index -= N; return reinterpret_cast<const T*>(m_buf) + index; } T* elemPtr(size_t index) { if (index >= N) index -= N; return reinterpret_cast<T*>(m_buf) + index; } }; #endif
简单地说std::vector对于一个不变的内存大小来说更好一些。在你的情况下，如果你将所有的数据向前移动或者向一个向量中添加新的数据，那肯定是浪费了。正如@David所说的std::deque是一个很好的select，因为你会pop_head和push_back例如。 双向列表。
从cplus cplus参考一下
与其他基本标准序列容器（数组，vector和双variables）相比，列表通常在已经获得迭代器的容器内的任何位置上插入，提取和移动元素方面performance更好 ，因此在执行密集使用的algorithm中这些，如sortingalgorithm。
列表和forward_lists与这些其他序列容器相比的主要缺点是它们不能直接访问元素的位置; 例如，要访问列表中的第六个元素，必须从已知位置（如开始或结束）迭代到该位置，这需要线性时间。 它们还消耗一些额外的内存来保持与每个元素相关联的链接信息（这可能是大型小元素列表的重要因素）。
关于deque
对于频繁插入或删除开始或结束位置以外的元素的操作，dequesperformance得更差，并且与列表和转发列表相比，迭代器和引用的一致性更低。
缩放的vector
因此，与arrays相比，载体消耗更多的内存来交换pipe理存储和以有效方式dynamic增长的能力。
与其他dynamic序列容器（deques，lists和forward_lists）相比，向量非常有效地访问其元素（就像数组一样），并相对有效地从元素末尾添加或移除元素。 对于涉及插入或移除除了结尾之外的位置的元素的操作，它们执行比其他位置更差的操作，并且具有比列表和forward_lists更不一致的迭代器和引用。
我想即使使用std :: deque它也有复制项目的开销在一定的条件下，因为std :: deque本质上是一个数组映射，所以std :: list是消除复制开销的好主意。
为了提高std :: list的遍历性能，你可以实现一个内存池，这样std :: list将从一个trunk中分配内存，并且它是空间局部的caching。
