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

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

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

Разговор Укрощение Производительность зверя с конференции Meeting C ++ 2015 может быть интересным для вас.

Если вы можете использовать Boost, попробуйте повышение :: circular_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-подобного кольцевого буфера.

Проблема в том, что 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или предварительно созданный кольцевой буфер, если он у вас есть, будет достаточно хорош. (Но это не стоит того, чтобы писать кольцевой буфер, если профилирование не говорит о том, что вам нужно.)

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

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

#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-elements затем логически вы делаете какую-то очередь или кольцевой буфер, станд :: стек а также станд :: Deque являются реализациями LIFO а также ФИФО Очереди.

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

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

Источник:

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

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

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