12.5map
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) calledmap:
In other contexts, amapis known as an associative array or a dictionary.
The standard-librarymapis a container of pairs of values optimized for lookup and insertion. We can use the same initializer as forvectorandlist(§12.2, §12.3):
mapphone_book { {"David Hume",123456}, {"Karl Popper",234567}, {"Bertrand Arthur William Russell",345678} };
When indexed by a value of its first type (called thekey), amapreturns the corresponding value of the second type (called thevalueor themapped type). For example:
int get_number(const string& s) { return phone_book[s]; }
In other words, subscripting amapis essentially the lookup we calledget_number(). If akeyisn’t found, it is entered into themapwith a default value for itsvalue. The default value for an integer type is0and 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 usefind()andinsert()(§12.8) instead of[ ].