STL

Associative Containers

navigating by key
 Preliminaries:Trees
• tree – graph with no cycles
• rooted tree – a tree with a single distinguished node – root

given a node N
– ancestors – nodes on path from N to root
– descendants – nodes whose ancestor is N
– subtree – all descendants of a node
– parent – closest ancestor
– child – closest descendant
– leaf – node with no children, root – node with no parents
– height – length of longest path to a leaf
– depth – length of path to the root

• binary tree – each parent has at most two children

• search tree – nodes store keys
• sorted binary tree – key in node is greater than keys
in left subtree and less than keys right subtree

2
 Search Trees
• balanced search tree – constraint on differences in subtrees height
• self-balancing search tree – maintains balance under insert/delete operations
• red-black tree – self-balanced binary search tree with these properties
– root and leaves are black
– insertion – adding node and coloring it red
– red node’s children are always black, hence:
– longest path to leaf is no more than twice the shortest path
– guarantees O(log N)
• lookups
• insertions/deletions

3
 Pairs

• aggregates values of two, possibly different, types

• used in associative containers
• defined in <utility>
• may use a two-argument constructor
pair<int,int>(arg1,arg2)
• may copy and compare
• may access individual elements with first and second
• may create with std::make_pair(arg1,arg2) function that
returns a pair composed of arg1 and arg2

4
 Associative Containers
• do not store elements in linear order, provide mapping from keys to values
• usually insertion, deletion, lookup times are equivalent

kinds
• ordered containers - preserve order of elements
implemented using search trees
– map – stores pairs, first element is key, lookup by key
– multimap – map with multiple elements with same key
– set – element and key are the same
– multiset – multiple elements allowed

• unordered containers – C++11, do not order elements, quicker access

implemented using hash tables
– unordered_map
– unordered_multimap
– unordered_set
– unordered_multiset

5
 Maps, Declaring and Traversing
• stores sorted key/value pairs
• sorting is based on key
• insertion/deletion/lookup takes logarithmic time
• need <map> and std::map
• declaring: map <int, string> employees;
• traversing container
– may iterate over map (in order of keys) to access elements
for (auto it=employees.cbegin();
it!=employees.cend(); ++it)
cout << “Name: ” << it -> second <<
endl;
– using range-based for (C++11)
for(const auto& e: employees)
cout << e.first << ": " << e.second << endl;

6
 Maps, Lookup

• with indexing
cout << employee[123]; // access and prints value
• with find, returns end()if not found
auto it = employees.find(123);
if (it != employees.end()) cout << “Found it!”

• range (find elements from key1 to key2)

– lower_bound(key1) returns iterator to first element no smaller than key1
– upper_bound(key2) returns iterator to first element greater
than key
note the asymmetry of operation – set up to create a half-open range
both return end() if key is not there

7
 Maps, Inserting
• const-maps and maps of constant elements are allowed
• key is always implicitly const
• inserting
– “unsafe” with overloaded indexing operator, overwrites old key value if exists,
creates new if does not
employees[123] = ”Joe”;
– “safe” with insert()
auto ret=employees.insert(make_pair(123, ”Joe”));
• returns pair<map<int, string>::iterator, bool> does not
overwrite old pair with same key
– second pair element indicates whether insert was successful
-- true if element inserted
-- false if already exists
– first pair element iterator to existing or inserted map element
if(ret.second) cout << ”insert successful!” << endl;

8
 Maps, Inserting with Iterator/Range
• can insert initializer list, if constant value
auto ret=employees.insert({123, ”Joe”});

• can insert close to a “hint” iterator: inserts before iterator’s position

auto result=employees.insert(myit, make_pair(123, ”Joe”));
–may ignore hint
–returns iterator to inserted or existing pair

• can insert range

managers.insert(employees.begin(), employees.end());
–if keys equal, unspecified behavior
–no return value

9
 Maps, Erasing

• may erase at iterator, or iterator range (same as sequential containers)

– returns iterator to the next element past erased
• may erase by key: employee.erase(123);
– returns number of nodes erased

10
 Multimaps
• may store several elements with same key
• interface similar to maps
– does not provide indexing operator (does not make sense)
• lookup
– elements with same key are stored together
– find returns iterator to one of elements (not necessarily first), hence:
– lower_bound(key1), upper_bound(key2) – same operation as
for map
– equal_range(key) returns a pair of iterators for the range

• updates: same as map

– erase(key) removes all elements with key,
returns number of elements erased

11
 Sets and Multisets
• key and value are the same
– put another way: operates on scalar variables (not pairs)
• need <set> and
using std::set or using std::multiset
• keep elements sorted
• does not implement indexing (nothing to index)
• as key, element is constant and cannot be modified
– to update use erase() followed by insert()
• all expected insert()s and erase()s
– inserts: by element, with iterator hint, by iterator range
– erases: by element, iterator, range
erase(element) removes all elements from multiset

12
 Hash Tables

• an array of buckets of elements

• hash function translates (hashes) key to
bucket index
• collision – hashing different keys to same bucket
– usually resolved through pointer to linked list of elements
• implements amortized O(1) element lookup/insertion/deletion

13
 Unordered Containers
• unordered map – needs
<unordered_map> and
using std::unordered_map
– same interface as map
• no lower_bound() or upper_bound() – container is
not ordered
– plus: transparent memory implementation
• bucket_count() – number of buckets
• load_factor() = size()/bucket_count()
• max_load_factor() – returns or sets maximum load factor before bucket count
increases (1 by default)
• bucket(key) – bucket for key
• begin(key), end(key) returns local_iterator for the chain of elements in a bucket
• unordered set – needs <unordered_set> and
using std::unordered_set
– same interface as set and above bucket functions
• unordered multimap and multiset exist with expected interfaces

14
 Associative Containers Review
• What is pair class? what is first/second? what is make_pair()?
• What are associative containers? How are they different from sequential?
• How are ordered associative different from unordered? Name specific
containers in both categories.
• How is map declared? How are elements in a map accessed?
• How are elements inserted into a map? erased from a map? What is the
difference between safe and unsafe insert?
• What is multimap? How is it different from map? Does multimap provide
indexing operator? Why/why not? what are
lower_bound()/upper_bound()?
• What is set/multiset?
• What are unordered containers? What are their advantages/disadvantages
over ordered associative containers?
• What are bucket_count(), load_factor(), max_load_factor() ?

15