) 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.''
linked list VS std::vector
Author
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.''
) 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.''
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).
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).
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.
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.
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]
std::vector erase()
[edited by - xg0blin on October 18, 2002 2:46:16 PM]
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.
Implementations of the STL may not be thread-safe.
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 ]
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.
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''.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
