### vectors vs lists

helllo!

my question is about the lists if i can change a random element of a list like i can do it with vectors

for example
if i have

 ``123`` ``````vector v; for(int i=0;i<10;i++) v.push_back(i); v[5]=14;``````

can i do that with lists??(to change the sixth element for example)

or to delete the sixth element..can i do also that??

i know that lists are faster than vectors
 i know that lists are faster than vectors

For most purposes, it's the other way round. Lists are faster when you regularly need to insert elements in between two other elements, or delete elements from such positions though.

As to the question: Lists don't support random access, but you can get the nth element with

 ``123`` ``````auto it = li.begin(); for(int i=0; i

There's probably some better method, but I can't think of it right now.
Last edited on
That's the disadvantage. You could access/erase nth element like this:
 ``123`` ``````list<...>::iterator it = myList.begin(); for(int i = 0; i < n; i++) it++; *it = 14;``````

But that is much slower than using [] on vector. See http://en.wikipedia.org/wiki/Linked_list#Linked_lists_vs._dynamic_arrays
> Lists are faster when you regularly need to insert elements in between two other elements, or delete elements from such positions though.

Yeah, that is one typical use-case for the std::list<>.

The other is when one needs a 'strong guarantee' of exception safety. http://www2.research.att.com/~bs/3rd_safe0.html
There is anothers disavantages of lists which may be important when working withs small objects:
-these are doubly linked lists so there is an extra two pointers used for every elemnts so for a `list<T>` of n elements will use approximately `(sizeof(T) + 2 * sizeof(void*)) * n = n*sizeof(T) + 2 * n * sizeof(void*)`. This is negligable for big types but can be an issue for very small types like int. For` vector<T>` the reserved memory, if not specified with reserve() could vary upon implementations but it is usualy less than `2*n*sizeof(T)`.
-For a list each time an element have to be added a node must be allocated which implies a call to `malloc`(unless you use your own allocator) and malloc have a non-negligable cost. The same for `free`() when an element is removed. With a vector there is no allocations if the reserved memory is big enough(but the cost of a reallocation if not can be very bad)
Last edited on
For the fist point i just thouht std::forward_list of c++11 partially adress this problem as it is a singly linked list and thereof use `n * (sizeof(T) + sizeof(void*))` instead.
Last edited on
@JLBorges, thank you very much for that link. Now I'm a lot less paranoid about exceptions than I used to be. Maybe I'll even start using them if I do something non-trivial in C++..
 my question is about the lists if i can change a random element of a list like i can do it with vectors can i do that with lists??(to change the sixth element for example)

list is organized such a way that you have sequential access to its elements. So list has no random access iterator and no subscripting operator [].

To change the sixth element of a list you should use function std::advance to move an iterator to the position of the sixth element. For example

 ``123456789`` ``````std::list lst; // code to fill the list auto it = lst.begin(); std::advance( it, 6 ); if ( it != lst.end() ) *it = new_value;``````

Last edited on
@hamsterman, Section 2.4 of the TR on C++ Performance (which discusses the performance costs of error handling) might interest you. The Final Draft of TR 18015 is publicly available here: http://www.open-std.org/jtc1/sc22/wg21/docs/TR18015.pdf
Topic archived. No new replies allowed.