Является ли список лучше, чем вектор, когда нам нужно хранить "последние n элементов"?

Ответ 1

Ни. Ваша коллекция имеет фиксированный размер и std::array достаточно.

Структура данных, которую вы реализуете, называется кольцевым буфером. Для его реализации вы создаете массив и отслеживаете смещение текущего первого элемента.

Когда вы добавляете элемент, который выталкивает элемент из буфера - т.е. когда вы удаляете первый элемент - вы увеличиваете смещение.

Для извлечения элементов в буфере вы добавляете индекс и смещение и принимаете по модулю это и длину буфера.

Ответ 2

std:: deque - гораздо лучший вариант. Или, если у вас есть benchmarked std:: deque и он считает, что его производительность неадекватна для вашего конкретного использования, вы можете реализовать циклический буфер в массиве фиксированного размера, сохраняя индекс начала буфера. При замене элемента в буфере вы должны перезаписать элемент в начальном индексе, а затем установить начальный индекс в его предыдущее значение плюс один по модулю размер буфера.

Обход списка очень медленный, поскольку элементы списка могут быть разбросаны по всей памяти, а векторное смещение на самом деле удивительно быстро, так как память перемещается по одному блоку памяти довольно быстро, даже если это большой блок.

Обсуждение Приручение зверя производительности на конференции Meeting С++ 2015 может вас заинтересовать.

Ответ 3

Если вы можете использовать Boost, попробуйте boost:: circle_buffer:

Это своего рода последовательность, похожая на 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

circular_buffer сохраняет свои элементы в смежной области памяти, что позволяет быстро вставлять, удалять и произвольный доступ к элементам < <времени > .

PS... или внесите круговой буфер непосредственно, как предложено Taemyr.

Журнал перегрузки # 50 - август 2002 года имеет приятное введение (Питом Гудлиффом) для написания надежного кольцевого буфера STL.

Ответ 4

Проблема состоит в том, что O (n) говорит только об асимптотическом поведении, когда n стремится к бесконечности. Если n мало, то постоянные факторы становятся значительными. Результат состоит в том, что для "последних 5 целых элементов" я был бы ошеломлен, если бы вектор не разбил список. Я даже ожидал, что std::vector будет бить std::deque.

Для "последних 500 целых элементов" я бы ожидал, что std::vector будет быстрее, чем std::list, но теперь, вероятно, победит std::deque. Для "последних 5 миллионов элементов с медленным копированием" std:vector будет самым медленным из всех.

Буферный буфер на основе std::array или std::vector, вероятно, будет быстрее, хотя.

Как (почти) всегда с проблемами производительности:

• инкапсулировать с помощью фиксированного интерфейса
• напишите простейший код, который может реализовать этот интерфейс
• Если профилирование показывает, что у вас есть проблема, оптимизируйте (что сделает код более сложным).

На практике просто использовать std::deque или предварительно построенный кольцевой буфер, если он у вас есть, будет достаточно хорошим. (Но не стоит беспокоиться о написании кольцевого буфера, если профилирование не говорит о необходимости.)

Ответ 5

Если вам нужно сохранить последние N -элементы, то логически вы делаете какую-то очередь или круговой буфер, std:: stack и std:: deque являются реализациями LIFO и FIFO.

Вы можете использовать boost:: circle_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 элементов, лучшим решением является тот, который быстро реализуется и работает правильно.

Ответ 6

Вот минимальный круговой буфер. Я в первую очередь публикую это здесь, чтобы получить тонну комментариев и идей улучшения.

Минимальная реализация

#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

Demo

On Coliru: попробуйте онлайн

Ответ 7

Да. Временная сложность std::vector для удаления элементов с конца линейна. std:: deque может быть хорошим выбором для того, что вы делаете, поскольку он предлагает постоянную вставку и удаление времени в начале, а также в конце списка, а также лучшую производительность, чем std:: list

Источник:

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

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

Ответ 8

Вот начало класса шаблона dequeue, основанного на кольцевом буфере, который я написал некоторое время назад, в основном для экспериментов с использованием 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

Ответ 9

Вкратце скажем, что std::vector лучше для неизменяемого размера памяти. В вашем случае, если вы перемещаете все данные вперед или добавляете новые данные в вектор, это должно быть ненужным. Как @David сказал, что std::deque является хорошим вариантом, так как вы бы pop_head и push_back например. двухсторонний список.

из cplus cplus reference о списке

По сравнению с другими базовыми стандартными контейнерами последовательности (массив, вектор и deque), списки выполняют в целом лучше при вставке, извлечении и движущихся элементов в любом положении внутри контейнера, для которого итератор уже получен, а следовательно, и в алгоритмах которые интенсивно используют их, например алгоритмы сортировки.

Основной недостаток списков и forward_lists по сравнению с другими контейнеры последовательности - это то, что они не имеют прямого доступа к элементам посредством их положение; Например, чтобы получить доступ к шестому элементу в списке, нужно перебирать из известной позиции (например, начало или конец) в это положение, которое принимает линейное время на расстоянии между эти. Они также потребляют некоторую дополнительную память, чтобы поддерживать связь информация, связанная с каждым элементом (которая может быть важной фактор для больших списков малогабаритных элементов).

about deque

Для операций, которые включают частую вставку или удаление элементов в положениях, отличных от начала или конца, и имеют менее согласованные итераторы и ссылки, чем списки и пересылаемые списки.

vetor

Поэтому, по сравнению с массивами, векторы потребляют больше памяти в обмене за способность управлять хранилищем и динамически расти в эффективном путь.

По сравнению с другими контейнерами динамической последовательности (deques, lists и forward_lists), векторы очень эффективны для доступа к своим элементам (как и массивы) и относительно эффективное добавление или удаление элементов с ее конца. Для операций, связанных с вставкой или удаляя элементы в других местах, кроме конца, они выполняют хуже чем другие, и имеют менее последовательные итераторы и ссылки чем списки и forward_lists.

Ответ 10

Я думаю, что даже использование std:: deque также имеет накладные расходы на элементы копирования в определенном состоянии, потому что std:: deque - это карта массивов, поэтому std:: list - хорошая идея для устранения накладных расходов на копию.

Чтобы увеличить производительность траверса для std:: list, вы можете реализовать пул памяти, чтобы std:: list выделил память из туловища и ее пространственную локальность для кеширования.