vector vs list in STL

Question

I noticed in Effective STL that      vector is the type of sequence that   should be used by default    What s does it mean  It seems that ignore the efficiency vector can do anything    Could anybody offer me a scenario where vector is not a feasible option but list must be used

User · Answer

Basically a vector is an array with automatic memory management. The data is contiguous in memory. Trying to insert data in the middle is a costly operation.

In a list the data is stored in unrelated memory locations. Inserting in the middle doesn't involve copying some of the data to make room for the new one.

To answer more specifically your question I'll quote this page

vectors are generally the most efficient in time for accessing elements and to add or remove elements from the end of the sequence. For operations that involve inserting or removing elements at positions other than the end, they perform worse than deques and lists, and have less consistent iterators and references than lists.

User · Answer

The only hard rule where list must be used is where you need to distribute pointers to elements of the container    Unlike with vector  you know that the memory of elements won t be reallocated  If it could be then you might have pointers to unused memory  which is at best a big no-no and at worst a SEGFAULT    Technically a vector of   ptr would also work but in that case you are  emulating list so that s just semantics    Other soft rules have to do with the possible performance issues of inserting elements into the middle of a container  whereupon list would be preferable

User · Answer

When you have a lot of insertion or deletion in the middle of the sequence  e g  a memory manager

User · Answer

If you don t need to insert elements often then a vector will be more efficient   It has much better CPU cache locality than a list   In other words  accessing one element makes it very likely that the next element is present in the cache and can be retrieved without having to read slow RAM

User · Answer

Make it simple- At the end of the day when you are confused choosing containers in C   use this flow chart image   Say thanks to me    -  Vector-  vector is based on contagious memory vector is way to go for small data-set vector perform fastest while traversing on data-set vector insertion deletion is slow on huge data-set but fast for very small  List-  list is based on heap memory list is way to go for very huge data-set list is comparatively slow on traversing small data-set but fast at huge data-set list insertion deletion is fast on huge data-set but slow on smaller ones

User · Answer

Well the students of my class seems quite unable to explain to me when it is more effective to use vectors  but they look quite happy when advising me to use lists   This is how I understand it  Lists  Each item contains an address to the next or previous element  so with this feature  you can randomize the items  even if they aren t sorted  the order won t change  it s efficient if you memory is fragmented  But it also has an other very big advantage  you can easily insert remove items  because the only thing you need to do is change some pointers  Drawback  To read a random single item  you have to jump from one item to another until you find the correct address   Vectors  When using vectors  the memory is much more organized like regular arrays  each n-th items is stored just after  n-1 th item and before  n 1 th item  Why is it better than list   Because it allow fast random access  Here is how  if you know the size of an item in a vector  and if they are contiguous in memory  you can easily predict where the n-th item is  you don t have to browse all the item of a list to read the one you want  with vector  you directly read it  with a list you can t  On the other hand  modify the vector array or change a value is much more slow   Lists are more appropriate to keep track of objects which can be added removed in memory  Vectors are more appropriate when you want to access an element from a big quantity of single items   I don t know how lists are optimized  but you have to know that if you want fast read access  you should use vectors  because how good the STL fasten lists  it won t be as fast in read-access than vector

User · Answer

Preserving the validity of iterators is one reason to use a list   Another is when you don t want a vector to reallocate when pushing items   This can be managed by an intelligent use of reserve    but in some cases it might be easier or more feasible to just use a list

User · Answer

Any time you cannot have iterators invalidated

User · Answer

One special capability of std  list is splicing  linking or moving part of or a whole list into a different list    Or perhaps if your contents are very expensive to copy  In such a case it might be cheaper  for example  to sort the collection with a list   Also note that if the collection is small  and the contents are not particularly expensive to copy   a vector might still outperform a list  even if you insert and erase anywhere  A list allocates each node individually  and that might be much more costly than moving a few simple objects around   I don t think there are very hard rules  It depends on what you mostly want to do with the container  as well as on how large you expect the container to be and the contained type  A vector generally trumps a list  because it allocates its contents as a single contiguous block  it is basically a dynamically allocated array  and in most circumstances an array is the most efficient way to hold a bunch of things

User · Answer

Lists are just a wrapper for a doubly-LinkedList in stl  thus offering feature you might expect from d-linklist namely O 1  insertion and deletion  While vectors are contagious data sequence which works like a dynamic array P S- easier to traverse

User · Answer

In the case of a vector and list  the main differences that stick out to me are the following   vector   A vector stores its elements in contiguous memory  Therefore  random access is possible inside a vector which means that accessing an element of a vector is very fast because we can simply multiply the base address with the item index to access that element  In fact  it takes only O 1  or constant time for this purpose  Since a vector basically wraps an array  every time you insert an element into the vector  dynamic array   it has to resize itself by finding a new contiguous block of memory to accommodate the new elements which is time-costly  It does not consume extra memory to store any pointers to other elements within it    list   A list stores its elements in non-contiguous memory  Therefore  random access is not possible inside a list which means that to access its elements we have to use the pointers and traverse the list which is slower relative to vector  This takes O n  or linear time which is slower than O 1   Since a list uses non-contiguous memory  the time taken to insert an element inside a list is a lot more efficient than in the case of its vector counterpart because reallocation of memory is avoided  It consumes extra memory to store pointers to the element before and after a particular element    So  keeping these differences in mind  we usually consider memory  frequent random access and insertion to decide the winner of vector vs list in a given scenario

User · Answer

Situations where you want to insert a lot of items into anywhere but the end of a sequence repeatedly   Check out the complexity guarantees for each different type of container   What are the complexity guarantees of the standard containers

User · Answer

Most answers here miss one important detail  what for   What do you want to keep in the containter   If it is a collection of ints  then std  list will lose in every scenario  regardless if you can reallocate  you only remove from the front  etc  Lists are slower to traverse  every insertion costs you an interaction with the allocator  It would be extremely hard to prepare an example  where list lt int gt  beats vector lt int gt   And even then  deque lt int gt  may be better or close  not justyfing the use of lists  which will have greater memory overhead   However  if you are dealing with large  ugly blobs of data - and few of them - you don t want to overallocate when inserting  and copying due to reallocation would be a disaster - then you may  maybe  be better off with a list lt UglyBlob gt  than vector lt UglyBlob gt    Still  if you switch to vector lt UglyBlob  gt  or even vector lt shared ptr lt UglyBlob gt   gt   again - list will lag behind   So  access pattern  target element count etc  still affects the comparison  but in my view - the elements size - cost of copying etc

User · Answer

vector    Contiguous memory  Pre-allocates space for future elements  so extra space required beyond what s necessary for the elements themselves  Each element only requires the space for the element type itself  no extra pointers   Can re-allocate memory for the entire vector any time that you add an element  Insertions at the end are constant  amortized time  but insertions elsewhere are a costly O n   Erasures at the end of the vector are constant time  but for the rest it s O n   You can randomly access its elements  Iterators are invalidated if you add or remove elements to or from the vector  You can easily get at the underlying array if you need an array of the elements    list    Non-contiguous memory  No pre-allocated memory  The memory overhead for the list itself is constant  Each element requires extra space for the node which holds the element  including pointers to the next and previous elements in the list  Never has to re-allocate memory for the whole list just because you add an element  Insertions and erasures are cheap no matter where in the list they occur  It s cheap to combine lists with splicing  You cannot randomly access elements  so getting at a particular element in the list can be expensive  Iterators remain valid even when you add or remove elements from the list  If you need an array of the elements  you ll have to create a new one and add them all to it  since there is no underlying array    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  Other than that  there are naturally instances where you re going to need one or the other based on your application  but in general  those are good guidelines

User · Answer

List is Doubly Linked List so it is easy to insert and delete an element  We have to just change the few pointers  whereas in vector if we want to insert an element in the middle then each element after it has to shift by one index  Also if the size of the vector is full then it has to first increase its size  So it is an expensive operation  So wherever insertion and deletion operations are required to be performed more often in such a case list should be used

User · Answer

When you want to move objects between containers  you can use list  splice   For example  a graph partitioning algorithm may have a constant number of objects recursively divided among an increasing number of containers  The objects should be initialized once and always remain at the same locations in memory  It s much faster to rearrange them by relinking than by reallocating   Edit  as libraries prepare to implement C  0x  the general case of splicing a subsequence into a list is becoming linear complexity with the length of the sequence  This is because splice  now  needs to iterate over the sequence to count the number of elements in it   Because the list needs to record its size   Simply counting and re-linking the list is still faster than any alternative  and splicing an entire list or a single element are special cases with constant complexity  But  if you have long sequences to splice  you might have to dig around for a better  old-fashioned  non-compliant container

[c++] vector vs. list in STL

Examples related to c++

Examples related to list

Examples related to vector

Examples related to stl