[C++]: Use of associative container map

Table of Contents

1. Introduction to map

2. Initialization of map

2.1. Method 1

2.2. Method 2

2.3. Method 3

3. Comparison of map sorting (functor)

4. Use of common built-in functions of map

4.1 Iterator

4.2 Capacity

4.3 Element access

3.4Modifier

3.5 Operation

5. Map traversal (iteration)

5.1 Iterator

5.2 Scope for

Summarize

1. Introduction to map

  • Map is an associative container that stores elements composed of key and value in a specific order (compared by key).
  • In a map, the key is usually used to sort and uniquely identify elements, while the value stores the content associated with this key. The types of key and value may be different, and inside the map, key and value are bound together through the member type value_type, and their alias name is pair: typedef pair value_type;
  • Internally, the elements in the map are always sorted according to the key value.
  • Accessing individual elements by key value in map is usually slower than unordered_map containers, but map allows direct iteration of elements according to order (that is, when iterating over elements in map, an ordered sequence can be obtained).
  • Map supports subscript accessors, that is, by putting the key in [ ], you can find the value corresponding to the key.
  • Amap is usually implemented as a binary search tree (more precisely: balanced binary search tree (red-black tree)).

  • key: the type of key in the key-value pair
  • T: The type of value in the key-value pair
  • Compare: The type of comparator. The elements in the map are compared according to key. By default, they are compared according to less than. Generally (built-in type elements) this parameter does not need to be passed. If it cannot be compared (self Define type), the user needs to explicitly pass the comparison rules (usually passed according to function pointers or functors)
  • Alloc: Apply for the underlying space through the space configurator, and do not need to be passed by the user, unless the user does not want to use the Space Configurator provided by the standard library

2. Initialization of map

2.1, Method 1 

 map<int, int> m; //Construct an empty one

2.2, Method 2 

map<char, int> m;
m['a'] = 10;
m['b'] = 30;
m['c'] = 50;
m['d'] = 70;
map<char, int> m1(m); //copy construction

2.3, Method 3

map<char, int> m;
m['a'] = 10;
m['b'] = 30;
m['c'] = 50;
m['d'] = 70;
map<char, int> m2(m.begin(), m.end()); //Iterator construction

3. Comparison of map sorting (functor)

struct classcomp
{
bool operator() (const char & amp; lhs, const char & amp; rhs) const
{
return lhs > rhs;
}
};
map<char, int, classcomp> m3; // class as Compare

4. Use of common built-in functions of map

4.1 Iterator

map<int,int> v;
//Iterators(iterator)
v.begin(); //Get the position of the first number
v.end(); //Get the position of the last number
v.rbegin(); //Get the position of the last number
v.rend(); //Get the position of the first number

4.2 capacity

map<int,int> v;
    //Capacity(capacity)
v.size(); //Get the number of v data
v.max_size(); //Returns the maximum length that the string can reach
v.empty(); //Determine whether v is empty

4.3 Element Access

 map<char, int> m;
m['a'] = 10; //Similar to array subscript, but uses key to find value
cout << m['a'] <<endl;
    The principle of /*operator[] is:
    Use <key, T()> to construct a key-value pair, and then call the insert() function to insert the key-value pair into the map.
    If the key already exists, the insertion fails and the insert function returns the iterator at the location of the key.
    If the key does not exist, the insertion is successful, and the insert function returns the iterator at the location of the newly inserted element.
    The operator[] function finally returns the value in the key-value pair returned by insert*/

3.4 Modifier

map<char, int> m;
map<char, int> m1;
m['a'] = 10;
m['b'] = 30;
m['c'] = 50;
m['d'] = 70;
m.insert(make_pair('e', 88)); //Insert element

map<char, int>::iterator it = m.find('b');
m.erase(it); // erasing by iterator
m.erase('c'); // erasing by key
it = m.find('d');
m.erase(it, m.end()); // erasing by range

m1.swap(m); //swap
m1.clear(); // Clear

3.5 operation

map<char, int>::iterator it = m.find('b');
m.count('a');

5. Map traversal (iteration)

5.1 Iterator 

map<char, int>::iterator it = m.begin();
while (it != m.end())
{
cout << (*it).first << " " << (*it).second << endl;
it++;
}

5.2 range for 

 for (auto e : m)
{
cout << e.first << " " << e.second << endl;
}

Summary

  1. The elements in the map are key-value pairs
  2. The key in the map is unique and cannot be modified
  3. By default, keys are compared based on less than
  4. If you use an iterator to traverse the elements in the map, you can get an ordered sequence
  5. The bottom layer of map is a balanced search tree (red-black tree), and the search efficiency is relatively high O(log2 N)
  6. Supports [ ] operator, insert search is actually performed in operator [ ]