STL containers: a quick review

the standard stl sequence containers: vector, string, deque and list
the standard stl associative containers: set, multiset, map and multimap
the nonstandard sequence containers: slist and rope
the nonstandard associative containers: hash_set, hash_multiset, hash_map and hash_multimap

I find that both set and map are implemented as a tree. set is a binary search tree, map is a self-balancing binary search tree, such as red-black tree.

set has one key, map has two keys.
set is ordered, hash_set can be used to find a key quickly.

map, set, multimap, and multiset

These are implemented using a red-black tree, a type of balanced binary search tree. They have the following asymptotic run times:

Insertion: O(log n)
Lookup: O(log n)
Deletion: O(log n)

hash_map, hash_set, hash_multimap, and hash_multiset

These are implemented using hash tables. They have the following runtimes:

Insertion: O(1) expected, O(n) worst case
Lookup: O(1) expected, O(n) worst case
Deletion: O(1) expected, O(n) worst case

void example(string s)

{

set<string> my_set;

my_set.insert("abc");

my_set.insert("def");

my_set.insert("aaa");

for(set<string>::iterator iter=my_set.begin();iter!=my_set.end();iter++)

{

cout<<*iter<<endl;

}

}

output aaa, abc, def

if use hash_set: output abc, def, aaa