• Advertisement
Sign in to follow this  

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

This topic is 4871 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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
Sign in to follow this  

  • Advertisement