Archived

This topic is now archived and is closed to further replies.

linked list VS std::vector

This topic is 5533 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

I recently wondered, if there''s an advantage of a linked list over std::vector. Quite some time ago I implemented a linked list but some weeks ago I started learning STL (I skipped that earlier ) and std::vector seems to be easier and - of course - a lot faster to implement(in development time). So I wonder, is there still a reason to use good ol'' linked lists?? Thanks for your replies! AngelForce -- If you find any mistakes, you''re allowed to keep ''em! ''When I look back I am lost.''

Share this post


Link to post
Share on other sites
You can always find a good reason to use almost any data structure.

Usually, I just use linked lists when I have a container that I know at some point I''m going to need to traverse, but I don''t need random access to it. Usually, the objects that it contains each maintain a member that is an iterator to it''s own position on the list, and that particular object takes care of removing itself from the list. Since deleting an element of a linked list doesn''t invalidate other iterators to that list, it''s extremely useful (can''t quite do that with a vector).

Share this post


Link to post
Share on other sites
With a linked list, you can have a constant random insertion/remove operations complexity (provided you already have an iterator at the "right place", obviously).

With a vector, you have a O(n) complexity for random insertion/remove operations.

So, if you need to do a lot of random insertion/remove, linked list can be faster than vectors.

Share this post


Link to post
Share on other sites
I believe that vectors are implemented using lists...correct me if I'm wrong. and you can delete elements from a vector very easily without invalidating any other elements. Just use
std::vector erase()

[edited by - xg0blin on October 18, 2002 2:46:16 PM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
You may want to use your own custom data structure vs an STL structure if you are accessing the data from multiple threads.

Implementations of the STL may not be thread-safe.

Share this post


Link to post
Share on other sites
quote:
Original post by xg0blin
I believe that vectors are implemented using lists...correct me if I''m wrong.

You''re wrong. I don''t think any vectors are implemented that way, and I believe a recent/forthcoming change to standard would prohibit it anyway.

quote:
and you can delete elements from a vector very easily without invalidating any other elements. Just use
std::vector erase()

I think you misunderstood... deleting elements doesn''t invalidate other elements, but can invalidate iterators. In the case of a vector, all iterators to elements after the deleted one are invalidated.


[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files | My stuff ]

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
You may want to use your own custom data structure vs an STL structure if you are accessing the data from multiple threads.

Implementations of the STL may not be thread-safe.


I would argue that it would normally be easier to protect the container with an exclusion device (a read/write lock would normally be suitable, I think) by hand than to reimplement the damn thing all over again.

Share this post


Link to post
Share on other sites
quote:
Original post by DrPizza
I would argue that it would normally be easier to protect the container with an exclusion device (a read/write lock would normally be suitable, I think) by hand than to reimplement the damn thing all over again.



The concern for thread-safety is not about the library itself using syncronization primatives. The issue is whether or not the library can be made thread-safe using such primatives. Some cannot be made thread-safety without a great deal of hacking - anything that uses global holes or any std::string implementation that uses the ''reference counting'' flavor are prohibitive to multi-threading, requiring thread-local-storage, and class-wide mutexes respectively. Neither of which are easy to add correctly outside the library implementation.

e.g. the MSVC6 Dinkumware STL library uses reference counted strings. It''s not part of the stl, but strtok uses a static string buffer (effectively the same as a global hole, requires TLS for a MT version).


Many stl implementations are thread-safe (meaning they can be thread-safe given proper syncronization). Virtually all stl containers are thread-safe. The strings are a ''hot-spot''.

Share this post


Link to post
Share on other sites
What would be the case in a dll?
I think you cannot use templates inside a dll(correct me if I''m wrong!)
So if you''d like to use a list inside a dll you''d have to implement a linked list?

AngelForce

--
If you find any mistakes, you''re allowed to keep ''em!

''When I look back I am lost.''

Share this post


Link to post
Share on other sites