C++笔记16•数据结构:关联式容器map和set•
map和set
1.关联式容器
前面介绍的的是序列式容器：vector、list、deque等容器。这次博客介绍STL新的容器成员，那就是关联式容器；顾名思义关联式容器就是容器存在中的数据之间存在联系（关联）。与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高。一般key不能被修改，由key去查找key对应的value。
2. 键值对
2.1含义：用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量 key 和 value ， key 代 表键值， value 表示与 key 对应的信息 。2.2举例：比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。2.3键值对的结构键值对是被存放在一个pair的结构体当中的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被写在一个模板里叫做make_pair中省略了参数类型。
template <class T1,class T2> pair<T1,T2> make_pair (T1 x, T2 y) { return ( pair<T1,T2>(x,y) ); }举个例子：
#include <iostream> int main() { std::pair <int, int> foo; std::pair <double, int> bar; foo = std::make_pair(10, 20); bar = std::make_pair(10.5, 'A'); std::cout << "foo: " << foo.first << ", " << foo.second << '\n'; std::cout << "bar: " << bar.first << ", " << bar.second << '\n'; return 0; }
3.树形结构的关联式容器
STL 总共实现了两种不同结构的管理式容器：树型结构与哈希结构(后面介绍)。树型结 构的关联式容器主要有四种： map 、 set 、 multimap 、 multiset 。这四种容器的共同点是：使用平衡搜索树( 即红黑树 ) 作为其底层结果，容器中的元素是一个有序的序列。下面一依次介绍每一个容器。3.1 set
1. set 是按照一定次序存储元素的容器2. 在 set 中，元素的 value 也标识它 (value 就是 key ，类型为 T) ，并且每个 value 必须是唯一的,set中的元素不能在容器中修改 ( 元素总是 const) ，但是可以从容器中插入或删除它们。3. 在内部， set 中的元素总是按照其内部比较对象 ( 类型比较 ) 所指示的特定严格弱排序准则进行排序。4. set 容器通过 key 访问单个元素并且 允许根据顺序对子集进行直接迭代。5. set 在底层是用二叉搜索树 (红黑树) 实现的。6.set 中插入元素时，只需要插入 value 即可，不需要构造键值对7.set 中的元素不可以重复 ( 因此可以使用 set 进行去重 )8.使用 set 的迭代器遍历 set 中的元素，可以得到有序序列（升序）9.set中的元素默认按照小于来比较10.set 中查找某个元素，时间复杂度为：O( log(n))代码示例：int main() { set<int> s; s.insert(1); s.insert(2); s.insert(3); s.insert(4); s.insert(5); s.insert(0); s.insert(6); s.insert(5);//set 不会将重复的5插入（去重） set<int>::iterator it = s.begin(); while (it != s.end()) { cout << *it << " "; ++it; } cout <<endl; return 0; }3.2 multiset
与set的区别就是multiset可以插入重复数据，其他基本都一样，所包含的头文件都是 #include <set>代码示例：int main() { multiset<int> s; //插入操作 s.insert(1); s.insert(2); s.insert(3); s.insert(4); s.insert(5); s.insert(0); s.insert(6); s.insert(5);//multiset 会将重复的5插入 这个是与set最主要的区别 multiset<int>::iterator it = s.begin(); while (it != s.end()) { cout << *it << " "; ++it; } cout << endl; //查找操作 multiset<int>::iterator pos = s.find(6);//时间复杂度O(logN) if (pos != s.end()) { cout << "找到6了" << endl; } else { cout << "没有找到6" << endl; } pos = find(s.begin(), s.end(), 0);//时间复杂度O(N) if (pos != s.end()) { cout << "找到0了" << endl; } else { cout << "没有找到0" << endl; } //重复的数据，find返回中序第一个数据 multiset<int>::iterator pf = s.find(5); while (pf != s.end()) { cout << *pf << " "; ++pf; } cout << endl; //删除操作 s.erase(0);//指定数值删除 multiset<int>::iterator pose = s.find(10);//先查找再删除 if (pose != s.end()) { s.erase(pose);//删除迭代器 } else { cout << "不存在，删除失败！" << endl; } multiset<int>::iterator start = s.lower_bound(2); multiset<int>::iterator end = s.upper_bound(4); s.erase(start,end);//删除区间迭代器（删除给定数值区间的数据） for (auto i : s) { cout << i << " "; } cout << endl; return 0; }3.3 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 中通过键值访问单个元素， map 允许根据顺序对元素进行直接迭代( 即对 map 中的元素进行迭代时，可以得到一个有序的序列（默认升序） ) 。5. map 支持下标访问符，即在 [] 中放入 key ，就可以找到与 key 对应的 value 。6. map 通常被实现为二叉搜索树 ( 更准确的说：平衡二叉搜索树 (map的底层是 红黑树 )) 。7.map中的的元素是键值对，封装在pair结构体中用first和second访问，key 是唯一的，并且不能修改，为了简便，pair被写在一个模板里叫做make_pair中省略了参数类型。8. map的底层为平衡搜索树 ( 红黑树 ) ，查找效率比较高 O(log(N))9. 支持 [ ] 操作符， operator[ ] 中实际进行插入查找。说明： map中的[ ]操作符可以直接实现插入，其底层是用insert实现的；
代码示例：#include <iostream> #include <map> using namespace std; void test1() { map<int, int> m; m.insert(pair<int, int>(1, 1)); m.insert(make_pair(2, 1)); m.insert(make_pair(3, 1)); m.insert(make_pair(4, 1));//用模板make_pair代替pair<int,int> //operator[] 实现插入 m[5];//默认的value是0 //m[5];//第二次插入会失败 因为map不支持插入重复的数据 m[5]++;//第二次插入虽然会失败 但是m[5]（operator[] 操作符）会返回原来节点的迭代器，并返回value值 由于m[5]还有后置++ 则value++ m[6]++;//插入成功（（operator[] 操作符）会返回新节点的迭代器） 并且value++ m[6] = 3;//有了就只修改 （修改） m[7] = 2;//没有就 先插入，再修改（插入+修改） //m.insert({ 8, 1 });//直接插入 map<int, int>::iterator it = m.begin(); while (it != m.end()) { cout << (*it).first << ":" << (*it).second << endl; cout << it->first << ":" << it->second << endl; ++it;//一定要++it，更新迭代器 } for (auto e : m) { cout << e.first << ":" << e.second << endl; } } void test2() { string arr[] = { "葡萄", "梨", "哈密瓜", "西瓜", "苹果", "橙子", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; map<string, int> m; //统计arr中水果的个数 方法一 查找+插入 //for(size_t i=0;i<sizeof(arr)/ sizeof(arr[0]);i++) //{ // map<string, int>::iterator pos = m.find(arr[i]); // if (pos != m.end()) // { // pos->second++; // } // else // { // m.insert(make_pair(arr[i], 1)); // } //} //范围for实现第二种的话 for (auto& e : arr) { map<string, int>::iterator pos = m.find(e); if (pos != m.end()) { pos->second++; } else { m.insert(make_pair(e, 1)); } } //方法二 //for (auto& s : arr) //{ // pair<map<string, int>::iterator,bool> ret = m.insert(make_pair(s,1));//简单写法 auto ret = m.insert(make_pair(s,1));初学者最好不要这样使用 // //auto ret = m.insert(make_pair(s, 1)); // if (!ret.second)//if (ret.second==false) // { // ret.first->second++; // } //} 方法三 for (auto& e : arr) { m[e]++; } 这三种统计次数的方法 一般推荐使用 方法三 使用operator[] 运算符重载 map<string, int>::iterator it = m.begin(); while (it != m.end()) { cout << it->first << ":" << it->second << endl; ++it;//一定要++it，更新迭代器 } } int main() { //test1(); test2(); return 0; }3.4multimap
multimap与map的区别就是multimap可以插入重复数据，其他基本都一样，所包含的头文件都是 #include <map>multimap 中的接口可以参考 map ，功能都是类似的。注意：1. multimap 中的 key 是可以重复的。2. multimap 中的元素默认将 key 按照小于来比较3. multimap 中没有重载 operator[] 操作 ( 同学们可思考下为什么 ?) 。4. 使用时与 map 包含的头文件相同ps： multimap 和 map 的唯一不同就是： map 中的 key 是唯一的，而 multimap 中 key 是可以重复的。还有就是multimap 和 map成员函数中 的 insert 返回值不一样：
代码示例void test3()//multimap { multimap<int, int> m; m.insert(pair<int, int>(1, 1)); m.insert(make_pair(2, 1)); m.insert(make_pair(3, 1)); m.insert(make_pair(4, 1));//用模板make_pair代替pair<int,int> //multimap不支持operator[] 实现插入 因为多个相同的key 不知道指向哪一个value进行访问 但可以用原生的insert插入重复的数据 m.insert(make_pair(5, 1)); m.insert(make_pair(5, 1)); m.insert({6,1}); multimap<int, int>::iterator it = m.begin(); while (it != m.end()) { cout << it->first << " " << it->second << endl; ++it;//一定要++it，更新迭代器 } for (auto e : m) { cout << e.first << " " << e.second << endl; } } void test4()//multimap { string arr[] = { "葡萄", "梨", "哈密瓜", "西瓜", "苹果", "橙子", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; multimap<string, int> m; //统计arr中水果的个数 方法一 查找+插入 //for(size_t i=0;i<sizeof(arr)/ sizeof(arr[0]);i++) //{ // multimap<string, int>::iterator pos = m.find(arr[i]); // if (pos != m.end()) // { // pos->second++; // } // else // { // m.insert(make_pair(arr[i], 1)); // } //} 范围for实现第二种的话 for (auto& e : arr) { multimap<string, int>::iterator pos = m.find(e); if (pos != m.end()) { pos->second++; } else { m.insert(make_pair(e, 1)); } } //方法二 //for (auto& s : arr) //{ // pair<multimap<string, int>::iterator, bool> ret = m.insert(make_pair(s, 1));//简单写法 auto ret = m.insert(make_pair(s,1));初学者最好不要这样使用 // //auto ret = m.insert(make_pair(s, 1)); // if (!ret.second)//if (ret.second==false) // { // ret.first->second++; // } //}//方法二也不行 这个是因为multimap和map成员函数中的insert返回值不一样 // //map中的insert返回pair<iterator, bool> multimap中的insert只返回iterator //方法三 //for (auto& e : arr) //{ // m[e]++; //} //multimap不支持operator[]重载 此方法不可以使用 multimap<string, int>::iterator it = m.begin(); while (it != m.end()) { cout << it->first << ":" << it->second << endl; ++it;//一定要++it，更新迭代器 } //实现全部插入（重复的也可以）不去重 for (auto& e : arr) { m.insert(make_pair(e, 1)); } for (auto& i : m) { cout << i.first << ":" << i.second << endl; } } int main() { test3(); test4(); return 0; }