Associative Containers in C++

E81 CSE 428S: Multi-Paradigm Programming in C++ Associative Containers Department of Computer Science & Engineering Washington University, St. Louis MO Chris Gill cdgill@wustl.edu 1

Some Standard Associative Containers The std::set class template Balanced binary tree that orders keys (e.g., by operator<) No duplicate keys are allowed (all are unique) Inserting, finding, and deleting a key are all O(log(n)) The std::multiset class template Like std::set but duplicate keys are allowed The std::map class template Balanced binary tree that orders keys (e.g., by operator<) and each key has an associated value that may be of another type No duplicate keys are allowed (all are unique) but different keys may have the same value associated with them Inserting, finding, and deleting a key/value pair all O(log(n)) The std::multimap class template Like std::map but duplicate keys are allowed CSE 428S Multi-Paradigm Programming in C++ 2

More Standard Associative Containers The std::unordered_set class template Hash map that stores keys using operator== and a hash function No duplicate keys are allowed (all are unique) The std::unordered_multiset class template Like std::unordered_set but duplicate keys are allowed The std::unordered_map class template Hash map that stores key/value pairs using operator== and a hash function No duplicate keys are allowed (all are unique) but different keys may have the same value associated with them The std::unordered_multimap class template Like std::unordered_map but duplicate keys are allowed CSE 428S Multi-Paradigm Programming in C++ 3

Associative Containers Associated Types Associative containers declare additional types A key_type gives the type of keys the container holds A value_type gives the type of values the container holds A mapped_type gives type associated with key (maps only) For sets key and value types are the same Associated type set<int>::key_type is int, as is set<int>::value_type Examples for maps (note key becomes const in value) Associated type map<int, string>::key_type is int Type map<int, string>::mapped_type is string Associated type map<int, string>::value_type is pair<const int, string>

Iteration Through Associative Containers set map C C 2 iter2 B B 2 D D 7 A A 3 multiset multimap C C 2 iter1 B B 2 D D 7 A A 3 C C 5 Iteration is bi-directional Can increment (e.g., ++iter1) or decrement (e.g., --iter1) Dereferencing gives read-only access to keys E.g., *iter1 = D ; or iter2->first = D ; are not allowed But, can gain read-write access to map s value E.g., iter2->second = 7; is allowed

Adding Elements to a Map or Set set (before) map (before) E D 2 D B 2 E 7 B A 3 set (after) map (after) D D 2 B B 2 E E 7 A 3 C C 5 Insert returns a pair (may also rebalance the tree) First part is an iterator to element, second is true on success Multi{map,set} insert just returns iterator to inserted element For maps, insert takes a pair (several possible ways) E.g., m.insert({ C , 5}); // list initialization E.g., m.insert(make_pair( C , 5)); E.g., m.insert(pair<string, int>( C , 5)); E.g., m.insert(map<string, int>::value_type( C , 5));

Finding Elements in a Multimap or Multiset iter2 iter2 C C 2 iter1 iter1 B B 2 C C 7 A A 3 B B 5 Find returns an iterator to first matching element Forward iteration from first matching element (if one was found) gives all other equal elements (find returns past the end iterator if no match) Can obtain iterators bounding range of equal elements s.lower_bound( B ); gives first element not less than B s.upper_bound( B ); gives first element greater than B s.equal_range( B ); returns a pair of iterators bounding the range of elements with key B (or insertion point if not found)

Unordered Containers (UCs) unordered_set unordered_multiset unordered_map unordered_multimap A B C A 0 B 7 C 2 C 3 C A 0 B 7 C 2 A B C UCs use == to compare (instead of < to order) elements Types in unordered containers must be equality comparable When you write your own structs/classes, overload == vs. < UCs store elements in indexed buckets instead of a tree Useful for types that don t have an obvious ordering relation over their values UCs use hash functions to put and find elements in buckets May improve performance in some cases (if performance profiling suggests so) Declare UCs with pluggable hash functions via callable objects, decltype, etc.

Some Nuances Choose carefully which operators you use E.g., , m.insert(map<string, int>::value_type( C , 5)); avoids extra copying of a temporary (as in m[ C ] = 5);) Also realize that overloaded operator[] has different interpretations in different containers In a vector or other random access sequence container it s a constant time indexing operation to a particular location In a map or other associative container it s a logarithmic time operation ( find or insert versus read or write ) Unordered containers give another mix of operations E.g., via hashing, for which callable objects can be used

Studio 19 Looks at the ordered associative containers Considers how different ordering semantics may arise from the types they contain or from explicit callable types that are given to them Explores how different container member functions and standard algorithms work with them Studios 12 through 19 are due 11:59pm Wednesday November 29th (night before Exam 1) Submit as soon as each is done so you get feedback and can resubmit any that may be marked incomplete CSE 428S Multi-Paradigm Programming in C++ 10