Associative Containers’ Associated TypesIteration Through Associative ContainersAdding Elements to a Map or SetFinding Elements in a Multimap or MultisetUnordered Containers (UCs)Concluding RemarksCSE 332: C++ Associative Containers IIAssociative 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)•Examples 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>CSE 332: C++ Associative Containers IIIteration Through Associative Containers•Iteration is bi-directional–Can increment (e.g., ++iter1) or decrement (e.g., --iter1) an iterator•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 mapped value–E.g., iter2->second = 7; is allowedsetmultisetmapmultimap2B3A5C2C7D2B3A2C7DBACCDBACDiter1iter2CSE 332: C++ Associative Containers IIAdding Elements to a Map or Set •Insert returns a pair (may also rebalance the tree)–First part is an iterator to element, second is bool (true on success)–Multimap or multiset insert just returns an iterator to inserted element •For maps, insert takes a pair (several possible ways)–E.g., m.insert({“C”, 5}); if compiler supports 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)); set (before)set (after)map (before)2B3A5C2D7E2B3A2D7EBCDEEmap (after)BDCSE 332: C++ Associative Containers IIFinding Elements in a Multimap or Multiset •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 –E.g., s.lower_bound(“B”); gives first element not less than “B” –E.g., s.upper_bound(“B”); gives first element greater than “B” –E.g., s.equal_range(“B”); returns a pair of iterators bounding the range of elements with key “B” (or insertion point if match not found)2B3A5B2C7CBABCCiter1iter2iter1iter2CSE 332: C++ Associative Containers IIUnordered Containers (UCs)•UCs use == to compare elements instead of < to order them–Types in unordered containers must be equality comparable–When you write your own structs, overload == as well as <•UCs store elements in indexed buckets instead of in 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. Aunordered_setunordered_multisetunordered_mapunordered_multimap0B CA B CCA 7B 2C0A 7B 2C3CCSE 332: C++ Associative Containers IIConcluding Remarks•Choose carefully which operators you use–E.g., , m.insert(map<string, int>::value_type(“C”, 5)); avoids construct/destruct/assign of a temporary (vs. 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