Advantages of a slide over a vector?

Question

I need only a dynamically growing array. I don’t need random access, and I always insert it at the end and read it from beginning to end.

slist seems like the first choice, because it provides only what I need. However, I can’t say what benefit I get using a slide instead of a vector. In addition, several articles I read about STL say: "vectors are usually the most effective over time to access elements and add or remove elements from the end of the sequence." So my question is: for my needs, is slash really a better choice than vector? Thanks in advance.

Answer 1

For starters, slist is non-standard.

For your choice, a linked list will be slower than a vector to count on it. There are two reasons for this:

• First of all, the location of the cache; vectors store their elements linearly in RAM, which facilitates caching and prefetching.
• Secondly, adding to the linked list is associated with dynamic allocations that add a lot of overhead. In contrast, vectors do not need to allocate memory most of the time.

However, std::deque is likely to be even faster. An in-depth performance analysis showed that, despite the bias, std::deque almost always surpasses the performance of std::vector (if random access is not needed) due to an improved (allocated) memory allocation strategy.

Answer 2

Yes, if you always read the beginning to the end, the slist (linked list) sounds like a way to go. A possible exception is that you will simultaneously add a large number of elements to the end. Then the vector might be better if you use the reserve appropriately.

Of course, a profile to be sure that it is better for your application.

Answer 3

Matt Austern (author of "Generic Programming and the STL" and C ++ general guru) is a strong proponent of single-level lists for inclusion in the upcoming C ++ standard; see his presentation http://www.accu-usa.org/Slides/SinglyLinkedLists.ppt and his long article at http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/ n2543.htm for more details, including a discussion of the trade-offs that may help you choose this data structure. (Note that the currently proposed name is forward_list , although slist is what it was traditionally named in SGI STL and other popular libraries).

Answer 4

I will be the second (or maybe the third ...) opinion that std::vector or std::deque will do the job. The only thing I will add is a few additional factors that should determine the solution between std::vector<T> and std::list<T> . They have a lot in common with the T characteristics and the algorithms you plan to use.

Firstly, this is the memory overhead. Std::list is a node-based container, so if T is a primitive type or a relatively small user type, then the node-based memory overhead may not be significant - consider that std::list<int> is likely to use the storage is at least 3 * sizeof(int) for each element, whereas std::vector will use the storage sizeof(int) with little overhead at the top level. std::deque is similar to std::vector , but has a little overhead that is linear up to N

The next question is the cost of building a copy. If T(T const&) generally expensive, then avoid std::vector<T> , as this leads to multiple copies appearing as the size of the vector increases. Here std::deque<T> is the clear winner, and std::list<T> also the contender.

The final problem that usually determines the decision on the type of container is whether your algorithms can work with the annulment restrictions of the std::vector and std::deque iterator. If you manipulate the elements of the container a lot (for example, sorting, pasting in the middle or shuffling), you can lean towards Std::list , since order management takes a little more than resetting a few binding pointers.

Answer 5

I assume you mean std :: list on "slist". Vectors are good when you need fast, random access to a sequence of elements, with guaranteed continuous memory and fast sequential reading (IOW, from start to finish). Lists are good when you need to quickly (permanently) insert or delete items at the beginning or end of a sequence, but don't care about random access or sequential read performance.

The reason for the difference is the implementation method 2. Vectors are implemented internally as an array of elements that need to be redistributed when its size / capacity is reached when adding the element. Lists are implemented as a doubly linked list, which may lead to skipping the cache for sequential reads. For random access lists, lists also need to scan from the first (or last) item in the list until it finds the requested item.

Answer 6

Sounds nice to std :: deque to me. It has memory advantages, such as contiguous allocation of memory for each "plate" (useful for CPU caches), no overhead for each element, for example, using std :: list, and it does not need to redistribute the whole set, like std :: vector, Learn more about std :: deque here