Skip to content

Associative Containers

Associative Containers

Associative containers implement sorted data structures that can be quickly searched (O(log n) complexity. They are usually implemented as binary trees.

  • set: collection of unique keys, sorted by keys
  • map: collection of key-value pairs, sorted by keys, keys are unique
  • multiset: collection of keys, sorted by keys
  • multimap: collection of key-value pairs, sorted by keys

Unordered associative containers implement unsorted (hashed) data structures that can be quickly searched (O(1) amortized, O(n) worst-case complexity). They are usually implemented as hash tables.

  • unordered_set (C++11): collection of unique keys, hashed by keys
  • unordered_map (C++11): collection of key-value pairs, hashed by keys, keys are unique
  • unordered_multiset (C++11): collection of keys, hashed by keys
  • unordered_multimap (C++11): collection of key-value pairs, hashed by keys
1
2
3
4
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

1
2
std::set<int> a = {2, 3, 1, 5, 4};
std::unordered_set<int> a2 = {1, 2, 3, 4, 5};

1
2
3
4
std::map<std::string, double> m;
m["PI"] = 3.14;
m["ZERO"] = 0.0;
m["IRPF"] = 0.15;

1
2
3
4
std::map<std::string, double> m;
m["PI"] = 3.14;
m["ZERO"] = 0.0;
m["IRPF"] = 0.15;

1
2
3
4
std::cout << a.size() << '\n';
std::cout << a2.size() << '\n';
std::cout << m.size() << '\n';
std::cout << m2.size() << '\n';

1
2
a.insert(8);
a2.insert(8);

1
2
m["hundred"] = 100.0;
m2["hundred"] = 100.0;

1
2
m["hundred"] = 100.0;
m2["hundred"] = 100.0;

1
2
3
4
a.erase(2);
a2.erase(2);
m.erase("thousand");
m2.erase("thousand");

Share Snippets