map and unordered_map

Two associated containers that are formed with a key value and a mapped value, allowing for fast retrieval of elements based on their key.

• Map
  • map::at
  • map::begin
  • map::clear
  • map::count
  • map::emplace
  • map::empty
  • map::end
  • map::erase
  • map::find
  • map::insert
  • map::max_size
  • map::operator[]
  • map::operator=
  • map::rbegin
  • map::rend
  • map::size
  • map::swap
• Unordered_map
  • unordered_map::at
  • unordered_map::begin
  • unordered_map::bucket
  • unordered_map::bucket_count
  • unordered_map::bucket_size
  • unordered_map::clear
  • unordered_map::count
  • unordered_map::emplace
  • unordered_map::empty
  • unordered_map::end
  • unordered_map::erase
  • unordered_map::find
  • unordered_map::insert
  • unordered_map::load_factor
  • unordered_map::max_bucket_count
  • unordered_map::max_load_factor
  • unordered_map::max_size
  • unordered_map::operator[]
  • unordered_map::operator=
  • unordered_map::rehash
  • unordered_map::size
  • unordered_map::swap

Map

Elements in map are ordered internally in an AVL tree allowing for logarithmic lookups/insertions.

Member functions

map::at

mapped_type& at(const key_type& k);

Returns a reference to the mapped value at key value k, throws out_of_range if key does not exist in the map

map<string, int> mp;

mp["Mars"] = 68;
mp.at("Mars") = 688;

cout << mp.at("Mars") << endl

output

688

map::begin

iterator begin();

Returns an iterator to the first element in the map

map<char, int> mp;

mp['c'] = 100;
mp['b'] = 200;
mp['a'] = 300;

for (map<char, int>::iterator i = mp.begin(); i != mp.end(); ++i) {
	cout << i.first() << " - " << i.second() << endl;
}

output

a - 300
b - 200
c - 100

map::clear

void clear();

Removes all elements from the map and destroys them

map<int, int> mp;

mp[3] = 1;
mp[2] = 2;
mp[1] = 3;

for (map<int, int>::iterator i = mp.begin(); i != mp.end(); ++i) {
	cout << i.first() << " - " << i.second() << endl;
}

cout << endl;
mp.clear();

mp[10] = 20;

for (map<int, int>::iterator i = mp.begin(); i != mp.end(); ++i) {
	cout << i.first() << " - " << i.second() << endl;
}

output

1 - 3
2 - 2
3 - 1

10 - 20

map::count

int count(const key_type& k) const;

Returns the number of matches for key k, all map elements are unique so it will return either 0 or 1

map<char, int> mp;

mp['a'] = 101;
mp['c'] = 202;

cout << (mp.count('a') ? "a is in map" : "a not in map") << endl;
cout << (mp.count('b') ? "b is in map" : "b not in map") << endl;

output

a is in map
b not in map

map::emplace

std::pair<iterator, bool> emplace(key_type, mapped_type);

Inserts a new element if the key is unique much like map::insert

map<int, string> mp;

mp.emplace(5, "dog");
mp.emplace(3, "cat");
mp.emplace(10, "chicken");

for (map<int, string>::iterator i = mp.begin(); i != mp.end(); ++i) {
	cout << i.first() << " - " << i.second() << endl;
}

output

3 - cat
5 - dog
10 - chicken

map::empty

bool empty() const;

Returns whether map is empty

map<int, int> mp;

cout << (mp.empty() ? "empty" : "not empty") << endl;
mp[5] = 10;
cout << (mp.empty() ? "empty" : "not empty") << endl;

output

empty
not empty

map::end

iterator end();

Returns an iterator referring to the past-the-end element in the map

map<char, int> mp;

mp['c'] = 100;
mp['b'] = 200;
mp['a'] = 300;

for (map<char, int>::iterator i = mp.begin(); i != mp.end(); ++i) {
	cout << i.first() << " - " << i.second() << endl;
}

output

a - 300
b - 200
c - 100

map::erase

void erase(iterator position);
void erase(const key_type& k);

Removes an element from the map

map<char, int> mp;

mp['a'] = 1;
mp['b'] = 2;
mp['c'] = 3;
mp['d'] = 4;
map<char, int>::iterator it = mp.find('c');
mp.erase(it);
mp.erase('a');

for (it = mp.begin(); it != mp.end(); ++it) {
	cout << it.first() << " - " << it.second() << endl;
}

output

b - 2
d - 4

map::find

iterator find(const key_type& k);

Searches for an element with key k and returns an iterator to it, of none ar found returns iterator to map::end

map<int, int> mp;

mp[10] = 20;

mp.find(10).second() = 30;

cout << mp.find(10).second() << endl;

output

30

map::insert

void insert(std::pair<key_type, mapped_type>);

Inserts a new key value pair into the map if the key is unique

map<string, int> mp;

mp.insert(std::pair<string, int>("one", 1));
mp.insert(std::pair<string, int>("two", 2));

map::max_size

itn max_size() const;

Returns the maximum size of the map

map<string, int> mp;
cout << mp.max_size() << endl;

output

1000

map::operator[]

mapped_type& operator[](const key_type& k);

Returns the mapped value at the key k, if it does not exist it will create a new element with the key and default mapped_value

map<int, int> mp;

mp[0] = 10;
mp[1] = 11;
mp[2];
cout << mp[2] << endl;

for (map<int, int>::iterator i = mp.begin(); i != mp.end(); ++i) {
	cout << i.first() << " - " << i.second() << endl;
}

output

0
0 - 10
1 - 11
2 - 0

map::operator=

map& operator=(const map& x);

Assigns the contents of x into the map replacing its current content

map<int, int> mp, mp2;

mp[0] = 10;
mp[1] = 11;
mp[2];

mp2 = mp;
for (map<int, int>::iterator i = mp2.begin(); i != mp2.end(); ++i) {
	cout << i.first() << " - " << i.second() << endl;
}

output

0 - 10
1 - 11
2 - 0

map::rbegin

reverse_iterator rbegin();

Returns a reverse_iterator to the last element in the map

map<int, int> mp;

mp[0] = 10;
mp[1] = 11;
mp[2];

for (map<int, int>::reverse_iterator i = mp.rbegin(); i != mp.rend(); ++i) {
	cout << i.first() << " - " << i.second() << endl;
}

output

2 - 0
1 - 11
0 - 10

map::rend

reverse_iterator rend();

Returns a reverse_iterator to the past-the-end element of the map

map<int, int> mp;

mp[0] = 10;
mp[1] = 11;
mp[2];

for (map<int, int>::reverse_iterator i = mp.rbegin(); i != mp.rend(); ++i) {
	cout << i.first() << " - " << i.second() << endl;
}

output

2 - 0
1 - 11
0 - 10

map::size

int size() const;

Returns the size of the map

map<string, int> mp;

cout << mp.size() << endl;

mp["ball"] = 10;

cout << mp.size() << endl;

output

0
1

map::swap

void swap(map& x);

Exchanges the content of the map with the content of x

map<string, int> mp, mp2;

mp["dog"] = 1;
mp["cat"] = 2;

mp2["tiger"] = 10;

mp2.swap(mp);

cout << "mp" << endl;
for (map<string, int>::iterator i = mp.begin(); i != mp.end(); ++i) {
	cout << i.first() << " - " << i.second() << endl;
}

cout << "mp2" << endl;
for (map<string, int>::iterator i = mp2.begin(); i != mp2.end(); ++i) {
	cout << i.first() << " - " << i.second() << endl;
}

output

mp
tiger - 10
mp2
cat- 2
dog - 1

Unordered_map

Elements are not stored in any particular order, the key value is hashed and placed into buckets. This allows, on average, constant time lookups/insertions.

unordered_map::at

mapped_type& at(const key_type& k);

Returns a reference to the mapped value at key value k, throws out_of_range if key does not exist in the map

unordered_map<string, int> mp;

mp["Mars"] = 68;
mp.at("Mars") = 688;

cout << mp.at("Mars") << endl

output

688

unordered_map::begin

iterator begin();
local_iterator begin(int n);

Returns an iterator to the first element in the map or local iterator to the first element in a bucket

unordered_map<char, int> mp;

mp['c'] = 100;
mp['b'] = 200;
mp['a'] = 300;

for (unordered_map<char, int>::iterator i = mp.begin(); i != mp.end(); ++i) {
	cout << i.first() << " - " << i.second() << endl;
}
for (int i = 0; i < mp.bucket_count(); ++i) {
    cout << "bucket #" << i << ": ";
    for (unordered_map<char, int>::local_iterator l = mp.begin(i); l != mp.end(i); ++l){
        cout << l.second() << ", ";
    }
    cout << endl;
}

output

b - 200
c - 100
a - 300
bucket #0: 200, 
bucket #1: 100, 
bucket #2: 
bucket #3: 
bucket #4: 
bucket #5: 
bucket #6: 300,

unordered_map::bucket

int bucket(const key_type& k) const;

Returns the bucket that k would be in

unordered_map<int, int> mp;

cout << mp.bucket(10) << endl;

mp[10] = 10;

cout << mp.bucket(10) << endl;

output

0
1

unordered_map::bucket_count

int bucket_count() const;

Returns the number of buckets in the map

unordered_map<int, int> mp;
cout << "buckets: " << mp.bucket_count() << endl; 
cout << mp.bucket(10) << endl;

mp[10] = 10;

cout << "buckets: " << mp.bucket_count() << endl; 
cout << mp.bucket(10) << endl;

output

buckets: 1
0
buckets: 3
1

unordered_map::bucket_size

int bucket_size(int n) const;

Returns the size of the bucket n

unordered_map<int, int> mp;

mp[10] = 10;

cout << "size: " << mp.bucket_size(mp.bucket(10)) << endl;

output

size: 1

unordered_map::clear

void clear();

Removes all elements from the map and destroys them

unordered_map<char, int> mp;

mp['a'] = 5;
mp['b'] = 10;
mp['c'] = 20;

for (unordered_map<char, int>::iterator i = mp.begin(); i != mp.end(); ++i) {
    cout << i.first() << " - " << i.second() << endl;
}
mp.clear();
for (unordered_map<char, int>::iterator i = mp.begin(); i != mp.end(); ++i) {
    cout << i.first() << " - " << i.second() << endl;
}

output

b - 10
c - 20
a - 5

unordered_map::count

int count(const key_type& k) const;

Returns the number of matches for key k, all map elements are unique so it will return either 0 or 1

unordered_map<char, int> mp;

mp['a'] = 101;
mp['c'] = 202;

cout << (mp.count('a') ? "a is in map" : "a not in map") << endl;
cout << (mp.count('b') ? "b is in map" : "b not in map") << endl;

output

a is in map
b not in map

unordered_map::emplace

std::pair<iterator, bool> emplace(key_type, mapped_type);

Inserts a new element if the key is unique much like unordered_map::insert

unordered_map<int, string> mp;

mp.emplace(5, "dog");
mp.emplace(3, "cat");
mp.emplace(10, "chicken");

for (unordered_map<int, string>::iterator i = mp.begin(); i != mp.end(); ++i) {
	cout << i.first() << " - " << i.second() << endl;
}

output

3 - cat
10 - chicken
5 - dog

unordered_map::empty

bool empty() const;

Returns whether map is empty

unordered_map<int, int> mp;

cout << (mp.empty() ? "empty" : "not empty") << endl;
mp[5] = 10;
cout << (mp.empty() ? "empty" : "not empty") << endl;

output

empty
not empty

unordered_map::end

iterator end();
local_iterator end(int n);

Returns an iterator to the last element in the map or local iterator to the last element in a bucket

unordered_map<char, int> mp;

mp['c'] = 100;
mp['b'] = 200;
mp['a'] = 300;

for (unordered_map<char, int>::iterator i = mp.begin(); i != mp.end(); ++i) {
	cout << i.first() << " - " << i.second() << endl;
}
for (int i = 0; i < mp.bucket_count(); ++i) {
    cout << "bucket #" << i << ": ";
    for (unordered_map<char, int>::local_iterator l = mp.begin(i); l != mp.end(i); ++l){
        cout << l.second() << ", ";
    }
    cout << endl;
}

output

b - 200
c - 100
a - 300
bucket #0: 200, 
bucket #1: 100, 
bucket #2: 
bucket #3: 
bucket #4: 
bucket #5: 
bucket #6: 300,

unordered_map::erase

iterator erase(iterator position);
iterator erase(const key_type k);

Removes an element from the map

unordered_map<char, int> mp;

mp['a'] = 1;
mp['b'] = 2;
mp['c'] = 3;
mp['d'] = 4;
map<char, int>::iterator it = mp.find('c');
mp.erase(it);
mp.erase('a');

for (it = mp.begin(); it != mp.end(); ++it) {
	cout << it.first() << " - " << it.second() << endl;
}

output

b - 2
d - 4

unordered_map::find

iterator find(const key_type& k);

Searches for an element with key k and returns an iterator to it, of none ar found returns iterator to unordered_map::end

unordered_map<int, int> mp;

mp[10] = 20;

mp.find(10).second() = 30;

cout << mp.find(10).second() << endl;

output

30

unordered_map::insert

std::pair<iterator, bool> insert(std::pair<key_type, mapped_type>);

Inserts a new key value pair into the map if the key is unique

unordered_map<string, int> mp;

mp.insert(std::pair<string, int>("one", 1));
mp.insert(std::pair<string, int>("two", 2));

unordered_map::load_factor

double load_factor() const;

Returns the current load factor load_factor = size / bucket_count

unordered_map<int, int> mp;

mp[10] = 10;

cout << mp.load_factor() << endl;

output

.333333

unordered_map::max_bucket_count

int max_bucket_count() const;

Returns the maximum number of buckets the map can have

unordered_map<int, int> mp;

cout << mp.max_bucket_count() << endl;

output

357913941

unordered_map::max_load_factor

double max_load_factor() const;
void max_load_factor(double z);

Set or get the max_load_factor

unordered_map<int, int> mp;

cout << mp.max_load_factor() << endl;

mp.max_load_factor(.80);

cout << mp.max_load_factor() << endl;

output

.75
.8

unordered_map::max_size

int max_size() const;

Returns the maximum number of elements that the map can store

unordered_map<int, int> mp;

cout << mp.max_size() << endl;

output

357913941

unordered_map::operator[]

mapped_type& operator[](const key_type& k);

Returns the mapped value at the key k, if it does not exist it will create a new element with the key and default mapped_value

unordered_map<int, int> mp;

mp[0] = 10;
mp[1] = 11;
mp[2];
cout << mp[2] << endl;

for (unordered_map<int, int>::iterator i = mp.begin(); i != mp.end(); ++i) {
	cout << i.first() << " - " << i.second() << endl;
}

output

0
0 - 10
1 - 11
2 - 0

unordered_map::operator=

unordered_map& operator=( const unordered_map& x);

Assigns the contents of x into the map replacing its current content

unordered_map<int, int> mp, mp2;

mp[0] = 10;
mp[1] = 11;
mp[2];

mp2 = mp;
for (unordered_map<int, int>::iterator i = mp2.begin(); i != mp2.end(); ++i) {
	cout << i.first() << " - " << i.second() << endl;
}

output

0 - 10
1 - 11
2 - 0

unordered_map::rehash

void rehash(int n);

Will rehash the container to nextPrime(n) increasing the amount of buckets, will remap all existing elements to their new buckets nextPrime(n) worst case: (2n - 1)/2

unordered_map<int, int> mp;

mp.rehash(30);

cout << mp.bucket_count() << endl;

output

31

unordered_map::size

int size() const;

Returns the number of elements in the map

unordered_map<int, int> mp;

cout << mp.size() << endl;

mp[10] = 10;
mp[20] = 20;
mp[30] = 30;

cout << mp.size() << endl;

output

0
3

unordered_map::swap

void swap(unordered_map& x);

Exchanges the content of the map with the content of x

unordered_map<string, int> mp, mp2;

mp["dog"] = 1;
mp["cat"] = 2;

mp2["tiger"] = 10;

mp2.swap(mp);

cout << "mp" << endl;
for (unordered_map<string, int>::iterator i = mp.begin(); i != mp.end(); ++i) {
	cout << i.first() << " - " << i.second() << endl;
}

cout << "mp2" << endl;
for (unordered_map<string, int>::iterator i = mp2.begin(); i != mp2.end(); ++i) {
	cout << i.first() << " - " << i.second() << endl;
}

output

mp
tiger - 10
mp2
cat - 2
dog - 1