Sign in to follow this  
gimbal_lock

Should vector always be used instead of singly-linked lists?

Recommended Posts

This isn't really a help question, but it's a n00b question nonetheless. Is there any situation that would call for a singly-linked list instead of a vector, or is vector just a better container all around? I heard that STL is not part of the C++ standard and that some platforms may not have it. So, for platform independence perhaps? I'm not sure. Maybe for speed? I can't imagine that it's much faster to traverse a list full of nodes that all exist in different parts of memory than it is to directly index a node in the vector class, in fact underneath the hood they are probably the exact same thing, am I right?

Share this post


Link to post
Share on other sites
Use a vector if:
  • You need fast, random access to elements.

  • You add and remove elements infrequently.


Use a list if:
  • You need fast insertion and removal of elements.

  • You don't particularly need random access.


Use a deque if:
  • You need a compromise between the two. In many cases, the deque will actually be faster than either option anyway.


Use a stack if:
  • You need a stack. It's not a sequence container.

Share this post


Link to post
Share on other sites
I am not an expert, and I've never used the STL, so do not take the following advice/opionion as anything more.

The STL is part of the standard now, and will be on pretty much any development platform from the past 5 years. [and likely more].

The vector is not a linked list under the hood iirc.

And no, there's no real situation in C++ where you'd use your own linked list over the STL's vector [or a similar construct]. It's done, it's tested, it's fast, it's pretty complete. Now that it is part of the standard, I wish that C++ books would start with the STL rather than end with it. Unfortunately a lot of the templete jibberish kinda prevents that.

Share this post


Link to post
Share on other sites
Quote:
Original post by gimbal_lock
Is there any situation that would call for a singly-linked list instead of a vector, or is vector just a better container all around?


Depends on the situation, sometimes a vector is perfect for some situations, sometimes in others its the worst.

Besides there is no linked-list types in STL, how-ever there is a list type (list != linked-list) which is generally implementated with a doublely-linked list also STL extensions has a list (called slist) implementated with a singely-linked list but it's currently not part of the standard.

Quote:
Original post by gimbal_lock
I heard that STL is not part of the C++ standard and that some platforms may not have it. So, for platform independence perhaps? I'm not sure.


rubbish, STL is offically part of the c++ standard since it was first standardized in 1998 and all c++ compilers are required to implement it.

Quote:
Original post by gimbal_lock
Maybe for speed? I can't imagine that it's much faster to traverse a list full of nodes that all exist in different parts of memory than it is to directly index a node in the vector class, in fact underneath the hood they are probably the exact same thing, am I right?


There not the same underneath, and there not the same abstraction, list are better for insertion & deletion in abartry places, vectors are better for random access.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this