有很多问题表明应该始终使用向量，但在我看来，对于需要存储“最后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已经足够。
你实现的数据结构叫做环形缓冲区。为了实现它，你需要创建一个数组，并跟踪当前第一个元素的偏移量。
当你添加一个将推出缓冲区的元素时 - 也就是当你删除第一个元素时 - 你会增加偏移量。
要在缓冲区中获取元素，你需要将索引和偏移量相加并对缓冲区的长度取模。
boost::circular_buffer。 - GManNickGstd::deque是更好的选择。如果你对其性能进行了基准测试，发现它在特定用途下表现不佳，那么你可以在固定大小的数组中实现循环缓冲区，并存储缓冲区起始位置的索引。当替换缓冲区中的元素时，您将覆盖起始索引处的元素，然后将起始索引设置为其先前值加上缓冲区大小的模数。
列表遍历非常慢，因为列表元素可能分散在内存中，而向量移位实际上非常快，因为单个内存块上的内存移动非常快，即使它是一个大块。
Taming The Performance Beast这次Meeting C++ 2015会议的演讲可能对您有兴趣。
std::deque 使用数组，但不止一个。引用自cppreference："与std::vector不同，deque的元素不是连续存储的：典型实现使用一系列单独分配的固定大小数组"。这仍然比每个单独的项目在不同的位置分别分配要好得多。 - Wyzard
std::list 或者 std::deque 的序列。它支持随机访问迭代器，常数时间的在缓冲区开头或结尾进行插入和删除操作，并且可以与 std 算法互操作。// 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
《Overload Journal #50 - Aug 2002》（Pete Goodliffe撰写）对编写强健的类似STL的循环缓冲区有一个不错的介绍。
N个元素，那么逻辑上您正在执行某种队列或循环缓冲区操作，std::stack和std::deque是LIFO和FIFO队列的实现。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 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] << ' ';
}
#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
演示
pop_front所需的时间也会相应增加——随着向量变得越来越长，pop_front涉及的操作数量呈线性增长。这就是我们所说的“O(N)”。 - Quuxplusone以下是我一段时间前写的基于环形缓冲区的双端队列模板类的开端，主要是为了尝试使用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 是一个不错的选择，因为您需要使用 pop_head 和 push_back 等双向列表操作。关于列表的更多信息，请参考 cplus cplus reference。因此，与数组相比，向量在消耗更多内存的同时具备了管理存储和以高效的方式动态增长的能力。
与其他动态序列容器（双端队列、列表和前向列表）相比，向量非常高效地访问其元素（就像数组一样），并且在从其末尾添加或删除元素方面相对高效。对于涉及在位置末尾以外插入或删除元素的操作，它们表现不如其他容器，并且迭代器和引用不如列表和前向列表一样一致。
std::list 是一个双向链表，因此从前面和后面都同样好用。 - Zan Lynxstd::deque 保存更大的块并使它们看起来既像向量又像列表。它就像是向量的列表。它的性能比列表更接近向量。 - Zan Lynxdeque 具有随机访问，而 list 则没有。 - MSalters我认为即使使用std::deque，在某些情况下它也会有复制项目的开销，因为std::deque本质上是一个数组映射，所以使用std::list是消除复制开销的好方法。
为了增加std::list的遍历性能，您可以实现一个内存池，这样std::list将从主干分配内存，并具有缓存的空间局部性。