当我们需要存储 "the last n items" 时，list 是否比 vector 更好？

Question

有很多问题表明应该始终使用向量，但在我看来，列表更适合我们需要存储 "the last n items"[=14= 的场景]

例如，假设我们需要存储最近看到的 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 的实际行为吗？

Answer 1

std::deque 是一个更好的选择。或者，如果您已经对 std::deque 进行了基准测试并发现其性能不适合您的特定用途，您可以在固定大小的数组中实现一个循环缓冲区，存储缓冲区开始的索引。替换缓冲区中的元素时，您将覆盖起始索引处的元素，然后将起始索引设置为其先前的值加上缓冲区大小的模数。

列表遍历非常慢，因为列表元素可以分散在整个内存中，向量移位实际上出奇地快，因为内存在单个内存块上的移动速度非常快，即使它是一个大块。

Meeting C++ 2015 大会上的演讲 Taming The Performance Beast 您可能会感兴趣。

Answer 2

简单地说，std::vector 对于 memory.In 的非更改大小更好，如果您向前移动所有数据或在向量中附加新数据，那必须是 waste.As @David 说 std::deque 是一个不错的选择，因为你会 pop_head 和 push_back 例如。双向列表。

来自 cplus cplus reference 关于列表

Compared to other base standard sequence containers (array, vector and deque), lists perform generally better in inserting, extracting and moving elements in any position within the container for which an iterator has already been obtained, and therefore also in algorithms that make intensive use of these, like sorting algorithms.

The main drawback of lists and forward_lists compared to these other sequence containers is that they lack direct access to the elements by their position; For example, to access the sixth element in a list, one has to iterate from a known position (like the beginning or the end) to that position, which takes linear time in the distance between these. They also consume some extra memory to keep the linking information associated to each element (which may be an important factor for large lists of small-sized elements).

关于deque

For operations that involve frequent insertion or removals of elements at positions other than the beginning or the end, deques perform worse and have less consistent iterators and references than lists and forward lists.

vetor

Therefore, compared to arrays, vectors consume more memory in exchange for the ability to manage storage and grow dynamically in an efficient way.

Compared to the other dynamic sequence containers (deques, lists and forward_lists), vectors are very efficient accessing its elements (just like arrays) and relatively efficient adding or removing elements from its end. For operations that involve inserting or removing elements at positions other than the end, they perform worse than the others, and have less consistent iterators and references than lists and forward_lists.

Answer 3

是的。 std::vector 从末尾移除元素的时间复杂度是线性的。 std::deque 可能是您正在做的事情的一个不错的选择，因为它在列表的开头和结尾提供恒定的时间插入和删除，并且性能也比 std::list

来源：

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

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

Answer 4

如果您需要存储最后的 N 个元素，那么从逻辑上讲，您正在做某种队列或循环缓冲区，std::stack and std::deque are implementations of LIFO and 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;
};

Sample use 对于 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 个元素时，最好的解决方案是实施速度快且工作正常的解决方案。

Answer 5

我认为即使使用 std::deque 它在某些情况下也会有复制项的开销，因为 std::deque 本质上是数组映射，所以 std::list 是消除复制开销。

为了提高 std::list 的遍历性能，您可以实现一个内存池，这样 std::list 将从主干中分配内存，它的空间局部性用于缓存。

Answer 6

都没有。您的 collection 大小固定，std::array 就足够了。

您实现的数据结构称为环形缓冲区。要实现它，您需要创建一个数组并跟踪当前第一个元素的偏移量。

当您添加一个元素将某个项目推出缓冲区时 - 即当您删除第一个元素时 - 您会增加偏移量。

要获取缓冲区中的元素，您需要添加索引和偏移量，并取其模数和缓冲区的长度。

Answer 7

如果可以使用 Boost，请尝试 boost::circular_buffer:

类似于std::list或std::deque的一种序列。它支持随机访问迭代器、缓冲区开头或结尾的恒定时间插入和擦除操作以及与标准算法的互操作性。

它提供固定容量存储：当缓冲区被填满时，新的数据从缓冲区的开头开始写入并覆盖旧的

// 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 ... 或实施 circular buffer directly as suggested by .

Overload Journal #50 - 2002 年 8 月 nice introduction（作者：Pete Goodliffe）编写了强大的类似 STL 的循环缓冲区。

Answer 8

这是一个最小的循环缓冲区。我将其发布在这里主要是为了获得大量评论和改进想法。

最小实现

#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

演示

On Coliru: try it online

Answer 9

这是我不久前写的基于环形缓冲区的出列模板 class 的开头部分，主要是为了尝试使用 std::allocator（所以不是要求 T 是默认可构造的）。请注意，它目前没有迭代器，或 insert/remove、copy/move 构造函数等

#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

Answer 10

问题是O(n) 只谈渐近行为，因为n 趋于无穷大。如果 n 很小，那么所涉及的常数因子就变得很重要。结果是，对于 "last 5 integer items"，如果 vector 没有击败 list，我会感到震惊。我什至希望 std::vector 击败 std::deque。

对于 "last 500 integer items" 我仍然希望 std::vector 比 std::list 快 - 但 std::deque 现在可能会赢。对于 "last 5 million slow-to-copy items"，std:vector 是最慢的。

基于 std::array 或 std::vector 的环形缓冲区可能仍然更快。

（几乎）总是存在性能问题：

封装固定接口
编写可以实现该接口的最简单代码
如果分析表明您有问题，请进行优化（这会使代码更加复杂）。

在实践中，只使用 std::deque，或者如果你有一个预建的环形缓冲区，就足够了。（但不值得费心编写环形缓冲区，除非分析表明您需要这样做。）

当我们需要存储 "the last n items" 时，list 是否比 vector 更好？

Is list better than vector when we need to store "the last n items"?

c++

buffering

fifo

data-stream

c++11