Container Holy Wars (from realloc thread)

Stoffel · 2000-02-29T15:02:11

There''s an STL container holy war going on in the realloc thread. I gave a presentation on STL a while ago (from a beginner''s point-of-view), and one of the things I presented was when to use each kind of container. I thought I''d throw it up here and see if there are any comments/criticisms: First, there are two groups: sequential and sorted. Sequential must be used when the order in which elements are added are important, regardless of their values. Sorted containers should be used when order is unimportant but searches by value through the container must be made often. The sequential containers are std::vector, std::deque, std::list, and the sorted containers are std::set, std::map, std::multiset and std::multimap. std::vector This is the fastest container, but should only be used when elements are to be added and removed from one end of the container. You are allowed to remove or insert elements in the middle, but it is an inefficient operation. std::deque (double-ended queue) Slower than vector, this container will let you add or remove elements from either end of a sequence. If insertions and deletions happen only at the beginning or end of the sequence, use this container. std::list Slowest of the sequential containers, the list allows constant insertion or deletion from any point in the list. It also allows one list to be inserted at any point in a second list in constant time. However, random access is not allowed, therefore searching for the Nth element takes linear time. std::map Map is implemented as a red-black tree. It allows storing of elements (map::value_type) that can be indexed by a separate key (map::key_type). Use maps if your container must be searched often and you want to reference elements by some arbitrary type or struct. Only one object can exist per key. std::multimap Same as map, only allows multiple objects with the same key. std::set Elements are stored in a red-black tree. Essentially, it is the same as a map, but there is no key. Finding an element in a set requires supplying the element for which to search. Only one instance of each element can exist. Use a set if it is simple to build the object for which you wish to search. std::multiset Same as set, but multiple objects of the same value are allowed. Well, hope that adds some fuel to the fire. =)

General and Gameplay Programming Programming

Started by Stoffel February 24, 2000 01:49 PM

22 comments, last by Stoffel 24 years, 6 months ago

Strauss

122

February 29, 2000 08:42 AM

You''re right, osmanb, if you will insert or delete in the end of the container, a vector will be faster than a linked list, when I wrote that post, I was thinking in an insertion on the middle of the container, in that case, a linked list will be faster.

Stoffel

Author

250

February 29, 2000 12:42 PM

quote: If you do have very strict memory management requirements, remember that every container takes an extra template parameter, allowing YOU to supply the allocator.

You''re a better person than I. I break out in cold sweats when I have to write function objects; I can''t imagine writing an allocator.

osmanb

2,082

February 29, 2000 01:17 PM

I never said I actually WRITE allocators. Unfortunately, they are the one part of STL that is severely underdocumented, even in Austern''s book, and on SGI''s site. Nonetheless, it is possible. I LOVE making function objects to do my dirty work, though. (Especially in conjunction with the generic algorithms from STL.)

-Brian

vince

122

February 29, 2000 03:02 PM

Just a note - for my bigvector<> i didn''t write an allocator. I just wrote a vector implementation from scratch that had the subset of the vector interface that I needed. I found that easier than supplying an allocator in this particular case.

-vince

-vince

Container Holy Wars (from realloc thread)

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Container Holy Wars (from realloc thread)

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines