佛山做外贸网站的公司吗/郑州seo哪家好

一、关联式容器

在初阶阶段，我们已经接触过STL中的部分容器，比如：vector、list、deque、forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高。

---

二、键值对

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。

SGI-STL中关于键值对的定义：

using namespace std;template <class T1, class T2>
struct pair
{typedef T1 first_type;typedef T2 second_type;T1 first;T2 second;pair() : first(T1()), second(T2()){}pair(const T1& a, const T2& b) : first(a), second(b){}
};

---

三、pair

pair的文档介绍

pair 是 C++ 标准库中的一个模板类，用于存储两个对象的有序对。通常情况下，pair 用于将两个不同类型的对象组合成一个单元，并且允许这两个对象分别访问。

3.1 pair的常用接口说明

3.1.1 无参构造函数

pair();

int main()
{pair <string, double> p;                     cout << p.first << "  " << p.second << endl;return 0;
}

---

3.1.2 有参构造函数 / 拷贝构造函数

template<class U, class V> pair (const pair<U,V>& pr);
当参数不匹配时为有参构造函数
当参数匹配时为拷贝构造函数

---

3.1.3 有参构造函数

pair (const first_type& a, const second_type& b);

int main()
{pair <string, double> p("Love", 5.20);   cout << p.first << " " << p.second << endl;;return 0;
}

---

3.1.4 make_pair()函数

template <class T1, class T2>pair<T1,T2> make_pair (T1 x, T2 y);

template <class T1, class T2>
pair<T1, T2> make_pair(T1 x, T2 y)
{return (pair<T1, T2>(x, y));
}

---

四、树形结构的关联式容器

根据应用场景的不桶，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。下面一依次介绍每一个容器。

4.1 标准库中的set

4.1.1 set的介绍

set的文档介绍

1. set是按照一定次序存储元素的容器
2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
3. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
4. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。
5. set在底层是用二叉搜索树(红黑树)实现的。

set的模板参数列表介绍

T: set中存放元素的类型，实际在底层存储<value, value>的键值对。

Compare：set中元素默认按照小于来比较

Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理（目前不需要掌握）

---

4.1.2 set的常用接口说明

4.1.2.1 set对象的常见构造

4.1.2.1.1 无参构造函数

set (const key_compare& comp = key_compare());

int main()
{set<int> s;return 0;
}

---

4.1.2.1.2 有参构造函数（使用迭代器进行初始化构造）

template <class InputIterator>set (InputIterator first, InputIterator last,const key_compare& comp = key_compare());

int main()
{string s("I Love Y");set<int> ss(s.begin(), s.end());for (auto e : ss){cout << e << ' ';}cout << endl;return 0;
}

---

4.1.2.1.3 拷贝构造函数

set (const set& x);

int main()
{string s("I Love Y");set<int> ss1(s.begin(), s.end());set<int> ss2(ss1);for (auto e : ss2){cout << e << ' ';}cout << endl;return 0;
}

---

4.1.2.2 set iterator 的使用

4.1.2.2.1 begin()函数 + end()函数

 	  iterator begin();
const_iterator begin() const;
获取第一个数据位置的iterator/const_iteratoriterator end();
const_iterator end() const;
获取最后一个数据的下一个位置的iterator/const_iterator

int main()
{string s("I Love Y");set<int> ss1(s.begin(), s.end());set<int>::iterator it = ss1.begin();while (it != ss1.end()){cout << *it << ' ';++it;}cout << endl;return 0;
}

---

4.1.2.2.2 rbegin()函数 + rend()函数

 	  reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
获取最后一个数据位置的reverse_iterator/const_reverse_iterator reverse_iterator rend();
const_reverse_iterator rend() const;
获取第一个数据前一个位置的reverse_iterator/const_reverse_iterator 

int main()
{string s("I Love Y");set<int> ss1(s.begin(), s.end());set<int>::reverse_iterator it = ss1.rbegin();while (it != ss1.rend()){cout << *it << ' ';++it;}cout << endl;return 0;
}

---

4.1.2.3 set对象的容量操作

4.1.2.3.1 size()函数

size_type size() const;	获取数据个数

---

4.1.2.3.2 empty()函数

bool empty() const;		判断是否为空

int main()
{set<int> ss;cout << ss.empty() << endl;string s("I Love Y");set<int> ss1(s.begin(), s.end());cout << ss1.empty() << endl;return 0;
}

---

4.1.2.4 set对象的增删查改及访问

4.1.2.4.1 insert()函数

pair<iterator,bool> insert (const value_type& val);
在set中插入一个元素val：若set中有这个元素，插入失败,则返回一个pair对象
pair.first=原来val元素位置的迭代器,pair.second = false若set中没有这个元素，插入成功,则返回一个pair对象
pair.first=新插入val元素位置的迭代器,pair.second = trueiterator insert (iterator position, const value_type& val);
不建议使用：在position位置插入一个val，并返回插入元素位置的迭代器template <class InputIterator>void insert (InputIterator first, InputIterator last);
插入一段迭代器区间的元素

int main()
{set<int> s;string ss("I Love Y");/*pair<iterator, bool> insert(const value_type & val);在set中插入一个元素val：*/pair<set<int>::iterator, bool> ret;for (int i = 0; i < 14; i += 2){ret = s.insert(i % 10);cout << "插入元素：" << *ret.first << "  是否成功：" << ret.second << endl;}for (auto e : s){cout << e << ' ';}cout << endl;// 插入一段迭代器区间的元素s.insert(ss.begin(), ss.end());for (auto e : s){cout << e << ' ';}cout << endl;return 0;
}

---

4.1.2.4.2 erase()函数

void erase (iterator position);
删除position位置的元素size_type erase (const value_type& val);
删除元素val并返回删除val的个数void erase (iterator first, iterator last);
删除一段迭代器区间内的元素

int main()
{set<int> s;for (int i = 0; i < 10; i++){s.insert(i);}for (auto e : s){	cout << e << ' ';	}cout << endl;set<int>::iterator it = s.begin();s.erase(it);for (auto e : s){	cout << e << ' ';	}cout << endl;// 删除元素val并返回val的个数s.erase(5);for (auto e : s){	cout << e << ' ';	}cout << endl;// 删除一段迭代器区间内的元素s.erase(++s.begin() , --s.end());for (auto e : s){	cout << e << ' ';	}cout << endl;return 0;
}

---

4.1.2.4.3 swap()函数

void swap (set& x);
交换两个set的数据空间

int main()
{set<int> s1;set<int> s2;for (int i = 1; i < 10; i += 2){	s1.insert(i);	}for (int i = 0; i < 10; i += 2){	s2.insert(i);	}for (auto e : s1){	cout << e << ' ';	}cout << endl;for (auto e : s2){	cout << e << ' ';	}cout << endl;s1.swap(s2);for (auto e : s1){	cout << e << ' ';	}cout << endl;for (auto e : s2){	cout << e << ' ';	}cout << endl;return 0;
}

---

4.1.2.4.4 clear()函数

void clear();
清除set中的有效数据

int main()
{set<int> s;for (int i = 1; i < 10; i += 2){	s.insert(i);	}s.clear();return 0;
}

---

4.1.2.4.5 find()函数

iterator find (const value_type& val) const;
返回set中为val元素位置的迭代器

int main()
{set<int> s;for (int i = 1; i < 10; i += 2){s.insert(i);}set<int>::iterator it = s.find(5);cout << *it << endl;return 0;
}

---

4.1.2.4.6 count()函数

size_type count (const value_type& val) const;
返回set中为val元素的个数
由于set并不允许相同的元素存在
所以set中所有元素的个数都是1

int main()
{set<int> s;for (int i = 1; i < 10; i += 2){s.insert(i);}for (auto e : s){cout << e << "的个数：" << s.count(e) << endl;}return 0;
}

---

4.1.2.4.7 lower_bound()函数

iterator lower_bound (const value_type& val) const;
返回第一个 >= val 对象位置的迭代器

int main()
{set<int> s;// 10 20 30 40 50for (int i = 1; i < 6; i++){s.insert(i*10);}set<int>::iterator it = s.lower_bound(30);cout << *it << endl;return 0;
}

---

4.1.2.4.8 upper_bound()函数

iterator upper_bound (const value_type& val) const;
返回第一个 > val 对象位置的迭代器

int main()
{set<int> s;// 10 20 30 40 50for (int i = 1; i < 6; i++){s.insert(i * 10);}set<int>::iterator it = s.upper_bound(30);cout << *it << endl;return 0;
}

---

4.1.2.4.9 equal_range()函数

pair<iterator,iterator> equal_range (const value_type& val) const;
返回一个pair对象
pair.first = 第一个 >= val 对象位置的迭代器
pair.second = 第一个 > val 对象位置的迭代器

int main()
{set<int> s;// 10 20 30 40 50for (int i = 1; i < 6; i++){s.insert(i * 10);}pair<set<int>::iterator, set<int>::iterator> p = s.equal_range(30);cout << *p.first << " " << * p.second << endl;return 0;
}

---

4.2 标准库中的multiset

4.2.1 multiset的介绍

multiset的文档介绍

1. multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。
2. multiset元素的值不能在容器中进行修改(因为元素总是const的)，但可以从容器中插入或删除。
3. 在内部，multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。
4. multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭代器遍历时会得到一个有序序列。
5. multiset底层结构为二叉搜索树(红黑树)。

注意：

1. mtltiset的插入接口中只需要插入即可
2. 与set的区别是，multiset中的元素可以重复，set是中value是唯一的
3. 使用迭代器对multiset中的元素进行遍历，可以得到有序的序列
4. multiset中的元素不能修改
5. 在multiset中找某个元素，时间复杂度为$O(lo{g}_{2}N)$
6. multiset的作用：可以对元素进行排序

4.2.2 multiset的常用接口说明

注意：multiset的接口与set的接口基本相似，可以参考set的使用，那么下面multiset将不会进行演示使用。

4.2.2.1 multiset对象的常用构造

4.2.2.1.1 无参构造函数

multiset (const key_compare& comp = key_compare());

---

4.2.2.1.2 有参构造函数（使用迭代器进行初始化构造）

template <class InputIterator>multiset (InputIterator first, InputIterator last,const key_compare& comp = key_compare());

---

4.2.2.1.3 拷贝构造函数

multiset (const multiset& x);

---

4.2.2.2 multiset iterator 的使用

4.2.2.2.1 begin()函数 + end()函数

 	  iterator begin();
const_iterator begin() const;
获取第一个数据位置的iterator/const_iteratoriterator end();
const_iterator end() const;
获取最后一个数据的下一个位置的iterator/const_iterator

---

4.2.2.2.2 rbegin()函数 + rend()函数

 	  reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
获取最后一个数据位置的reverse_iterator/const_reverse_iterator reverse_iterator rend();
const_reverse_iterator rend() const;
获取第一个数据前一个位置的reverse_iterator/const_reverse_iterator 

---

4.2.2.3 multiset 对象的容量操作

4.2.2.3.1 size()函数

size_type size() const;
获取数据个数

---

4.2.2.3.2 empty()函数

bool empty() const;		判断是否为空

---

4.2.2.4 multiset 对象的增删查改及访问

4.2.2.4.1 insert()函数

iterator insert (const value_type& val);
在multiset中插入一个元素val，并返回插入元素位置的迭代器
由于multiset可以存在相同的元素，那么就不存在插入失败的情况iterator insert (iterator position, const value_type& val);
不建议使用：在position位置插入一个val，并返回插入元素位置的迭代器template <class InputIterator>void insert (InputIterator first, InputIterator last);
插入一段迭代器区间的元素

---

4.2.2.4.2 erase()函数

void erase (iterator position);
删除position位置的元素size_type erase (const value_type& val);
删除元素val并返回删除val的个数void erase (iterator first, iterator last);
删除一段迭代器区间内的元素

---

4.2.2.4.3 swap()函数

void swap (multiset& x);
交换两个multiset的数据空间

---

4.2.2.4.4 clear()函数

void clear();
清除multiset中的有效数据

---

4.2.2.4.5 find()函数

iterator find (const value_type& val) const;
返回multiset中为val元素位置的迭代器

---

4.2.2.4.6 count()函数

size_type count (const value_type& val) const;	
返回multiset中为val元素的个数，multiset中可以存在相同的元素

---

4.2.2.4.7 lower_bound()函数

iterator lower_bound (const value_type& val) const;
返回第一个 >= val 对象位置的迭代器

---

4.2.2.4.8 upper_bound()函数

iterator upper_bound (const value_type& val) const;
返回第一个 > val 对象位置的迭代器

---

4.2.2.4.9 equal_range()函数

pair<iterator,iterator> equal_range (const value_type& val) const;
返回一个pair对象
pair.first = 第一个 >= val 对象位置的迭代器
pair.second = 第一个 > val 对象位置的迭代器

---

4.3 标准库中的map

4.3.1 map的介绍

map的文档介绍

1. map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
2. 在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:typedef pair<const key, T> value_type;
3. 在内部，map中的元素总是按照键值key进行比较排序的。
4. map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
5. map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
6. map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。

map的模板参数列表介绍

key: 键值对中key的类型

T： 键值对中value的类型

Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)

Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器（目前不需要掌握）

---

4.3.2 map的常用接口说明

4.3.2.1 map对象的常用构造

4.3.2.1.1 无参构造函数

map (const key_compare& comp = key_compare());

int main()
{map<int, int> m;return 0;
}                                                                                                                                                                                                                   

4.3.2.1.2 有参构造函数（使用迭代器进行初始化构造

template <class InputIterator>map (InputIterator first, InputIterator last,const key_compare& comp = key_compare());

map（有序关联容器）的构造函数通常也不接受其他容器类型的迭代器来直接构造。map 要求它的元素按照键（key）的顺序进行排序，因此在构造时，它期望提供的元素已经按照键的升序排列。

如果尝试使用未排序的迭代器范围（例如，来自 vector 或 list 的迭代器）来构造 map，将会导致编译错误或未定义行为，因为 map 无法保证这些元素的排序。

如果想要从一个容器（如 vector）创建一个 map，你需要确保容器中的元素已经按照键的升序排列，然后你可以使用迭代器范围来构造 map。

int main()
{vector<pair<int, int>> v({ {5,5},{13,13},{1,1} });sort(v.begin(), v.end());map<int,int> m1(v.begin(), v.end());map<int, int> m2(m1.begin(), m1.end());return 0;
}

---

4.3.2.1.3 拷贝构造函数

map (const map& x);

int main()
{map<int, int> m1;m1.insert(make_pair(1, 1));m1.insert(make_pair(2, 2));map<int, int> m2(m1);return 0;
}

---

4.3.2.2 map iterator 的使用

4.3.2.2.1 begin()函数 + end()函数

 	  iterator begin();
const_iterator begin() const;
获取第一个数据位置的iterator/const_iteratoriterator end();
const_iterator end() const;
获取最后一个数据的下一个位置的iterator/const_iterator

int main()
{map<int, int> m1;m1.insert(make_pair(1, 1));m1.insert(make_pair(2, 2));map<int, int>::iterator it = m1.begin();while(it != m1.end()){cout << "first：" << it->first << "  second:" << it->second << endl;++it;}return 0;
}

---

4.3.2.2.2 rbegin()函数 + rend()函数

 	  reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
获取最后一个数据位置的reverse_iterator/const_reverse_iterator reverse_iterator rend();
const_reverse_iterator rend() const;
获取第一个数据前一个位置的reverse_iterator/const_reverse_iterator 

int main()
{map<int, int> m1;m1.insert(make_pair(1, 1));m1.insert(make_pair(2, 2));map<int, int>::reverse_iterator it = m1.rbegin();while (it != m1.rend()){cout << "first：" << it->first<< "  second:" << it->second << endl;++it;}return 0;
}

---

4.3.2.3 map对象的容量操作

4.3.2.3.1 size()函数

size_type size() const;
获取数据个数

int main()
{map<int, int> m1;cout << m1.size() << endl;m1.insert(make_pair(1, 1));m1.insert(make_pair(2, 2));cout << m1.size() << endl;return 0;
}

---

4.3.2.3.2 empty()函数

bool empty() const;		判断是否为空

int main()
{map<int, int> m1;cout << m1.empty() << endl;m1.insert(make_pair(1, 1));m1.insert(make_pair(2, 2));cout << m1.empty() << endl;return 0;
}

---

4.3.2.4 map对象的增删查改及访问

4.3.2.4.1 insert()函数

pair<iterator,bool> insert (const value_type& val);
在map中插入键值对val：若map中有这个键值对，插入失败,则返回一个pair对象
pair.first=原来val位置的迭代器,pair.second = false若map中没有这个键值对，插入成功,则返回一个pair对象
pair.first=新插入val位置的迭代器,pair.second = trueiterator insert (iterator position, const value_type& val);
不建议使用：在position位置插入一个val，并返回插入键值对位置的迭代器template <class InputIterator>void insert (InputIterator first, InputIterator last);
插入一段迭代器区间的元素

int main()
{map<int,int> m1;/*pair<iterator, bool> insert(const value_type & val);在set中插入一个元素val：*/pair<map<int,int>::iterator, bool> ret;for (int i = 0; i < 14; i += 2){ret = m1.insert(make_pair(i % 10, i % 10));cout << "插入key：" << ret.first->first<< "  是否成功：" << ret.second << endl;}for (auto e : m1){cout << "first：" << e.first<< "  second：" << e.second << endl;}cout << endl;// 插入一段迭代器区间的元素map<int, int> m2;m2.insert(make_pair(520, 520));m2.insert(make_pair(1314, 1314));cout << "insert前m2中的元素" << endl;for (auto e : m2){cout << "first：" << e.first<< "  second：" << e.second << endl;}cout << endl;m2.insert(m1.begin(), m1.end());cout << "insert后m2中的元素" << endl;for (auto e : m2){cout << "first：" << e.first<< "  second：" << e.second << endl;}cout << endl;return 0;
}

---

4.3.2.4.2 erase()函数

void erase (iterator position);
删除position位置的元素size_type erase (const value_type& val);
删除元素val并返回删除val的个数void erase (iterator first, iterator last);
删除一段迭代器区间内的元素

int main()
{map<int, int> m1;/*pair<iterator, bool> insert(const value_type & val);在map中插入一个元素val：*/for (int i = 0; i < 14; i += 2){m1.insert(make_pair(i % 10, i % 10));}for (auto e : m1){cout << "first：" << e.first<< "  second：" << e.second << endl;}cout << endl;// 删除迭代器位置的元素m1.erase(m1.begin());for (auto e : m1){cout << "first：" << e.first<< "  second：" << e.second << endl;}cout << endl;// 删除元素，并返回元素个数m1.erase(6);for (auto e : m1){cout << "first：" << e.first<< "  second：" << e.second << endl;}cout << endl;// 删除一段迭代器区间内的元素m1.erase(++m1.begin(),--m1.end());for (auto e : m1){cout << "first：" << e.first<< "  second：" << e.second << endl;}cout << endl;return 0;
}

---

4.3.2.4.3 swap()函数

void swap (map& x);
交换两个map的数据空间

int main()
{map<int,int> m1;for (int i = 0; i < 14; i += 2){m1.insert(make_pair(i % 10, i % 10));}cout << "swap前m1中的元素" << endl;for (auto e : m1){cout << "first：" << e.first<< "  second：" << e.second << endl;}cout << endl;map<int, int> m2;m2.insert(make_pair(520, 520));m2.insert(make_pair(1314, 1314));cout << "swap前m2中的元素" << endl;for (auto e : m2){cout << "first：" << e.first<< "  second：" << e.second << endl;}cout << endl;m1.swap(m2);cout << "swap后m1中的元素" << endl;for (auto e : m1){cout << "first：" << e.first<< "  second：" << e.second << endl;}cout << endl;cout << "swap后m2中的元素" << endl;for (auto e : m2){cout << "first：" << e.first<< "  second：" << e.second << endl;}cout << endl;return 0;
}

---

4.3.2.4.4 clear()函数

void clear();
清除map中的有效数据

int main()
{map<int, int> m;for (int i = 0; i < 14; i += 2){m.insert(make_pair(i % 10, i % 10));}m.clear();return 0;
}

---

4.3.2.4.5 find()函数

	  iterator find (const key_type& k);
const_iterator find (const key_type& k) const;
返回map中为关键码为k位置的迭代器

int main()
{map<int, int> m;for (int i = 0; i < 14; i += 2){m.insert(make_pair(i % 10, i % 10));}map<int,int>::iterator it = m.find(6);cout << "first：" << it->first<< "  second：" << it->second << endl;return 0;
}

---

4.3.2.4.6 count()函数

size_type count (const key_type& k) const;
返回map中为k元素的个数
由于map并不允许相同的元素存在
所以map中所有元素的个数都是1

int main()
{map<int, int> m;for (int i = 0; i < 14; i += 2){m.insert(make_pair(i % 10, i % 10));}for (auto e : m){cout << e.first << "的个数："<< m.count(e.first) << endl;}return 0;
}

---

4.3.2.4.7 lower_bound()函数

	  iterator lower_bound (const key_type& k);
const_iterator lower_bound (const key_type& k) const;
返回第一个关键码 >= k对象位置的iterator/const_iterator

int main()
{map<int, int> m;for (int i = 0; i < 14; i += 2){m.insert(make_pair(i % 10, i % 10));}map<int, int>::iterator it = m.lower_bound(6);cout << "first：" << it->first<< "  second：" << it->second << endl;return 0;
}

---

4.3.2.4.8 upper_bound()函数

	  iterator upper_bound (const key_type& k);
const_iterator upper_bound (const key_type& k) const;
返回第一个关键码 > k 对象位置的iterator/const_iterator

int main()
{map<int, int> m;for (int i = 0; i < 14; i += 2){m.insert(make_pair(i % 10, i % 10));}map<int, int>::iterator it = m.upper_bound(6);cout << "first：" << it->first<< "  second：" << it->second << endl;return 0;
}

---

4.3.2.4.9 equal_range()函数

pair<const_iterator,const_iterator> equal_range (const key_type& k) const;
pair<iterator,iterator>             equal_range (const key_type& k);
返回一个pair对象
pair.first = 第一个关键码 >= k 对象位置的iterator/const_iterator
pair.second = 第一个关键码 > k 对象位置的iterator/const_iterator

int main()
{map<int, int> m;for (int i = 0; i < 14; i += 2){m.insert(make_pair(i % 10, i % 10));}pair<map<int, int>::iterator, map<int, int>::iterator>ret = m.equal_range(6);cout << "first：" << ret.first->first<< "  second：" << ret.first->second << endl;cout << "first：" << ret.second->first<< "  second：" << ret.second->second << endl;return 0;
}

---

4.3.2.4.10 operator[]

mapped_type& operator[] (const key_type& k);
返回关键码为key对应的value的引用

mapped_type& operator[] (const key_type& k)
{return (*((this->insert(make_pair(k,mapped_type()))).first)).second
}

int main()
{map<int, int> m;m.insert(make_pair(5, 5));// 若map中有这个元素，那么就返回key对应value的引用cout << "operator[]:" << m[5] <<endl;// 若map中没有这个元素，那么map中将会插入这个元素// 使用默认构造初始化value，并返回cout << "operator[]:" << m[10] << endl;for (auto e : m){cout << "first：" << e.first<< "  second：" << e.second << endl;}return 0;
}

---

【总结】

1. map中的的元素是键值对
2. map中的key是唯一的，并且不能修改
3. 默认按照小于的方式对key进行比较
4. map中的元素如果用迭代器去遍历，可以得到一个有序的序列
5. map的底层为平衡搜索树(红黑树)，查找效率比较高$O(lo{g}_{2}N)$
6. 支持[]操作符，operator[]中实际进行插入查找。

---

4.4 标准库中的multimap

4.4.1 multimap的介绍

multimap的文档介绍

1. Multimaps是关联式容器，它按照特定的顺序，存储由key和value映射成的键值对<key,value>，其中多个键值对之间的key是可以重复的。
2. 在multimap中，通常按照key排序和惟一地标识元素，而映射的value存储与key关联的内容。key和value的类型可能不同，通过multimap内部的成员类型value_type组合在一起，value_type是组合key和value的键值对:typedef pair<const Key, T> value_type;
3. 在内部，multimap中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对key进行排序的。
4. multimap通过key访问单个元素的速度通常比unordered_multimap容器慢，但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列。
5. multimap在底层用二叉搜索树(红黑树)来实现。
   注意：multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重复的。

注意：

1. multimap中的key是可以重复的。
2. multimap中的元素默认将key按照小于来比较
3. multimap中没有重载operator[]操作，因为multimap中的key可以重复，如果重载operator[]操作那么找到的结果是未定义的。
4. 使用时与map包含的头文件相同

---

4.4.2 multimap的常用接口说明

注意：multimap的接口与map的接口基本相似，可以参考map的使用，那么下面multimap将不会进行演示使用。

4.4.2.1 multimap对象的常用构造

4.4.2.1.1 无参构造函数

multimap (const key_compare& comp = key_compare());

---

4.4.2.1.2 有参构造函数（使用迭代器进行初始化构造）

template <class InputIterator>multimap (InputIterator first, InputIterator last,const key_compare& comp = key_compare());

---

4.4.2.1.3 拷贝构造函数

multimap (const multimap& x);

---

4.4.2.2 multimap iterator 的使用

4.4.2.2.1 begin()函数 + end()函数

 	  iterator begin();
const_iterator begin() const;
获取第一个数据位置的iterator/const_iteratoriterator end();
const_iterator end() const;
获取最后一个数据的下一个位置的iterator/const_iterator

---

4.4.2.2.2 rbegin()函数 + rend()函数

 	  reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
获取最后一个数据位置的reverse_iterator/const_reverse_iterator reverse_iterator rend();
const_reverse_iterator rend() const;
获取第一个数据前一个位置的reverse_iterator/const_reverse_iterator 

---

4.4.2.3 multimap 对象的容量操作

4.4.2.3.1 size()函数

size_type size() const;
获取数据个数

---

4.4.2.3.2 empty()函数

bool empty() const;		判断是否为空

---

4.4.2.4 multimap对象的增删查改及访问

4.4.2.4.1 insert()函数

iterator insert (const value_type& val);
在multimap中插入一个键值对val，并返回插入元素位置的迭代器
由于multimap可以存在相同的元素，那么就不存在插入失败的情况iterator insert (iterator position, const value_type& val);
不建议使用：在position位置插入一个val，并返回插入val位置的迭代器template <class InputIterator>void insert (InputIterator first, InputIterator last);
插入一段迭代器区间的元素

---

4.4.2.4.2 erase()函数

void erase (iterator position);
删除position位置的元素size_type erase (const value_type& val);
删除元素val并返回删除val的个数void erase (iterator first, iterator last);
删除一段迭代器区间内的元素

---

4.4.2.4.3 swap()函数

void swap (multiset& x);
交换两个multimap的数据空间

---

4.4.2.4.4 clear()函数

void clear();
清除multimap中的有效数据

---

4.4.2.4.5 find()函数

	  iterator find (const key_type& k);
const_iterator find (const key_type& k) const;
返回multimap中关键码为k位置的iterator/const_iterator

---

4.4.2.4.6 count()函数

size_type count (const key_type& k) const;
返回multimap中关键码为k元素的个数，multimap中可以存在相同的元素

---

4.4.2.4.7 lower_bound()函数

 	  iterator lower_bound (const key_type& k);
const_iterator lower_bound (const key_type& k) const;
返回第一个关键码 >= k 对象位置的iterator/const_iterator

---

4.4.2.4.8 upper_bound()函数

	  iterator upper_bound (const key_type& k);
const_iterator upper_bound (const key_type& k) const;
返回第一个关键码 > k 对象位置的iterator/const_iterator

---

4.4.2.4.9 equal_range()函数

pair<const_iterator,const_iterator> equal_range (const key_type& k) const;
pair<iterator,iterator>             equal_range (const key_type& k);
返回一个pair对象
pair.first = 第一个关键码 >= k 对象位置的iterator/const_iterator
pair.second = 第一个关键码 > k 对象位置的iterator/const_iterator

---

五、map和set在OJ中的应用

5.1 692. 前K个高频单词

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

思路：定义一个对象map<string, int> Map，string用来记录单词，int用来记录单词出现的次数。遍历vector并在Map中插入，由于Map是按照单词的大小进行比较的，再定义vector<pair<string, int>> tmp并用Map的迭代器区间对tmp进行初始化，再使用单词出现的次数进行排序。需要注意的是pair比较大小的时候是使用pair.first进行比较的，而单词的次数记录在pair.second中，所以我们需要自己写一个仿函数进行比较，单词出现次数多的在前面，单词小的在前面。由于答案只需要单词，那么再定义一个对象vector<string> ans记录答案，访问tmp中前k个元素，访问其中的单词并插入到ans中，最后输出ans完成本题。

class Solution {
public:struct Cmp{bool operator()(const pair<string, int>& p1 ,const pair<string, int>& p2){// 出现频率高，且按字典顺序return p1.second > p2.second || (p1.second == p2.second && p1.first < p2.first);}};vector<string> topKFrequent(vector<string>& words, int k) {map<string, int> Map;for(auto x : words){Map[x]++;}// 这里的vector是用来存储pair对象的vector<pair<string, int>> tmp(Map.begin(),Map.end());sort(tmp.begin() , tmp.end(), Cmp());// 需要输出vector<string> ,将pair中的string提取出来vector<string> ans;for(int i = 0 ; i < k ; i++){ans.push_back(tmp[i].first);}return ans;}
};

---

5.2 349. 两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

思路：set能对数据进行排序和去重，定义两个set对象s1，s2，使用nums1和nums2的迭代器区间对set进行初始化，定义vector<int> ans记录答案，定义两个set的迭代器it1和it2分别记录s1和s2的begin()，对两组数据同时遍历，迭代器指向元素小的++，因为小的元素不可能在和另外一组数据有相同的值，若迭代器指向的元素相等，将元素尾差到ans中，有一个迭代器走到最后则说明两组元素不可能再有相同的值了，将ans返回就能完成本道题。

上面是两个数组的交集的思路，而两个数组的差集的思路与交集的思路只有在元素入ans的时候有区别。对两组数据同时遍历，迭代器指向元素小的入ans并且迭代器++，因为小的元素不可能在和另外一组数据有相同的值，若迭代器指向的元素相等，两迭代器同时++，将ans返回就能实现得到两个数组的差集了。

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {// 将两分数据进行去重set<int> s1(nums1.begin(),nums1.end());set<int> s2(nums2.begin(),nums2.end());vector<int> ans;set<int>::iterator it1 = s1.begin();set<int>::iterator it2 = s2.begin();while(it1 != s1.end() && it2 != s2.end()){// 两个数中小的迭代器++// 两数相等时将数字尾差到vector中// 两迭代器同时++if(*it1 > *it2){++it2;}else if(*it1 < *it2){++it1;}else{ans.push_back(*it1);++it1;++it2;}}return ans;}
};

---

结尾

如果有什么建议和疑问，或是有什么错误，大家可以在评论区中提出。
希望大家以后也能和我一起进步！！🌹🌹
如果这篇文章对你有用的话，希望大家给一个三连支持一下！！🌹🌹