Should vector always be used instead of singly-linked lists?
Author
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?
Use a vector if:
Use a list if:
Use a deque if:
Use a stack 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.
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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
