Jump to content

Map (C++): Difference between revisions

Add links
From Wikipedia, the free encyclopedia
Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
Tag: Redirect target changed
 
(45 intermediate revisions by 20 users not shown)
Line 1: Line 1:
#REDIRECT [[Associative containers (C++)]]
{{lowercase|map (C++ container)}}
{{C++ Standard library}}


{{Redirect category shell|
The class template <code>std::'''map'''<Key, Data, Compare, Alloc></code> is a standard [[C++]] [[Standard Template Library#Containers|container]]. It is a sorted [[associative array]] of unique keys and associated data.<ref>[http://uw713doc.sco.com/en/SDK_c++/_Intro_map.html Introduction<!-- Bot generated title -->]</ref> 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 is not changed in any way.<ref name="cplusplus">[http://www.cplusplus.com/reference/stl/map/ map - C++ Reference<!-- Bot generated title -->]</ref> A variation on the map, called the [[multimap]], allows duplicate keys.
{{R from merge}}

}}
Iterators are not invalidated by insert and erase operations which don't remove the object to which the iterator points. 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]]).

==Main characteristics==

* Each element has a unique key
* Each element is composed of a key and a mapped value
* Elements follow a strict weak ordering<ref name="cplusplus" />

==Performance==
The time it takes to perform the following list of tasks, can be expressed as: ''O(log n)'' <br />
''Note that this performance cost applies to each task individually.''

* Searching for an element
* Inserting a new element
* Incrementing/decrementing an iterator
* Iterating through all elements
* Removing a single map element
* Copying an entire map <ref>[http://uw713doc.sco.com/en/SDK_c++/_Perform_map.html Performance<!-- Bot generated title -->]</ref>

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 (although maps are able to directly access elements with the <code>operator[]</code> ).<ref name="cplusplus" />

==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 <code>map<string, int></code> to count occurrences of words. It uses the word as the key and the count as the value.
<source lang="cpp">
#include <iostream>
#include <string>
#include <map>

using namespace std;

int main()
{
map<string, int> wordcounts;
string s;

while (cin >> s && s != "end")
++wordcounts[s];

while (cin >> s && s != "end")
cout << s << ' ' << wordcounts[s] << '\n';
}
</source>

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:

<source lang="cpp">
#include <iostream>
#include <map>
#include <utility> // make_pair
using namespace std;

int main()
{
typedef map<char, int> mapType;
mapType myMap;

// insert elements using insert function
myMap.insert(pair<char, int>('a', 1));
myMap.insert(pair<char, int>('b', 2));
myMap.insert(pair<char, int>('c', 3));
myMap.insert(mapType::value_type('d', 4)); // all standard containers provide this typedef
myMap.insert(make_pair('e', 5)); // can also use the utility function make_pair

// erase the first element using the erase function
mapType::iterator iter = myMap.begin();
myMap.erase(iter);

// output the size of the map
cout << "Size of myMap: " << myMap.size() << '\n';

cout << "Enter a key to search for: ";
char c;
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 = myMap.find(c);
if( iter != myMap.end() )
cout << "Value is: " << iter->second << '\n';
else
cout << "Key is not in myMap" << '\n';

// clear the entries in the map
myMap.clear();
}
</source>

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:<ref name="cplusplus" />

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

Below is an example of looping through a map to display all keys and values using iterators:
<source lang="cpp">
#include <iostream>
#include <string>
#include <map>

using namespace std;

int main()
{
typedef map<string, int> mapType;
mapType data;
// let's declare some initial values to this map
data["BobsScore"] = 10;
data["MartysScore"] = 15;
data["MehmetsScore"] = 34;
data["RockysScore"] = 22;
data["RockysScore"] = 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.
for(mapType::const_iterator it = data.begin(); it != data.end(); ++it)
{
cout << "Who(key = first): " << it->first;
cout << " Score(value = second): " << it->second << '\n';
}

return 0;
}
</source>

This will output the keys and values of the entire map.

== Member functions ==
What follows is a list of the public member functions in the <code>map</code> library:<ref name="cplusplus" />

{| class="wikitable"
|-
! Name||Description
|-
| <code>(constructor)</code> || Construct a map object
|-
| <code>(destructor)</code> || Destroys map object
|-
| <code>operator=</code> || Copy content of container
|-
| colspan=2 align=center| '''Iterators:'''
|-
| <code>begin</code> || Return iterator to beginning of map
|-
| <code>end</code> || Return iterator to end of map
|-
| <code>rbegin</code> || Return reverse iterator to reverse beginning (end)
|-
| <code>rend</code> || Return reverse iterator to reverse end (beginning)
|-
| colspan=2 align=center| '''Capacity:'''
|-
| <code>empty</code> || Test whether map is empty or not
|-
| <code>size</code> || Return container size of map
|-
| <code>max_size</code> || Return maximum size of map
|-
| colspan=2 align=center| '''Element access:'''
|-
| <code>operator[]</code> || Access element
|-
| colspan=2 align=center| '''Modifiers:'''
|-
| <code>insert</code> || Insert element
|-
| <code>erase</code> || Erase element
|-
| <code>swap</code> || Swap contents
|-
| <code>clear</code> || Clear contents
|-
| colspan=2 align=center| '''Observers:'''
|-
| <code>key_comp</code> || Return key comparison object
|-
| <code>value_comp</code> || Return value comparison object
|-
| colspan=2 align=center| '''Operations:'''
|-
| <code>find</code> || Return iterator to element
|-
| <code>count</code> || Count elements with a specific key
|-
| <code>lower_bound</code> || Return iterator to the lower bound
|-
| <code>upper_bound</code> || Return iterator to the upper bound
|-
| <code>equal_range</code> || Return range of equal elements
|-
| colspan=2 align=center| '''Allocator:'''
|-
| <code>get_allocator</code> || Return allocator
|}

== Member types ==
What follows is a list of the member types of the <code>map</code> container:<ref name="cplusplus" />

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

== 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 number|NaN]]s.

==References==
{{reflist}}

==See also==
*[[Standard_Template_Library#Containers|Standard Template Library containers]]
*[[unordered_map (C++ class)|unordered_map]]

[[Category:C++ standard library]]
[[Category:Articles with example C++ code]]

Latest revision as of 21:56, 13 October 2023

Redirect to:

Retrieved from "https://en.wikipedia.org/enwiki/w/index.php?title=Map_(C%2B%2B)&oldid=1180007632"