Standard Associative Containers Associative Containers Set/Map
Overview
Ordered Sets
 |
Hash Sets
 |
std::set<int> s {9,2,8};
s.insert(7);
s.erase(8);
if (s.find(7) != end(s)) {…}
if (s.contains(7)) {…} C++20
// find returns an iterator:
auto i = s.find(7);
if (i != end(s)) i = s.erase(i);std::multiset<int> s;
s.insert(8);
s.insert(7);
s.insert(2);
s.insert(7);
s.erase(7);{}
{8}
{7, 8}
{2, 7, 8}
{2, 7, 7, 8}
{2, 8}Ordered Key→Value Maps
 |
Hashed Key→Value Maps
 |
Maps store std::pair<Key const,Value>
Maps store pair<Key const,Value>
pair<K,V>
The standard library associative containers are based on nodes that are linked by pointers. Each node stores a pair of a key and a value.
std::pair<First,Second>
contains two values of different or same type
#include <utility>
std::pair<int,double> p {4, 8.15};
cout << p.first <<'\n'; // 4
cout << p.second <<'\n'; // 8.15
// C++17 features:
std::pair p2 {4, 8.15}; // std::pair<int,double>
auto [fst,snd] = p2; // structured binding
cout << fst <<" "<< snd <<'\n'; // 4 8.15std::map<int,std::string> m;
m.insert({2, "B"});
m.emplace(1, "A");
m[2] = "Y"; // modify
m[3] = "C"; // insert!
auto i = m.find(2);
if (i != end(m))
cout << i->first
<< i->second;
if (m.contains(2)) {…} C++20
m.erase(2);
auto j = m.find(3);
if (j != end(m)) j = m.erase(j);
// C++17 features:
m.insert_or_assign(4,"D");
m.insert_or_assign(1,"X");
m.try_emplace(4,"Z");
m.try_emplace(5,"E");{ }
{2:B}
{1:A,2:B}
{1:A,2:Y}
{1:A,2:Y,3:C}
→ iterator
if found
2 (key)
Y (value)
true (2 found)
{1:A,3:C}
j
{1:A }
j (after)
{1:A}
{1:A,4:D}
{1:X,4:D}
{1:X,4:D}
{1:X,4:D,5:E}std::multimap<int,std::string> m;
m.emplace(1, "A");
m.insert({2, "B"});
m.emplace(1, "C");
m.erase(1);{ }
{1:A}
{1:A,2:B}
{1:A,1:C,2:B}
{ 2:B}Keys or key-value pairs are stored in nodes that
are linked
by pointers.
Ordered Sets/Maps
usually implemented as balanced binary tree
Unordered Sets/Maps
implemented as hash table
How To
std::set<int> s1;
std::set<int> s2 {};
std::map<int,float> m1;
std::map<int,float> m2 {};This is a function declaration:
std::set<int> s3 ();std::set<int> s1 {12};
std::set<int> s2 {3,2,1,4,5};
std::set s3 {1, 2, 3, 4}; // set<int> C++17
std::set s4 {1.f, 2.3f, 4.5f}; // set<float> C++17
std::set s5 {1., 2.3, 4.6}; // set<double> C++17std::vector<int> v {2,3,1,4};
std::set<int> s (begin(v),begin(v)+3);v: - 2
- 3
- 1
- 4
s: {1,2,3}std::set<int> s;
s.insert(3)
auto r1 = s.insert(7);
cout << r1.second;
cout << *r1.first;
auto r2 = s.insert(7);
cout << r2.second;{ }
{3}
{3,7}
true (inserted)
7
false (NOT inserted)using VS = std::vector<std::string>;
std::set<VS> s;
s.insert( VS{"a","c"} );
s.emplace("v","w","x");
{ }
{{"a","c"}}
{{"a","c"},{"v","w","x"}}std::set<int> s;
s.insert({3,5});
vector<int> v {2,4,1};
s.insert(begin(v),end(v));{ }
{3,5}
{1,2,3,4,5}std::set<int> s {1,4};
auto h = s.find(4);
s.insert(h, 3);
h = s.find(1);
s.insert(h, 2);
{1, 4}
h
{1, 3, 4}
{1, 3, 4}
h
{1, 2, 3, 4}std::map<int,std::string> m;
auto r1 = m.insert({1,"a"});
cout << r1.second;
cout << *r1.first;
auto r2 = m.insert({1,"b"});
cout << r2.second;
cout << *r2.first;{ }
{1:"a"}
true (inserted)
"a" (key at position)
{1:"a"}
false (NOT inserted)
"a" (key at position)struct P2 { // custom value type
P2 (int x_, int y_): x{x_}, y{y_} {}
int x, y;
};std::map<char,P2> m;
m.insert( {'a', P2{1,2}} );
m.emplace('c', P2{3,4});
m.try_emplace('b', 5,6);
m.try_emplace('a', 8,9);{ }
{'a':{1,2}}
{'a':{1,2},'c':{3,4}}
{'a':{1,2},'b':{5,6},'c':{3,4}}
{'a':{1,2},'b':{5,6},'c':{3,4}}std::map<int,std::string> m;
m[1] = "a";
m[1] = "x";
m.insert_or_assign(3,"c")
m.insert_or_assign(3,"u")
try {
m.at(1) = "y";
m.at(2) = "z";
} catch(std::out_of_range&) {…}{ }
{1:"a"}
{1:"x"}
{1:"y",3:"c"}
{1:"y",3:"u"}
{1:"y",3:"u"}
← throws exceptionstd::vector<pair<int,string>> v;
v.emplace_back(3,"c");
v.emplace_back(1,"a");
v.emplace_back(2,"b");
map<int,string> m;
m.insert(begin(v), end(v));// final result
m: {1:"a",2:"b",3:"c"}std::map<int,std::string> m;
m.insert({4,"d"});
auto h1 = m.find(4);
m.insert(h1, {1,"a"});
auto h2 = m.find(1);
m.emplace(h2, 3,"c");{ }
{4:"d"}
{4:"d"}
h1
{1:"a",4:"d"}
{1:"a",4:"d"}
h2
{1:"a",3:"c",4:"d"}std::set<int> s {1,3,5,6};
if (s.find(6) != end(s)) {…}
if (s.find(7) != end(s)) {…}
if (s.contains(6)) {…}
if (s.contains(7)) {…}
true
false
true
falsestd::set<int> s {1,3,5,6};
auto i = s.find(3);
if (i != end(s)) {
cout << *i;
i = s.erase(i);
}
auto j = s.find(4);
if (j != end(s)) {…}{1, 3, 5, 6 }
i
true
3
{1, 5, 6 }
i (after)
{1, 5, 6 }
j
falsestd::map<int,std::string> m;
m[1] = "a";
m[2] = "b";
m[1] = "x";
try {
m.at(2) = "y";
m.at(3) = "z";
} catch(std::out_of_range&) {…}{ }
{1:"a"}
{1:"a",2:"b"}
{1:"x",2:"b"}
{1:"x",2:"y"}
← throws exceptionstd::multiset<int> s {1,3,3,6,9};
cout << s.count(1);
cout << s.count(2);
cout << s.count(3);
std::map<int,std::string> m {{1,"a"},{3,"b"}};
cout << m.count(1);
cout << m.count(2);
1
0
2
1
0It is not possible to modify keys through iterators or in range based for loops, because this could break the container invariant (key ordering or position in the hash table).
// keys that are cheap to copy:
std::set<int> s1 { … };
for (auto key : s1) { … }
// keys that are expensive to copy:
std::set<std::string> s2 { … };
for (auto const& key : s2) { … }
// C++17: lightweight key-value pairs
std::map<int,std::string> m2 { … };
for (auto [key,value] : m2) {
cout << key <<":"<< value <<" "; }
// C++17: expensive-to-copy key-value pairs
std::map<int,std::string> m2 { … };
for (auto const& [key,value] : m2) {
cout << key <<":"<< value <<" "; }
// C++11: lightweight key-value pairs
std::map<int,std::string> m1 { … };
for (auto kv : m1) {
cout << kv.first <<":"<< kv.second <<" "; }
// C++11: expensive-to-copy key-value pairs
std::map<int,std::string> m1 { … };
for (auto const& kv : m1) {
cout << kv.first <<":"<< kv.second <<" "; }std::set<int> s {1,3,9};
auto i = begin(s);
const auto e = end(s);
cout << *i;
// go to next
++i;
cout << *i;{1,3,9 }
i e
1
{1,3,9 }
3std::map<int,std::string> m {
{1,"a"}, {2,"b"}};
auto i = begin(m);
const auto e = end(m);
cout << i->first
<< i->second;
++i;
auto kvpair = *i;
cout << kvpair.first
<< kvpair.second;
auto [k,v] = *i;
cout << k <<" "<< v;
{1:"a", 2:"b" }
i e
1
"a"
{1:"a", 2:"b" }
2
"b"
C++17
2 "b"std::set<int> s {1,3,9};
auto i = rbegin(s);
const auto e = rend(s);
cout << *i;
// go to next
++i;
cout << *i;{ 1,3,9}
e i
9
{1,3,9 }
3std::map<int,std::string> m {
{1,"a"}, {2,"b"}};
auto i = rbegin(m);
const auto e = rend(m);
cout << i->first
<< i->second;
++i;
auto kvpair = *i;
cout << kvpair.first
<< kvpair.second;
auto [k,v] = *i;
cout << k <<" "<< v;
{ 1:"a", 2:"b"}
e i
2
"b"
{ 1:"a", 2:"b"}
1
"a"
C++17
1 "a"(available for all sets/maps)
.equal_range(key)→pair<@range_begin,@range_end>
This follows the usual
iterator range
convention, so @range_end points to one behind the last
element in the range.
std::multiset<int> s {2,4,4,4,6};
// 4 is a non-unique key:
auto e4 = s.equal_range(4);
cout << *(e4.first)
<< *(e4.second);
auto n = distance(e4.first,
e4.second);
// 1 is smaller than all:
auto e1 = s.equal_range(1);
// → empty range
// 2 is the smallest key:
auto e2 = s.equal_range(2);
// → range with 1 element
// 3 is in between keys:
auto e3 = s.equal_range(3);
// → empty range
// 6 is the largest key:
auto e6 = s.equal_range(6);
// → range with 1 element
// 7 is larger than all:
auto e7 = s.equal_range(7);
// → empty range
{2,4,4,4,6 }
4 (first in range)
6 (1 behind last)
n: 3 (range size)
{2,4,4,4,6 }
{2,4,4,4,6 }
{2,4,4,4,6 }
{2,4,4,4,6 }
{2,4,4,4,6 }
(ordered sets/maps only)
.lower_bound(key)→@first_not_less_than_key.upper_bound(key)→@first_greater_than_key
std::multiset<int> s {2,4,4,4,6};
// 1 is smaller than all:
auto l1 = s.lower_bound(1);
auto u1 = s.upper_bound(1);
if (l1 != end(s)) cout << *l1;
if (u1 != end(s)) cout << *u1;
// 2 is the smallest key:
auto l2 = s.lower_bound(2);
auto u2 = s.upper_bound(2);
if (l2 != end(s)) cout << *l2;
if (u2 != end(s)) cout << *u2;
// 3 is in between keys:
auto l3 = s.lower_bound(3);
auto u3 = s.upper_bound(3);
if (l3 != end(s)) cout << *l3;
if (u3 != end(s)) cout << *u3;
// 4 is a non-unique key:
auto l4 = s.lower_bound(4);
auto u4 = s.upper_bound(4);
if (l4 != end(s)) cout << *l4;
if (u4 != end(s)) cout << *u4;
// 6 is the largest key:
auto l6 = s.lower_bound(6);
auto u6 = s.upper_bound(6);
if (l6 != end(s)) cout << *l6;
if (u6 != end(s)) cout << *u6;
// 7 is larger than all:
auto l7 = s.lower_bound(7);
auto u7 = s.upper_bound(7);
if (l7 != end(s)) cout << *l7;
if (u7 != end(s)) cout << *u7;
{2,4,4,4,6 }
true → 2
true → 2
{2,4,4,4,6 }
true → 2
true → 4
{2,4,4,4,6 }
true → 4
true → 4
{2,4,4,4,6 }
true → 4
true → 6
{2,4,4,4,6 }
true → 6
false @end
{2,4,4,4,6 }
false @end
false @endEither with member functions:
container.empty()→ true, if container has no keyscontainer.size()→ total number of keys or key-value pairs
Or with free-standing functions:
std::map<int;std::string> m;
cout << m.empty();
cout << m.size();
m.insert(3,"x");
cout << m.empty();
cout << m.size();
m.insert(1,"y");
cout << m.size();{ }
true
0
{3:"x"}
false
1
{1:"y",3:"x"}
2std::multiset<int> s {1,3,3,7,9};
auto n = s.erase(3)
cout << n;
s.erase(7){1,3,3,7,9}
{1,7,9}
2
{1,9}std::set<int> s {1,3,6,8,9};
auto i = s.find(3);
i = s.erase(i);
auto j = s.erase(begin(s), s.find(8));{1,3,6,8,9}
i
{1,6,8,9}
i (after)
{1,6,8,9}
{8,9}
jstd::set<int> s {1,2,5,8};
s.clear();
s.empty();{1,2,5,8}
{ }
trueExtract & (Re-)Insert Nodes Extract/(Re-)Insert Nodes C++17
.extract(key)→node.extract(@position)→node
.insert(node)→@insert_position
container::node_type
Important Member Functions:
.key()→key_type&.mapped()→mapped_type&
set<string> s {"a","b","e"};
set<string> t {"x","z"};
t.insert(s.extract("a"));s: {"a","b","e"}
t: {"x","z"}
s: { "b","e"}
t: {"a","x","z"}set<string> s {"a","c","e"};
auto na = s.extract("a");
na.key() = "z";
// move node back in
s.insert(std::move(na));
map<int,string> m { {2,"a"},{3,"x"}};
auto n2 = m.extract(2);
n2.key() = 5;
// move node back in
m.insert(std::move(n2));{"a","c","e"}
get node
change key
{"c","e","z"}
{2:"a",3:"x"}
get node
change key
{3:"x",5:"a"}std::set<int> a {4,7,1,9};
std::set<int> b {1,2,3};
bool equal1 = (a == b);
// copy assignment:
a = b;
bool equal2 = (a == b);
b.clear();
bool equal3 = (a == b);
// ways of making copies:
std::set<int> a2 {a};
std::set<int> a3 (a);
std::set<int> a4 = a;
auto a5 {a};
auto a6 (a);
auto a7 = a;a: {4,7,1,9}
b: {1,2,3}
false
a: {1,2,3}
true
b: {} a: {1,2,3}
false
a2: {1,2,3}
a3: {1,2,3}
a4: {1,2,3}
a5: {1,2,3}
a6: {1,2,3}
a7: {1,2,3}std::set<int> s {1,6};
vector<int> keys {2,7,3,0};
s.assign(begin(keys)+1,
end(keys));s: {1,6}
- 2
- 7
- 3
- 0
-
s: {0,3,7}Comparisons are value-based
comparing two associative containers compares the contained keys / key-value pairs
Equality comparison of all set/map types with
== and !=
two associative containers are equal, if their key(-value) content is equal
Lexicographical comparisons of ordered sets/maps with
<, <=, >, <=
std::set<int> s1 {1,2,7,8,9};
std::set<int> s2 {1,4,5};
bool s1_equals_s2 = (s1 == s2); // false
bool s1_uenqual_s2 = (s1 != s2); // true
bool s1_smaller_s2 = (s1 < s2); // true
bool s1_greater_s2 = (s1 > s2); // false
std::map<int,std::string> m1 {{1,"z"},{2,"f"},{7,"b"}};
std::map<int,std::string> m2 {{1,"a"},{3,"x"}};
bool m1_equals_m2 = (m1 == m2); // false
bool m1_unequal_m2 = (m1 != m2); // true
bool m1_smaller_m2 = (m1 < m2); // true
bool m1_greater_m2 = (m1 > m2); // falseMerge C++17
Integrate nodes from source into target without copying keys or values:
target.merge(source)
Runtime complexity: source.size() ⋅ log(target.size() + source.size()))
set<string> s {2,7};
set<string> t {1,5,8,9};
t.merge(s);s: {2,7}
t: {1,5,8,9}
s: { }
t: {1,2,5,7,8,9}(unordered sets & maps only)
Note that the exact number of hash buckets as a function of the number of inserted elements is not standardized and depends on the standard library implementation.
unordered_map<int,string> m { {6,"x"},{4,"a"},{7,"n"},{2,"z"} };
cout
<< m.size() // 4
<< m.bucket_count() // 5
<< m.bucket_size(1) // 1
<< m.bucket_size(2) // 0
<< m.bucket_size(3) // 2
<< m.load_factor(); // 0.6 = 3/5
unordered_map<int,string> m { {6,"x"},{4,"a"},{7,"n"},{2,"z"} };
// set to at least 7 buckets:
m.rehash(7);
cout
<< m.size() // 4
<< m.bucket_count() // 7
<< m.bucket_size(1) // 1
<< m.bucket_size(2) // 0
<< m.load_factor(); // 0.57 = 4/7
unordered_set<int> s {1,3,5,8,9};
cout << s.load_factor();
cout << s.max_load_factor();
// set new maximum:
s.max_load_factor(0.8);
s.rehash(10);
cout << s.load_factor();
1.0
1.0
might trigger rehash
force rehash
0.3846unordered_set<int> s {1,3,5,8,9};
// get bucket with key 3
const auto b = s.bucket(3);
// iterate over keys in bucket
for (auto i = s.begin(b); i != s.end(b); ++i) {
cout << *i;
}using set_t = std::map<double>;
set_t::size_type i = 0; // std::size_t
set_t::key_type{0} k = 0; // double
set_t::value_type{0} v = 0; // double
using map_t = std::map<int,std::string>;
map_t::key_type{0} k = 0; // int
map_t::mapped_type{0} m = 0; // string
map_t::value_type{0,"a"} v {1,"a"}; // pair<const int,string>Example: std::map
a and b are equal
if a == b
is true, i.e., their values are the same
a and b are equivalent
if !(a < b) && !(b < a)
is true, i.e., neither one is ordered before the other
The C++ standard library uses equivalence based on less than
for ordering objects (according to a strict weak ordering).
std::set<int,std::greater<>> s;
s.insert({1,5,3,2});
s.insert(4);
// get comparator copy
auto kc = s.key_comp();
cout << kc(4,2);C++98-11: std::greater<int>
s: {5,3,2,1}
s: {5,4,3,2,1}
true// custom key type
struct P2 {
P2(int x_, int y_): x{x_}, y{y_} {}
int x, y;
};
// comparator function object
struct P2_less {
constexpr bool operator ()
(P2 const& l, P2 const& r) const noexcept {
if (l.x < r.x) return true;
return (l.y < r.y);
}
};std::set<P2,P2_less> s;
s.insert( P2{1,2} );
s.emplace(3,4);s: { }
s: {{1,2}}
s: {{1,2},{3,4}}Alternative 2: Make Your Type Comparable
You should only do that
- if objects of your type can be ordered in a way that is
natural
& unambiguous - if you can at least provide a strict weak ordering
For more details, see:
Unordered containers take an additional type parameter:
set<Key,Hasher>,map<Key,Mapped,Hasher>, …
The type Hasher needs to provide a public member function
std::size_t operator() (Key const&) constwhich returns the hash value (= an unsigned index) for a given key.
The default is std::hash<Key>.
struct TM_hash {
// 32bit integer hash by T. Mueller
constexpr std::size_t
operator () (std::uint32_t k) const noexcept {
k = ((k >> 16) ^ k) * 0x45d9f3b;
k = ((k >> 16) ^ k) * 0x45d9f3b;
k = ((k >> 16) ^ k);
return k;
}
};
// make set with custom hasher
std::unordered_set<std::uint32_t,TM_hash> s;
…
// get copy of hasher from set
auto h = s.hasher();// custom key type
class A { … };
// hasher function class
struct A_hash {
std::size_t operator () (A const& k) const noexcept {
… // suitable hash function
}
};
// make set with custom hasher
std::unordered_set<A,A_hash> s;
…Cheat Sheets
std:: Associative Containers
(click for fullscreen view)
std::set<KeyType,Compare>
(click for fullscreen view)
std::map<KeyType,MappedType,KeyCompare>
(click for fullscreen view)
std::unordered_set<KeyT,Hash,KeyEqual>
(click for fullscreen view)
std::unordered_map<KeyT,MappedT,Hash,KeyEqual>
(click for fullscreen view)