Pisanie kodu do znajdowania nazwiska na liście par (nazwisko, numer) jest dość żmudne. Ponadto liniowe wyszukiwanie w większych listach jest dalekie od optymalnego. Dlatego w bibliotece standardowej dostępne jest drzewo poszukiwań (czerwono-czarne) o nazwie map:
Mapa czasami występuje też pod nazwami tablica asocjacyjna i słownik. Jest zaimplementowana jako zrównoważone drzewo binarne. Mapa w bibliotece standardowej jest kontenerem par wartości zoptymalizowanym pod kątem wyszukiwania. Przy tworzeniu mapy można używać takiego samego inicjatora jak w przypadku wektora i listy:
map phone_book {
{„Jan Nowak”,32344},
{„Ewa Kowalska”,32432},
{„Artur Rbik”,32342}
};
Mapa jest indeksowana wg wartości swojego pierwszego typu (zwanego kluczem) i zwraca odpowiednią wartość drugiego typu (zwanego wartością albo typem mapowanym). Na przykład:
int get_number(const string& s)
{
return phone_book[s];
}
Indeksowanie mapy to w istocie operacja wyszukiwania, jaką wykonywaliśmy wcześniej przy użyciu funkcji get_number(). Jeżeli klucz nie zostanie znaleziony, jest wstawiany do mapy z domyślną wartością. Wartość domyślna dla typu całkowitoliczbowego to 0. Wartość, którą akurat wybrałem, reprezentuje niepoprawny numer telefoniczny. Aby uniknąć wprowadzania niepoprawnych numerów telefonicznych do książki, można zamiast operatora [] użyć funkcji find() i insert()).