Есть много вопросов, которые предполагают, что всегда нужно использовать вектор, но мне кажется, что список будет лучше для сценария, где нам нужно сохранить "последние 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 достаточно.
Структура данных, которую вы реализуете, называется кольцевым буфером. Для его реализации вы создаете массив и отслеживаете смещение текущего первого элемента.
Когда вы добавляете элемент, который выталкивает элемент из буфера - т.е. когда вы удаляете первый элемент - вы увеличиваете смещение.
Для извлечения элементов в буфере вы добавляете индекс и смещение и принимаете по модулю это и длину буфера.
std:: deque - гораздо лучший вариант. Или, если у вас есть benchmarked std:: deque и он считает, что его производительность неадекватна для вашего конкретного использования, вы можете реализовать циклический буфер в массиве фиксированного размера, сохраняя индекс начала буфера. При замене элемента в буфере вы должны перезаписать элемент в начальном индексе, а затем установить начальный индекс в его предыдущее значение плюс один по модулю размер буфера.
Обход списка очень медленный, поскольку элементы списка могут быть разбросаны по всей памяти, а векторное смещение на самом деле удивительно быстро, так как память перемещается по одному блоку памяти довольно быстро, даже если это большой блок.
Обсуждение Приручение зверя производительности на конференции Meeting С++ 2015 может вас заинтересовать.
Если вы можете использовать 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.
Проблема состоит в том, что 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 или предварительно построенный кольцевой буфер, если он у вас есть, будет достаточно хорошим. (Но не стоит беспокоиться о написании кольцевого буфера, если профилирование не говорит о необходимости.)
Если вам нужно сохранить последние 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 элементов, лучшим решением является тот, который быстро реализуется и работает правильно.
Вот минимальный круговой буфер. Я в первую очередь публикую это здесь, чтобы получить тонну комментариев и идей улучшения.
Минимальная реализация
#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
Да. Временная сложность std::vector для удаления элементов с конца линейна. std:: deque может быть хорошим выбором для того, что вы делаете, поскольку он предлагает постоянную вставку и удаление времени в начале, а также в конце списка, а также лучшую производительность, чем std:: list
Источник:
Вот начало класса шаблона 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
Вкратце скажем, что std::vector лучше для неизменяемого размера памяти. В вашем случае, если вы перемещаете все данные вперед или добавляете новые данные в вектор, это должно быть ненужным. Как @David сказал, что std::deque является хорошим вариантом, так как вы бы pop_head и push_back например. двухсторонний список.
из cplus cplus reference о списке
По сравнению с другими базовыми стандартными контейнерами последовательности (массив, вектор и deque), списки выполняют в целом лучше при вставке, извлечении и движущихся элементов в любом положении внутри контейнера, для которого итератор уже получен, а следовательно, и в алгоритмах которые интенсивно используют их, например алгоритмы сортировки.
Основной недостаток списков и forward_lists по сравнению с другими контейнеры последовательности - это то, что они не имеют прямого доступа к элементам посредством их положение; Например, чтобы получить доступ к шестому элементу в списке, нужно перебирать из известной позиции (например, начало или конец) в это положение, которое принимает линейное время на расстоянии между эти. Они также потребляют некоторую дополнительную память, чтобы поддерживать связь информация, связанная с каждым элементом (которая может быть важной фактор для больших списков малогабаритных элементов).
about deque
Для операций, которые включают частую вставку или удаление элементов в положениях, отличных от начала или конца, и имеют менее согласованные итераторы и ссылки, чем списки и пересылаемые списки.
Поэтому, по сравнению с массивами, векторы потребляют больше памяти в обмене за способность управлять хранилищем и динамически расти в эффективном путь.
По сравнению с другими контейнерами динамической последовательности (deques, lists и forward_lists), векторы очень эффективны для доступа к своим элементам (как и массивы) и относительно эффективное добавление или удаление элементов с ее конца. Для операций, связанных с вставкой или удаляя элементы в других местах, кроме конца, они выполняют хуже чем другие, и имеют менее последовательные итераторы и ссылки чем списки и forward_lists.
Я думаю, что даже использование std:: deque также имеет накладные расходы на элементы копирования в определенном состоянии, потому что std:: deque - это карта массивов, поэтому std:: list - хорошая идея для устранения накладных расходов на копию.
Чтобы увеличить производительность траверса для std:: list, вы можете реализовать пул памяти, чтобы std:: list выделил память из туловища и ее пространственную локальность для кеширования.