Map (C++ container)
From Wikipedia, the free encyclopedia
- The correct title of this article is map. The initial letter is shown capitalized due to technical restrictions.
| C++ Standard Library |
|---|
| ios |
| iostream |
| iomanip |
| map |
| fstream |
| C Standard Library |
| cassert |
| cctype |
| cerrno |
| cfloat |
| cmath |
| cstdio |
| cstdlib |
| ctime |
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 O(log(n)), 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).
[edit] 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:
#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;
}
When executed, the user first types in each name which is present, and a word "end" at the end of input; then for each name queried, "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.
