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

Question

There are many questions that suggest that you always need to use a vector, but it seems to me that the list will be better for a scenario where we need to save the "last n elements"

For example, let's say we need to save the last 5 items: Iteration 0:

3,24,51,62,37, 

Then, at each iteration, the element at index 0 is deleted, and a new element is added at the end:

Iteration 1:

 24,51,62,37,8 

Iteration 2:

 51,62,37,8,12 

It seems that for this use case for the vector, the complexity will be O (n), since we would have to copy n elements, but in the list it should be O (1), since we are always just chopping off the head and adding each iteration to the tail.

Do I understand correctly? Is this the actual behavior of std :: list?

Answer 1

None. Your collection has a fixed size and std::array enough.

The data structure that you implement is called a ring buffer. To implement it, you create an array and track the offset of the current first element.

When you add an element that pushes an element from the buffer - i.e. when you delete the first element - you increase the offset.

To retrieve items in a buffer, you add an index and an offset and take in modulus this and the length of the buffer.

Answer 2

std :: deque is a much better option. Or, if you have a benchmarked std :: deque and thinks its performance is inadequate for your specific use, you can implement a circular buffer in a fixed-size array while maintaining the index of the beginning of the buffer. When replacing an item in a buffer, you must overwrite the item in the start index, and then set the start index to its previous value plus one modulo size buffer.

The crawl of the list is very slow, because the elements of the list can be scattered throughout the memory, and the vector offset is actually surprisingly fast, as the memory moves through one block of memory quite quickly, even if it is a large block.

Discussion Taming the Beast of Performance at a Meeting C ++ 2015 Conference may interest you.

Answer 3

If you can use Boost try boost :: circle_buffer :

This is a kind of sequence similar to std::list or std::deque . It supports random access iterators, insert and delete constant time operations at the beginning or at the end of the buffer, and compatibility with std algorithms.

It provides storage with a fixed capacity: when the buffer is full, new data is written, starting from the beginning of the buffer and overwriting the old

 // 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 stores its elements in an adjacent memory area, which allows you to quickly insert, delete and randomly access elements <<time> .

---

PS ... or add a circular buffer directly as suggested by Taemyr .

Overload Magazine # 50 - August 2002 has a nice introduction (by Pete Goodliff) for writing a robust STL ring buffer.

Answer 4

The problem is that O (n) only speaks of asymptotic behavior when n tends to infinity. If n is small, then the constant factors become significant. The result is that for the "last 5 integer elements" I would be stunned if the vector did not break the list. I even expected std::vector to beat std::deque .

For the "last 500 integer elements", I would expect std::vector be faster than std::list , but now std::deque will probably win. For "the last 5 million items with slow copy," std:vector will be the slowest of all.

The buffer buffer based on std::array or std::vector is likely to be faster though.

As (almost) always with performance issues:

• encapsulate using a fixed interface
• write the simplest code that can implement this interface
• If profiling shows that you have a problem, optimize (which will make the code more complex).

In practice, just using std::deque or a std::deque ring buffer, if you have one, would be good enough. (But don’t worry about writing a ring buffer if profiling isn’t necessary.)

Answer 5

If you need to save the last N elements, then logically you make some kind of queue or circular buffer, std :: stack and std :: deque are implementations of LIFO and FIFO .

You can use boost :: circle_buffer or manually execute a simple 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; }; 

Example usage for a circular buffer of 5 int elements:

 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] << ' '; } 

As a side note, keep in mind that when you have only 5 elements, the best solution is one that quickly implements and works correctly.

Answer 6

Here is the minimum circular buffer. First of all, I am posting this here to get a ton of comments and improvement ideas.

Minimal implementation

 #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; } }; 

Using

 #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; } 

Compile with

 g++ -std=c++17 -O2 -Wall -Wextra -pedantic -Werror 

Demo

On Coliru: try it online

Answer 7

Yes. The time complexity of std :: vector to remove elements from the end is linear. std :: deque may be a good choice for what you are doing, as it offers constant insertion and deletion of time at the beginning as well as at the end of the list, as well as better performance than std :: list

Source:

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

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

Answer 8

Here is the beginning of the ring buffer-based dequeue template class that I wrote some time ago, mainly for experimenting with std::allocator (so T doesn't need a default constructor). Note that it currently does not have iterators, or insert / remove , copy / move constructors, etc.

 #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 9

In short, std::vector better for immutable memory size. In your case, if you move all the data forward or add new data to the vector, this should be unnecessary. Like @David said std::deque is a good option, as you would pop_head and push_back for example. bilateral list.

from cplus cplus reference about the list

Compared to other basic standard container containers (array, vector, and deque), lists generally perform better when inserting, retrieving, and moving elements in any position inside a container for which an iterator has already been received, and therefore in algorithms that use them intensively e.g. sorting algorithms.

The main disadvantage of lists and forward_lists compared to other sequence containers is that they do not have direct access to elements through their position; For example, to access the sixth element in the list, you need to iterate from a known position (for example, the beginning or end) to this position, which takes linear time at a distance between these. They also consume some additional memory to keep in touch the information associated with each item (which can be an important factor for large lists of small items).

about deque

For operations that involve frequently inserting or deleting elements at positions other than the beginning or end and that have less consistent iterators and links than lists and forwarded 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 other dynamic sequence containers (deques, lists, and forward_lists), vectors are very effective for accessing their elements (like arrays) and are relatively effective for adding or removing elements from its end. For operations related to inserting or deleting elements in places other than the end, they perform worse than others, and have less sequential iterators and links than lists and forward_lists.

Answer 10

I think that even using std :: deque also has overhead for copy elements in a certain state, because std :: deque is an array map, so std :: list is a good idea to eliminate copy overhead.

To increase the traverse performance for std :: list, you can implement a memory pool so that std :: list allocates memory from the trunk and its spatial locality for caching.