Menu
There are a lot of questions which suggest that one should always use a vector, but it seems to me that a list would be better for the scenario, where we need to store "the last n items"
For example, say we need to store the last 5 items seen: Iteration 0:
3,24,51,62,37, Then at each iteration, the item at index 0 is removed, and the new item 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 a vector the complexity will be O(n), since we would have to copy n items, but in a list, it should be O(1), since we are always just chopping off the head, and adding to the tail each iteration.
Is my understanding correct? Is this the actual behaviour of an std::list ?
570
std::vector is insanely faster than std::list to find an element. std::vector performs always faster than std::list with very small data. std::vector is always faster to push elements at the back than std::list. std::list handles very well large elements, especially for sorting or inserting in the front.
In general, use vector when you don't care what type of sequential container that you're using, but if you're doing many insertions or erasures to and from anywhere in the container other than the end, you're going to want to use list. Or if you need random access, then you're going to want vector, not list.
performing a linear search in a vector is several orders of magnitude faster than in a list . the only reason is the usage of the cache line. when a data is accessed, the data is fetched from the main memory to the cache.
A list holds different data such as Numeric, Character, logical, etc. Vector stores elements of the same type or converts implicitly. Lists are recursive, whereas vector is not. The vector is one-dimensional, whereas the list is a multidimensional object.
Neither. Your collection has a fixed size and std::array is sufficient.
The data structure you implement is called a ring buffer. To implement it you create an array and keep track of the offset of the current first element.
When you add an element that would push an item out of the buffer - i.e. when you remove the first element - you increment the offset.
To fetch elements in the buffer you add the index and the offset and take the modulo of this and the length of the buffer.
178
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
