map/multimap

1.特性     map保证出现在map内的pair只出现一次，且map内的元素按照first从小到大排序，但是当first相同时，那么按照输入的顺序排序 2.初始化 ①初始化一个映射

map<int, int> m;

②复制一个映射

map <int ,int > mm(m);

3.求长度(时间复杂度为O(1))

m.size();

4.判空(时间复杂度为O(1))

a.empty();

5.清空

a.clear();

6.删除元素/插入元素

a.erase(1); // 删除first为1的那个值 ，时间复杂度为O(logn ) a.erase(a.begin()); // 删除map的第一个元素 a.insert({1, 2}); // 插入一个pair a[1] = 2; // 插入一个pair，时间复杂度为O(logn)

7.判断一个数是否出现过

a.count(x); // 判断x是否在集合中出现过，如果出现过返回1，否则0

8.迭代器

a.begin(); // 第一个元素的迭代器 a.end(); // 最后一个元素的下一位的迭代器

9.遍历

// 1.迭代器遍历 for (map<int,int>::iterator it = m.begin(); it != m.end(); ++it) cout << (*it).second << ends; // 2. c++方式遍历 for (auto mi: m) cout << mi.second << ends;

10.查找（支持lower_bound() 和 upper_bound()操作）

map<int, int> s; s[1] = 2; S[2] = 3; map <int> ::iterator it = m.lower_bound(2); if (it != m.end()) cout << *it; else cout << 0;

11.multimap的性质和map一样，上面全是map的特性，而multimap在map的特性之上使得一个集合内可以出现多次同一个元素,multimap内的元素也是按照字典序排好序的

multimap<int, int> m; m.insert({1, 2}); m.insert({1, 3}); for (auto mi: m) cout << mi.second << ends;

输出

2 3

在s.erase(int x)时，会删除所有出现的x，时间复杂度为O(logn + k) (k为出现次数)

multimap<int, int> m; m.insert({1, 4}); m.insert({1, 3}); m.insert({1, 5}); m.erase(1); cout << m.empty();

输出

1