第十四章 STL容器第四节 Set和multiset、pair、Map和multimap容器
Set和multiset容器
- Set和multiset简介
- set是一个集合容器，其中所包含的元素是唯一的，集合中的元素按一定的顺序自动排列。元素插入过程是按排序规则插入，所以不能指定插入位置。
- set采用红黑树变体的数据结构实现，红黑树属于平衡二叉树。在插入操作和删除操作上比vector快。
- set不可以直接存取元素。（不可以使用at.(pos)与[]操作符）。
- multiset与set的区别：set支持唯一键值，每个元素值只能出现一次；而multiset中同一值可以出现多次。
- 不可以直接修改set或multiset容器中的元素值，因为该类容器是自动排序的。如果希望修改一个元素值，必须先删除原有的元素，再插入新的元素。
#include <set>
- set的插入与迭代器
-
函数：
set.insert(elem); //在容器中插入元素。 set.begin(); //返回容器中第一个数据的迭代器。 set.end(); //返回容器中最后一个数据之后的迭代器。 set.rbegin(); //返回容器中倒数第一个元素的迭代器。 set.rend(); //返回容器中倒数最后一个元素的后面的迭代器。 -
举例：
set<int> setInt; setInt.insert(3); setInt.insert(1);setInt.insert(5);setInt.insert(2); for(set<int>::iterator it=setInt.begin(); it!=setInt.end(); ++it) { int iItem = *it; cout << iItem; //或直接使用cout << *it } //这样子便顺序输出 1 2 3 5。
-
- Set集合的元素排序
-
示例：
set<int,less<int> > setIntA; //该容器是按升序方式排列元素。 set<int,greater<int>> setIntB; //该容器是按降序方式排列元素。set<int>相当于set<int,less<int>>。less<int>与greater<int>中的int可以改成其它类型，该类型主要要跟set容纳的数据类型一致。
- 疑问1：less<>与greater<>是什么？
- 疑问2：如果set<>不包含int类型，而是包含自定义类型，set容器如何排序？
- 要解决如上两个问题，需要了解容器的函数对象，也叫伪函数，英文名叫
functor。 -
举例使用
set<int,greater<int>> setIntB; setIntB.insert(3); setIntB.insert(1); setIntB.insert(5); setIntB.insert(2); //此时容器setIntB就包含了按顺序的5,3,2,1元素
-
- 函数对象functor的用法(就是前面讲的仿函数)
- 尽管函数指针被广泛用于实现函数回调，但C++还提供了一个重要的实现回调函数的方法，那就是函数对象。
- functor，翻译成函数对象，伪函数，算符，是重载了“()”操作符的普通类对象。从语法上讲，它与普通函数行为类似。
- greater<>与less<>就是函数对象。
-
下面举出greater
的简易实现原理。 template <class Item> struct greater{ //重载()运算符 bool operator() (const Item& iLeft, const Item& iRight){ return (iLeft>iRight); //如果是实现less<int>的话，这边是写return (iLeft<iRight); } } //容器就是调用函数对象的operator()方法去比较两个值的大小。 - 从上面greater实现可以看出，要想实现复杂数据类型的的排序必须满足一下条件
- 实现自定义类的函数对象
- 在函数对象中重载（）方法，指明按照自定义类的那个属性排序
- 声明容器时说明
-
示例代码：
//题目：学生包含学号，姓名属性，现要求任意插入几个学生对象到set容器中，使得容器中的学生按学号的升序排序。 //1. 学生类 class CStudent { public: CStudent(int iID, string strName) { m_iID = iID; m_strName = strName; } int m_iID; //学号 string m_strName; //姓名 } //为保持主题鲜明，本类不写拷贝构造函数，本类也不需要写拷贝构造函数。但大家仍要有考虑拷贝构造函数的习惯。 //2. 创建函数对象 //函数对象：因为这是特定类型，所以就不需要类模板了 struct StuFunctor{ //3. 重载()操作符 bool operator() (const CStudent &stu1, const CStudent &stu2){ return (stu1.m_iID<stu2.m_iID); } } //3. 使用 //main函数 void main(){ set<CStudent, StuFunctor> setStu; setStu.insert(CStudent(3,"小张")); setStu.insert(CStudent(1,"小李")); setStu.insert(CStudent(5,"小王")); setStu.insert(CStudent(2,"小刘")); //此时容器setStu包含了四个学生对象，分别是按姓名顺序的“小李”，“小刘”，“小张”，“小王” }
-
赋值、大小：
set<int> setIntA; setIntA.insert(3); setIntA.insert(1); setIntA.insert(7); setIntA.insert(5); setIntA.insert(9); set<int> setIntB(setIntA); //1 3 5 7 9 set<int> setIntC; setIntC = setIntA; //1 3 5 7 9 setIntC.insert(6); setIntC.swap(setIntA); //交换 setIntC.empty();//判断容器是否为空 setIntC.size(); //返回容器中元素的数目 -
set的删除
set.clear(); //清除所有元素 set.erase(pos); //删除pos迭代器所指的元素，返回下一个元素的迭代器。 set.erase(beg,end); //删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。 set.erase(elem); //删除容器中值为elem的元素。 //删除区间内的元素 //setInt是用set<int>声明的容器，现已包含按顺序的1,3,5,6,9,11元素。 set<int>::iterator itBegin=setInt.begin(); ++ itBegin; set<int>::iterator itEnd=setInt.begin(); ++ itEnd; ++ itEnd; ++ itEnd; setInt.erase(itBegin,itEnd); //此时容器setInt包含按顺序的1,6,9,11四个元素。 //删除容器中第一个元素 setInt.erase(setInt.begin()); //6,9,11 //删除容器中值为9的元素 set.erase(9); //删除setInt的所有元素 setInt.clear(); //容器为空 - set的查找（先看pair容器，在看这个）
-
函数
set.find(elem); //查找elem元素，返回指向elem元素的迭代器。 set.count(elem); //返回容器中值为elem的元素个数。对set来说，要么是0，要么是1。对multiset来说，值不可能大于1。 set.lower_bound(elem); //返回第一个>=elem元素的迭代器。 set.upper_bound(elem);// 返回第一个>elem元素的迭代器。 set.equal_range(elem); //返回容器中与elem相等的上下限的两个迭代器。上限是闭区间，下限是开区间，如[beg,end)。 //以上函数返回两个迭代器，而这两个迭代器被封装在pair中。 set<int> setInt; setInt.insert(3); setInt.insert(1); setInt.insert(7); setInt.insert(5); setInt.insert(9); set<int>::iterator itA = setInt.find(5); int iA = *itA; //iA == 5 int iCount = setInt.count(5); //iCount == 1 set<int>::iterator itB = setInt.lower_bound(5); set<int>::iterator itC = setInt.upper_bound(5); int iB = *itB; //iB == 5 int iC = *itC; //iC == 7 pair< set<int>::iterator, set<int>::iterator > pairIt = setInt.equal_range(5); //pair是什么？ set<int>::iterator itBeg = pairIt.first; set<int>::iterator itEnd = pairIt.second; //此时 *itBeg==5 而 *itEnd == 7
-
pair容器
- pair也是一个容器，译为对组，这个容器只能存放2个元素
- pair<T1,T2>:表示存放的两个值的类型，可以不一样，如T1为int，T2为float。T1,T2也可以是自定义类型。即T1,T2代表pair存放的两个元素的类型
- pair.first是pair里面的第一个值，是T1类型。
- pair.second是pair里面的第二个值，是T2类型。
- 就相当于OC中RAC框架中的元组RACTuple
-
举例使用：
/* 1. 如何判断一个数据是否插入成功？ 2. insert函数的返回值是_Pairib类型 3. using _Pairib = pair<iterator, bool>; 即_Pairib 是 pair<iterator, bool>类型 注意： iterator要指出具体迭代器的类型 */ void test11() { Teacher t1("t1", 30); Teacher t2("t1", 22); Teacher t3("t1", 34); Teacher t4("t1", 44); Teacher t5("t1", 30); set<Teacher,FuncTeacher> ss1; ss1.insert(t1); ss1.insert(t2); ss1.insert(t3); //接收insert函数的返回值 //此时pair1，内部有2个元素，一个是迭代器，一个是bool值 pair<set<Teacher,FuncTeacher>::iterator, bool> pair1 = ss1.insert(t4); if (pair1.second){ cout << "插入成功" << endl; }else{ cout << "插入失败" << endl; } //这个会插入失败，因为有2个30 pair<set<Teacher, FuncTeacher>::iterator, bool> pair2 =ss1.insert(t5); if (pair2.second) { cout << "插入成功" << endl; } else { cout << "插入失败" << endl; } for (set<Teacher, FuncTeacher>::iterator it = ss1.begin(); it != ss1.end(); it++) { cout << it->m_age << ":" << it->name << endl; } }
Map和multimap容器
- map/multimap的简介
- map是标准的关联式容器，一个map是一个键值对序列，即(key,value)对。它提供基于key的快速检索能力。
- map中key值是唯一的。集合中的元素按一定的顺序排列。元素插入过程是按排序规则插入，所以不能指定插入位置。
- map的具体实现采用红黑树变体的平衡二叉树的数据结构。在插入操作和删除操作上比vector快。
- map可以直接存取key所对应的value，支持[]操作符，如map[key]=value。
- multimap与map的区别：map支持唯一键值，每个键只能出现一次；而multimap中相同键可以出现多次。multimap不支持[]操作符。
#include <map>
-
map/multimap对象的默认构造
map/multimap采用模板类实现，对象的默认构造形式： map<T1,T2> mapTT; multimap<T1,T2> multimapTT; 如： map<int, char> mapA; map<string,float> mapB; //其中T1,T2还可以用各种指针类型或自定义类 - map的插入与迭代器
map.insert(...); //往容器插入元素，返回pair<iterator,bool>- 在map中插入元素的三种方式：假设
map<int, string> mapStu;- 通过pair的方式插入对象
mapStu.insert( pair<int,string>(3,"小张") ); - 通过pair的方式插入对象
mapStu.inset(make_pair(-1, “校长-1”)); - 通过value_type的方式插入对象
mapStu.insert(map<int,string>::value_type(1,"小李")); -
通过数组的方式插入值
mapStu[3] = “小刘"; mapStu[5] = “小王"； - 前三种方法，采用的是
insert()方法，该方法返回值为pair<iterator,bool>- iterator:是插入值的迭代器的位置
- bool：是否插入成功
- 这三种方法，一旦key存在，bool值为false，可以判断是否插入成功
- 第四种方法非常直观，但存在一个性能的问题。插入3时，先在mapStu中查找主键为3的项，若没发现，则将一个键为3，值为初始化值的对组插入到mapStu中，然后再将值修改成“小刘”。若发现已存在3这个键，则修改这个键对应的value，覆盖掉。
string strName = mapStu[2]; //取操作或插入操作- 只有当mapStu存在2这个键时才是正确的取操作，否则会自动插入一个实例，键为2，值为初始化值。
- 通过pair的方式插入对象
-
举例:
//假设 map<int, string> mapA; pair< map<int,string>::iterator, bool > pairResult = mapA.insert(pair<int,string>(3,"小张")); //插入方式一： pairResult.first是插入pair的迭代器位置，只有拿到它才能去除pair内部的值 //换一个理解方式：mapA内部存放的都是pair元素，insert是想mapA插入一个pair元素，同时返回一个pair类型的值，iterator就是指向插入那个元素的指针（也是pair类型），bool是插入是否成功 int iFirstFirst = (pairResult.first)->first; //iFirst == 3; string strFirstSecond = (pairResult.first)->second; //strFirstSecond为"小张" bool bSecond = pairResult.second; //bSecond == true; mapA.insert(map<int,string>::value_type(1,"小李")); //插入方式二 mapA[3] = "小刘"; //修改value mapA[5] = "小王"; //插入方式三 string str1 = mapA[2]; //执行插入 string() 操作，返回的str1的字符串内容为空。 string str2 = mapA[3]; //取得value，str2为"小刘" //迭代器遍历 for (map<int,string>::iterator it=mapA.begin(); it!=mapA.end(); ++it) { pair<int, string> pr = *it; int iKey = pr.first; string strValue = pr.second; } -
map内的排序
map<T1,T2,less<T1> > mapA; //该容器是按键的升序方式排列元素。未指定函数对象，默认采用less<T1>函数对象。 map<T1,T2,greater<T1>> mapB; //该容器是按键的降序方式排列元素。 less<T1>与greater<T1> 可以替换成其它的函数对象functor。 可编写自定义函数对象以进行自定义类型的比较，使用方法与set构造时所用的函数对象一样。 map.begin(); //返回容器中第一个数据的迭代器 map.end(); //返回容器中最后一个数据之后的迭代器。 map.rbegin(); //返回容器中倒数第一个元素的迭代器。 map.rend(); //返回容器中倒数最后一个元素的后面的迭代器。
-
map对象的拷贝构造与赋值
map<int, string> mapA; mapA.insert(pair<int,string>(3,"小张")); mapA.insert(pair<int,string>(1,"小杨")); mapA.insert(pair<int,string>(7,"小赵")); mapA.insert(pair<int,string>(5,"小王")); map<int ,string> mapB(mapA);//拷贝构造 map<int, string> mapC; mapC = mapA; //赋值 mapC[3] = "老张"; mapC.swap(mapA); //交换 mapC.size(); //返回容器中元素的数目 mapC.empty();//判断容器是否为空 -
map的删除
map.clear(); //删除所有元素 map.erase(pos); //删除pos迭代器所指的元素，返回下一个元素的迭代器。 map.erase(beg,end); //删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。 map.erase(keyElem); //删除容器中key为keyElem的对组。 map<int, string> mapA; mapA.insert(pair<int,string>(3,"小张")); mapA.insert(pair<int,string>(1,"小杨")); mapA.insert(pair<int,string>(7,"小赵")); mapA.insert(pair<int,string>(5,"小王")); //删除区间内的元素 map<int,string>::iterator itBegin=mapA.begin(); ++ itBegin; ++ itBegin; map<int,string>::iterator itEnd=mapA.end(); mapA.erase(itBegin,itEnd); //此时容器mapA包含按顺序的{1,"小杨"}{3,"小张"}两个元素。 mapA.insert(pair<int,string>(7,"小赵")); mapA.insert(pair<int,string>(5,"小王")); //删除容器中第一个元素 mapA.erase(mapA.begin()); //此时容器mapA包含了按顺序的{3,"小张"}{5,"小王"}{7,"小赵"}三个元素 //删除容器中key为5的元素 mapA.erase(5); //删除mapA的所有元素 mapA.clear(); //容器为空 - map的查找
map.find(key);查找键key是否存在，若存在，返回该键的元素的迭代器；若不存在，返回map.end();-
map.count(keyElem); //返回容器中key为keyElem的对组个数。对map来说，要么是0，要么是1。对multimap来说，值可能大于1。 map.lower_bound(keyElem); //返回第一个key>=keyElem元素的迭代器。map.upper_bound(keyElem); // 返回第一个key>keyElem元素的迭代器map.equal_range(keyElem); //返回容器中key与keyElem相等的上下限的两个迭代器。上限是闭区间，下限是开区间，如[beg,end)。- 以上函数返回两个迭代器，而这两个迭代器被封装在pair中。
-
举例：
//1. 例1 map<int,string>::iterator it=mapStu.find(3); if(it == mapStu.end()) { //没找到 }else{ //找到了 pair<int, string> pairStu = *it; int iID = pairStu.first; //或 int iID = it->first; string strName = pairStu.second; //或 string strName = it->second; } //2. 例2： 例如： mapStu是用map<int,string>声明的容器，已包含{1,"小李"}{3,"小张"}{5,"小王"}{7,"小赵"}{9,"小陈"}元素。 map<int,string>::iterator it; it = mapStu.lower_bound(5); //it->first==5 it->second=="小王" it = mapStu.upper_bound(5); //it->first==7 it->second=="小赵" it = mapStu.lower_bound(6); //it->first==7 it->second=="小赵" it = mapStu.upper_bound(6); //it->first==7 it->second=="小赵" //3. 例3： 例如 map<int,string> mapStu; ... //往mapStu容器插入元素{1,"小李"}{3,"小张"}{5,"小王"}{7,"小赵"}{9,"小陈"} pair< map<int,string>::iterator , map<int,string>::iterator > pairIt = mapStu.equal_range(5); map<int, string>::iterator itBeg = pairIt.first; map<int, string>::iterator itEnd = pairIt.second; //此时 itBeg->first==5 , itEnd->first == 7, itBeg->second=="小王", itEnd->second=="小赵"
-
multimap的使用举例:
Person p1, p2, p3, p4; p1.name = "王1"; p1.age = 11; p2.name = "王2"; p2.age = 12; p3.name = "王3"; p3.age = 13; p4.name = "王4"; p4.age = 14; multimap<string, Person> map1; //销售部门 map1.insert(make_pair("sale", p1)); map1.insert(make_pair("sale", p2)); //技术部 map1.insert(make_pair("develop", p3)); map1.insert(make_pair("develop", p4)); for (multimap<string,Person>::iterator it = map1.begin();it!=map1.end();it++) { cout << (*it).first<<(*it).second.name << endl; } cout << "销售部门人数:" << map1.count("sale") << endl; //这个it2返回的是符合第一个元素的迭代器，所以必须用tag记录 multimap<string, Person>::iterator it2 = map1.find("develop"); int tag = 0; while (it2 !=map1.end() && tag<map1.count("develop") ) { cout << (*it2).first << (*it2).second.name << endl; it2++; tag++; }
容器总结
- 容器的共通能力
- 理论提高：所有容器提供的都是值（value）语意，而非引用（reference）语意。
- 容器执行插入元素的操作时，内部实施拷贝动作。默认是值拷贝
- 所以STL容器内存储的元素必须能够被拷贝（必须提供拷贝构造函数）。
- 而且“=”操作符也要重载
- 除了queue与stack外，每个容器都提供可返回迭代器的函数，运用返回的迭代器就可以访问元素。
- 通常STL不会丢出异常。要求使用者确保传入正确的参数。
- 每个容器都提供了一个默认构造函数跟一个默认拷贝构造函数。
-
如已有容器vecIntA。
vector<int> vecIntB(vecIntA); //调用拷贝构造函数，复制vecIntA到vecIntB中。 //与大小相关的操作方法(c代表容器)： c.size(); //返回容器中元素的个数 c.empty(); //判断容器是否为空 //比较操作(c1,c2代表容器)： c1 == c2 判断c1是否等于c2 c1 != c2 判断c1是否不等于c2 c1 = c2 把c2的所有元素指派给c1
- 理论提高：所有容器提供的都是值（value）语意，而非引用（reference）语意。
-
各个容器的使用时机
- Vector的使用场景：比如软件历史操作记录的存储，我们经常要查看历史记录，比如上一次的记录，上上次的记录，但却不会去删除记录，因为记录是事实的描述。
- deque的使用场景：比如排队购票系统，对排队者的存储可以采用deque，支持头端的快速移除，尾端的快速添加。如果采用vector，则头端移除时，会移动大量的数据，速度慢。
- vector与deque的比较：
- vector.at()比deque.at()效率高，比如vector.at(0)是固定的，deque的开始位置却是不固定的。
- 如果有大量释放操作的话，vector花的时间更少，这跟二者的内部实现有关。
- deque支持头部的快速插入与快速移除，这是deque的优点。
- list的使用场景：比如公交车乘客的存储，随时可能有乘客下车，支持频繁的不确实位置元素的移除插入。
- set的使用场景：比如对手机游戏的个人得分记录的存储，存储要求从高分到低分的顺序排列。
- map的使用场景：比如按ID号存储十万个用户，想要快速要通过ID查找对应的用户。二叉树的查找效率，这时就体现出来了。如果是vector容器，最坏的情况下可能要遍历完整个容器才能找到该用户。