C++笔记16•数据结构:关联式容器map和set•

本文主要是介绍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;
}