Map (C++ container) | Present on
{{C++ Standard library}}
The class std::map<Key, Data, Compare, Alloc> is a standard [[C++]] container. It is a sorted associative array that maps objects of type Key to objects of type Data. The key values are unique; if an object is inserted with an already existing key, the object already present in the map is replaced by the new one.
The required time to randomly access each element is <math>O(\log(n))</math>, and the iterators are not invalidated by insert and erase operations (that don’t remove the object to which the iterator points); thus 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).
Internally, the elements in the map are sorted from lower to higher key value.
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 to store attendance records:
<source lang=”cpp”>
- include <iostream>
- include <string>
- include <map>
using namespace std;
int main()
{
cout.setf(ios::boolalpha); //make boolean variables output as "true" or "false" map<string, bool> present; string s;
while (cin >> s && s != "end")
present[s] = true;
while (cin >> s && s != "end")
cout << s << ' ' << present[s] << endl;
}
</source>
When executed, the user first types in each name which is present, and a word “end” at the end of input; then the user can query for a name and “true” would be printed if the person queried was present, and “false” if not.
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.
See also
- Standard Template Library containers
[[Category:C++ standard library]]
[[Category:Articles with example C++ code]]