vectors vs lists

[vagelis]

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

vector<int> 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
but what are the dissadvantages?

[hanst99]

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

auto it = li.begin();
for(int i=0; i<n; ++n) ++it;
element = *it;

There's probably some better method, but I can't think of it right now.

[hamsterman]

That's the disadvantage. You could access/erase nth element like this:

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

[JLBorges]

> 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

[aquaz]

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)

[aquaz]

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.

[hamsterman]

@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++..

[vlad from moscow]

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

std::list<int> lst;

// code to fill the list

auto it = lst.begin();

std::advance( it, 6 );

if ( it != lst.end() ) *it = new_value;

[JLBorges]

@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