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. You

Implementation in Python

In Python, the map is just a dictionary.

a = {}
a['hi'] = True