map (C++)


map (C++)

The class template std::map<Key, Data, Compare, Alloc> is a standard C++ container. It is a sorted associative array of unique keys and associated data.[1] The types of key and data may differ, and the elements of the map are internally sorted from lowest to highest key value. Since each key value is unique, if an object is inserted with an already existing key, the object already present in the map does not change.[1] A variation on the map, called the multimap, allows duplicate keys.

Iterators and references are not invalidated by insert and erase operations, except for iterators and references to erased elements. The usual implementation is a self-balancing binary search tree (but any other data structure that respects the complexity constraints can be used, like a skip list).

Contents

Design

Characteristics

  • Each element has a unique key
  • Each element is composed of a key and a mapped value
  • Elements follow a strict weak ordering[1]

Performance

Maps are designed to be especially efficient in accessing its elements by their key, as opposed to sequence containers which are more efficient in accessing elements by their position.[1]

The asymptotic complexity of the operations that can be applied to maps are as follows:

Operation Complexity
Searching for an element O(log n)
Inserting a new element O(log n)
Incrementing/decrementing an iterator O(log n)
Removing a single map element O(log n)
Copying an entire map [1] O(n)
Iterating through all elements O(n)

Overview of functions

    • map::map (constructor) - Constructs the map from variety of sources.
    • map::~map (destructor) - Destructs the map and the contained elements
    • map::operator= - Assigns values to the map
    • map::get_allocator - Returns the allocator used to allocate memory for the elements
  • Iterators
    • map::begin - Returns an iterator to the beginning of the map
    • map::end - Returns an iterator to the end of the map
    • map::rbegin - Returns a reverse iterator to the reverse beginning of the map
    • map::rend - Returns a reverse iterator to the reverse end of the map
  • Capacity
    • map::empty - Checks whether the map is empty
    • map::size - Returns the number of elements in the map.
    • map::max_size - Returns the maximum possible number of elements in the map.
  • Modifiers
    • map::clear - Clears the contents
    • map::insert - Inserts elements
    • map::emplace (C++11) - Constructs elements in-place
    • map::emplace_hint (C++11) - Constructs elements in-place using a hint
    • map::erase - Erases elements
    • map::swap - Swaps the contents with another map
  • Lookup
    • map::count - Returns the number of elements matching specific key
    • map::find - Finds an element with specific key
    • map::equal_range - Returns a range of elements matching specific key
    • map::lower_bound - Returns an iterator to the first element not less than the given value
    • map::upper_bound - Returns an iterator to the first element greater than a certain value
  • Observers
    • map::key_comp - Returns key comparison function.
    • map::value_comp - Returns value comparison function.

Usage

The map is declared in this format:

map <key_type, value_type [, comparing_option [, memory_allocator] ] > map_name

The following code demonstrates how to use the map<string, int> to count occurrences of words. It uses the word as the key and the count as the value.

#include <iostream>
#include <string>
#include <map>
 
int main()
{
    std::map<std::string, int> wordcounts;
    std::string s;
 
    while (std::cin >> s && s != "end")
        ++wordcounts[s];
 
    while (std::cin >> s && s != "end")
        std::cout << s << ' ' << wordcounts[s] << '\n';
}

When executed, the user first types a series of words separated by spaces, and a word "end" to signify the end of input; then the user can input words to query how many times each word occurred in the previous series.

The above example also demonstrates that the operator [] inserts new objects (using the default constructor) in the map if there isn't one associated with the key. So integral types are zero-initialized, strings are initialized to empty strings, etc.

The following example illustrates inserting elements into a map using the insert function and searching for a key using a map iterator and the find function:

#include <iostream>
#include <map>
#include <utility> // make_pair
 
int main()
{
    typedef std::map<char, int> MapType;
    MapType my_map;
 
    // insert elements using insert function
    my_map.insert(std::pair<char, int>('a', 1));
    my_map.insert(std::pair<char, int>('b', 2));
    my_map.insert(std::pair<char, int>('c', 3));
    my_map.insert(MapType::value_type('d', 4)); // all standard containers provide this typedef
    my_map.insert(std::make_pair('e', 5));      // can also use the utility function make_pair
    my_map.insert({'f', 6});                    // using C++11 initializer list
 
    //map keys are sorted automatically from lower to higher. 
    //So, my_map.begin() points to the lowest key value not the key which was inserted first.
    MapType::iterator iter = my_map.begin();
 
    // erase the first element using the erase function
    my_map.erase(iter);
 
    // output the size of the map
    std::cout << "Size of my_map: " << my_map.size() << '\n';
 
    std::cout << "Enter a key to search for: ";
    char c;
    std::cin >> c;
 
    // find will return an iterator to the matching element if it is found
    // or to the end of the map if the key is not found
    iter = my_map.find(c);
    if (iter != my_map.end() ) 
        std::cout << "Value is: " << iter->second << '\n';
    else
        std::cout << "Key is not in my_map" << '\n';
 
    // clear the entries in the map
    my_map.clear();
}

In the above example, five elements are entered using the insertion function, and then the first element is deleted. Then, the size of the map is output. Next, the user is prompted for a key to search for. Using the iterator, the find function searches for an element with the given key. If it finds the key, the program prints the element's value. If it does not find it, an iterator to the end of the map is returned and it outputs that the key could not be found. Finally all the elements in the tree are erased.

Iterators

Maps may use iterators to point to specific elements in the container. An iterator can access both the key and the mapped value of an element:[1]

map<Key,T>::iterator it; // declares a map iterator
it->first;               // the key value 
it->second;              // the mapped value
(*it);                   // the "element value", which is of type:  pair<const Key,T>

Below is an example of looping through a map to display all keys and values using iterators:

#include <iostream>
#include <string>
#include <map>
 
int main()
{
    typedef std::map <std::string, int> MapType;
    MapType data;
 
    // let's declare some initial values to this map
    data["Bobs score"] = 10;
    data["Martys score"] = 15;
    data["Mehmets score"] = 34;
    data["Rockys score"] = 22;
    data["Rockys score"] = 23;  /*overwrites the 22 as keys are unique */
 
    // Iterate over the map and print out all key/value pairs.
    // Using a const_iterator since we are not going to change the values.
    MapType::const_iterator end = data.end(); 
    for (MapType::const_iterator it = data.begin(); it != end; ++it) {
        std::cout << "Who(key = first): " << it->first;
        std::cout << " Score(value = second): " << it->second << '\n';
    }
 
    return 0;
}

This will output the keys and values of the entire map, sorted by keys.

Member types

What follows is a list of the member types of the map container:[1]

Member type Definition
key_type Key
mapped_type T
value_type pair<const Key,T>
key_compare Compare
value_compare Nested class to compare elements
allocator_type Allocator
reference Allocator::reference
const_reference Allocator::const_reference
iterator Bidirectional iterator
const_iterator Constant bidirectional iterator
size_type Unsigned integral type (usually same as size_t)
difference_type Signed integral type (usually same as ptrdiff_t)
pointer Allocator::pointer
const_pointer Allocator::const_pointer
reverse_iterator reverse_iterator<iterator>
const_reverse_iterator reverse_iterator<const_iterator>

Caveats

Because map requires a strict weak ordering, a map keyed on floating-point numbers can produce undefined behavior if any of the keys are not a numbers (NaN), since any comparison operation involving a NaN yields to false.

See also

References

External links


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Map — /map/, n. Walter, c1140 1209?, Welsh ecclesiastic, poet, and satirist. Also, Mapes /mayps, may peez/. * * * I Graphic representation, drawn to scale and usually on a flat surface, of features usually geographic, geologic, or geopolitical of an… …   Universalium

  • Map — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. {{{image}}}   Sigles d une seule lettre   Sigles de deux lettres > Sigles de trois lettres …   Wikipédia en Français

  • map — Ⅰ. map UK US /mæp/ noun [C] GRAPHS & CHARTS ► a drawing of the Earth s surface, or part of it, showing things such as the shape and position of countries, political borders, towns, rivers, etc.: on a map »Many of these students could not even… …   Financial and business terms

  • map — ► NOUN 1) a flat diagram of an area of land or sea showing physical features, cities, roads, etc. 2) a diagram or collection of data showing the arrangement, distribution, or sequence of something. ► VERB (mapped, mapping) 1) represent or record… …   English terms dictionary

  • map — [map] n. [ML mappa (mundi), map (of the world) < L mappa, napkin, cloth (on which maps were painted): said (by QUINTILIAN) to be of Punic orig.; prob. < TalmudHeb mappa < * manpa, contr. < menafa, a fluttering banner] 1. a drawing or… …   English World dictionary

  • Map — Map, v. t. [imp. & p. p. {Mapped}; p. pr. & vb. n. {Mapping}.] To represent by a map; often with out; as, to survey and map, or map out, a county. Hence, figuratively: To represent or indicate systematically and clearly; to sketch; to plan; as,… …   The Collaborative International Dictionary of English

  • Map — (m[a^]p), n. [From F. mappe, in mappemonde map of the world, fr. L. mappa napkin, signal cloth; a Punic word. Cf. {Apron}, {Napkin}, {Nappe}.] 1. A representation of the surface of the earth, or of some portion of it, showing the relative… …   The Collaborative International Dictionary of English

  • MAP — se refiere a: MAPFRE, empresa española de seguros cuyo ticker en la Bolsa de Madrid es MAP. Médico de atención primaria: sinónimo de médico de cabecera. Ministerio de Administraciones Públicas (España). Museo de Arte Precolombino (Cusco, Perú).… …   Wikipedia Español

  • MAP — 〈EDV; Abk. für engl.〉 Manufacturing Automation Protocol, Modell für die Datenübertragung zw. Rechnern verschiedener Arbeitsbereiche [engl., „automatisierte Protokollherstellung“] * * * MAP   [Abk. für Manufacturing Automation Protocol, dt.… …   Universal-Lexikon

  • .map — map,   Erweiterung für eine sog. Map Datei, d. h. für eine Datei, welche die Koordinaten von verweissensitiven (interaktiven) Grafiken sowie die zugeordneten URL Adressen enthält …   Universal-Lexikon

  • Map — [map] Walter 1140? 1209?; Welsh poet & satirist: also, Latin name, Mapes [māps, mā′pēz΄] …   English World dictionary