This chapter is from the book
This chapter is from the book
This chapter is from the book
12.5 map
Writing code to look up a name in a list of (name,number) pairs is quite tedious. In addition, a linear search is inefficient for all but the shortest lists. The standard library offers a balanced binary search tree (usually a red-black tree) called map:
)
In other contexts, a map is known as an associative array or a dictionary.
The standard-library map is a container of pairs of values optimized for lookup and insertion. We can use the same initializer as for vector and list (§12.2, §12.3):
map<string,int> phone_book {
{"David Hume",123456},
{"Karl Popper",234567},
{"Bertrand Arthur William Russell",345678}
};
When indexed by a value of its first type (called the key), a map returns the corresponding value of the second type (called the value or the mapped type). For example:
int get_number(const string& s)
{
return phone_book[s];
}
In other words, subscripting a map is essentially the lookup we called get_number(). If a key isn’t found, it is entered into the map with a default value for its value. The default value for an integer type is 0 and that just happens to be a reasonable value to represent an invalid telephone number.
If we wanted to avoid entering invalid numbers into our phone book, we could use find() and insert() (§12.8) instead of [ ].