【C++ data structure 】map

Common usage of map

Map stands for mapping. You can map any primitive type (including STL container) to any primitive type (including STL container). For example, you can create mappings such as int to double, string to int, etc.

Map provides one-to-one hashes, which function like Python’s dictionary:

• The first one is called a key, and each key can appear only once in the map.
• The second is called the value of the key;

1. The header files

#include <map>
Copy the code

The <bits/stdc++. H > header file already contains this header file.

Definition 2.

Define map as follows. The first parameter is of type key and the second parameter is of type value.

map<typename1, typename2> mp;
Copy the code

If the mapping is from string to integer, you must use string instead of char array.

Map keys and values can also be STL containers, for example a set can be mapped to a string:

map<set<int>, string> mp;
Copy the code

3. Access to elements in the map container

(1) Access by subscript

Note: Map keys are unique.

#include <iostream>
#include <map>
using namespace std;
int main(a){
    map<char.int> mp;
    mp['c'] = 30; 
    cout << mp['c'] << endl; 
    return 0;
}
Copy the code

30

(2) Access through iterators

Define iterators:

map<typename1, typename2>::iterator it;
Copy the code

This results in the iterator it, where map can use it->first to access keys and it->second to access values.

#include <stdio.h>
#include <map>
using namespace std;
int main(a){
    map<char.int> mp;
    mp['m'] = 20;
    mp['r'] = 30;
    mp['a'] = 40;
    for(map<char.int>::iterator it = mp.begin(a); it! =mp.end(a); it++){printf("%c %d\n", it->first, it->second);
    }
    return 0;
}
Copy the code

Output:

a 40

m 20

r 30

【 Note 】 The map automatically sorts the keys from smallest to largest. Iterators cannot be compared with < or >, but only with == or! =

(3) Access through a reverse iterator

#include <stdio.h>
#include <map>
using namespace std;
int main(a){
    map<char.int> mp;
    mp['m'] = 20;
    mp['r'] = 30;
    mp['a'] = 40;
    for(map<char.int>::reverse_iterator it = mp.rbegin(a); it! =mp.rend(a); it++){printf("%c %d\n", it->first, it->second);
    }
    return 0;
}
Copy the code

Output:

r 30

m 20

a 40

Rbegin () points to the last element of the map, and rend() points before the first element of the map.

4. Insert map elements

(1) Insert by insert + <key, value

map<int, string> mapStudent;  
mapStudent.insert(pair<int, string>(1."student_one"));  
Copy the code

(2) Insert via insert + iterator

map<int, string> mapStudent;  
mapStudent.insert(map<int, string>::value_type (1."student_one")); 
Copy the code

(3) Insert through array

map<int, string> mapStudent;  
mapStudent[1] = "student_one";
Copy the code

【 Note 】 The first and second methods are completely equivalent, but the third method is different from the first two. When the map contains keys, the first and second methods fail to insert, and the third method overwrites the previous key-value pairs. So if you insert elements with the same key successively, the first and second methods retain the data of the first, and the third method preserves the data of the last.

5. Map common function instance analysis

(1) the find ()

Find (key) returns an iterator for the map with key as the time complexity O(logN), where N is the number of maps in the map.

#include <stdio.h>
#include <map>
using namespace std;
int main(a){
    map<char.int> mp;
    mp['a'] = 1;
    mp['b'] = 2;
    mp['c'] = 3;
    map<char.int>::iterator it = mp.find('b');
    printf("%c %d\n", it->first, it->second);
    return 0;
}
Copy the code

b 2

(2) erase ()

① Delete a single element

Mp.erase (it) : it is the iterator of the element to be deleted, O(1)

#include <stdio.h>
#include <map>
using namespace std;
int main(a){
    map<char.int> mp;
    mp['a'] = 1;
    mp['b'] = 2;
    mp['c'] = 3;
    map<char.int>::iterator it = mp.find('b');
    mp.erase(it);  // delete b 2
    for(map<char.int>::iterator it = mp.begin(a); it! =mp.end(a); it++){printf("%c %d\n", it->first, it->second);
    }
    return 0;
}
Copy the code

a 1

c 3

Mp.erase (key) : Key is the key of the mapping to be deleted. The time complexity is O(logN).

#include <stdio.h>
#include <map>
using namespace std;
int main(a){
    map<char.int> mp;
    mp['a'] = 1;
    mp['b'] = 2;
    mp['c'] = 3;
    mp.erase('b');  // delete b 2
    for(map<char.int>::iterator it = mp.begin(a); it! =mp.end(a); it++){printf("%c %d\n", it->first, it->second);
    }
    return 0;
}
Copy the code

a 1

c 3

② Delete all elements in an interval

Mp. erase(first, last) : First is the starting iterator of the interval to be deleted. Last is the next address of the last iterator of the interval to be deleted.

#include <stdio.h>
#include <map>
using namespace std;
int main(a){
    map<char.int> mp;
    mp['a'] = 1;
    mp['b'] = 2;
    mp['c'] = 3;
    map<char.int>::iterator it = mp.find('b');  // set it to the mapping with key b
    mp.erase(it, mp.end());  // Delete all mappings after it
    for(map<char.int>::iterator it = mp.begin(a); it! =mp.end(a); it++){printf("%c %d\n", it->first, it->second);
    }
    return 0;
}
Copy the code

a 1

(3) the size ()

Size () : obtains the logarithm of the mapping in the map. The time complexity is O(1).

#include <stdio.h>
#include <map>
using namespace std;
int main(a){
    map<char.int> mp;
    mp['a'] = 10;
    mp['b'] = 20;
    mp['c'] = 30;
    printf("%d\n", mp.size());  // 3 pairs of mappings
    return 0;
}
Copy the code

3

(4) the count ()

Count (): Returns the number of keys in the map. There can be only one key in the map. Therefore, the result of count() can be 0 or 1.

#include <iostream>
#include <map>

int main (a){
  	std::map<char.int> mymap;
	char c;
	
	mymap ['a'] =101;
	mymap ['c'] =202;
	mymap ['d'] =303;
	
	for (c='a'; c<'e'; c++){
	  std::cout << c;
	  if (mymap.count(c)>0)
	    std::cout << " is an element of mymap.\n";
	  else 
	    std::cout << " is not an element of mymap.\n";
	}
	return 0;
}
Copy the code

Results:

a is an element of mymap.

b is not an element of mymap.

c is an element of mymap.

d is an element of mymap.

(5) the clear ()

Clear (): Clears a map. The map becomes empty.

(6) the empty ()

Empty () : Checks whether the map is empty. Return true if the map is empty and false otherwise.

(7) lower_bound(), upper_bound()

Lower_bound () : Returns the key value >= the first position of the given element. That is, if the key types are comparable, binary lookup can be used, and the type returned is an iterator. Upper_bound (): returns key > the first position of the given element. That is, if the key types are comparable, binary lookup can be used, and the type returned is an iterator.

map<int, string> mapStudent;  
mapStudent[1] = "student_one";  
mapStudent[3] = "student_three";  
mapStudent[5] = "student_five"; 
map<int, string>::iterator iter;
iter = mapStudent.lower_bound(2); // Return an iterator with a key of 3;
iter = mapStudent.upper_bound(2); // Return iterator with key 3
Copy the code