Abstract Data Type

Map

A map is a generalized array that consists of key-value pairs. A dictionary is considered to be a Abstract Data Type.

How to implement

Built-in Implementation

C++

Don’t use the square brackets (yet), use the other built-in functions that you can check here: https://en.cppreference.com/w/cpp/container/map insert something → map::emplace get something → map::at

map vs. unordered_map

	map	unordered_map
Ordering	increasing order (by default)	no ordering
Implementation	Self-Balancing Binary Search Tree	Hash Table
search time	$\log (n)$	$O(1)$ $\to$ Average, $O(n)$ $\to$ Worst Case
Insertion time	$\log (n)$ + Rebalance	Same as search
Deletion time	$\log (n)$ + Rebalance	Same as search

map<string,int> m;
m["monkey"] = 4;
m["banana"] = 3;
m["harpsichord"] = 9;
cout << m["banana"] << "\n"; // 3

If the value of a key is requested but the map does not contain it, the key is automatically added to the map with a default value.

map<string,int> m;
cout << m["aybabtu"] << "\n"; // 0

The function count checks if a key exists in a map:

if (m.count("aybabtu")) {
	// key exists
}

The following code prints all the keys and values in a map:

for (auto x : m) {
	cout << x.first << " " << x.second << "\n";
}

Delete from a map

 std::map<char,int> mymap;
 std::map<char,int>::iterator it;
 
// insert some values:
mymap['a']=10;
mymap['b']=20;
mymap['c']=30;
mymap['d']=40;
mymap['e']=50;
mymap['f']=60;
 
it=mymap.find('b');
mymap.erase (it);                   // erasing by iterator
 
mymap.erase ('c');                  // erasing by key
 
it=mymap.find ('e');
mymap.erase ( it, mymap.end() );    // erasing by range

Some other small insights

Recently discovered that you don’t need to do this when counting.

// NOT NEEDED
if (m.count(x)) {
	m[x]++;
} else {
	m[x] = 1;
}
 
// DO THIS INSTEAD
m[x]++;

I keep forgetting this for time to time

unordered_map<pair<int,int> int> does not exist. The hash function for a pair<int,int> is not defined.

Implementation in Python

Unordered Map

In Python, the map is just a dictionary. This is an unordered map

a = {}
a['hi'] = 5
 
# Iterate over keys
for key in unordered_map:
    print(key)
 
# Iterate over key-value pairs
for key, value in unordered_map.items():
    print(f"{key}: {value}")

Ordered Map

Use SortedDict

from sortedcontainers import SortedDict
 
sorted_map = SortedDict()
sorted_map['b'] = 2
sorted_map['a'] = 1
sorted_map['c'] = 3
 
print(sorted_map)  # Output: SortedDict({'a': 1, 'b': 2, 'c': 3})
 
# Iterate over keys
for key in sorted_map:
    print(key)
 
# Iterate over key-value pairs
for key, value in sorted_map.items():
    print(f"{key}: {value}")

Competitive Programming

The hash function can be reverse engineered to produce lots of hash collisions. https://codeforces.com/blog/entry/62393

• Therefore, preferable to use a regular map