本文主要是介绍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; }
这篇关于C++笔记16•数据结构:关联式容器map和set•的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
