C++ map和set功能详解
C++ map和set功能详解
本文详细介绍了C++中的map和set容器。从基本概念、使用方法到具体代码示例，内容全面且深入。对于C++开发者来说，这是一篇非常实用的教程。
前言
map和set是一种专门用来搜索的容器，底层为二叉搜素树
二叉搜索树：即比父节点小放在左边，比父节点大的放在右边
map能存储两个数据类型，我们称之为**
set只能存储一个数据类型，我们称之为**
一、set的介绍
介绍：
set是按照一定次序存储元素的容器。
在 set 中，元素的 value 也标识它 (value 就是 key ，类型为 T) ，并且每个 value 必须是唯一的。set中的元素不能在容器中修改( 元素总是 const) ，但是可以从容器中插入或删除它们。
3.在内部， set 中的元素总是按照其内部比较对象 ( 类型比较 ) 所指示的特定严格弱排序准则进行 排序。
set容器通过 key 访问单个元素的速度通常比 unordered_set 容器慢，但它们允许根据顺序对子集进行直接迭代。
set在底层是用二叉搜索树 ( 红黑树 ) 实现的
set的使用：
1、 set的使用
定义：
set<类型> s;
迭代器：
set的迭代器的遍历顺序为中序遍历
begin ：返回set中起始位置元素的迭代器
end ：返回set中最后一个元素后面的迭代器
rbegin ：返回容器逆序的第一个元素的迭代器
rend ：返回容器逆序的最后一个元素的前一个位置的迭代器
set的函数
1、pair<iterator,bool> insert (const value_type& x ) 在set中插入元素x，实际插入的是<x, x>构成的键值对，如果插入成功，返回<该元素在set中的位置，true>,如果插入失败，说明x在set中已经存在返回<x在set中的位置，false>
2、void erase ( iterator position ) 删除set中position位置上的元素
3、size_type erase ( const key_type& x ) 删除set中值为x的元素，返回删除的元素的个数
4、void erase ( iterator first, iterator last ) 删除set中[first, last)区间中的元素
5、void swap (set<Key,Compare,Allocator>& st ) 交换set中的元素
6、iterator find ( const key_type& x ) const 返回set中值为x的元素的位置
7、size_type count ( const key_type& x ) const 返回set中值为x的元素的个数
set的使用：
#include <set>
#include<iostream>
using namespace std;
void TestSet()
{
// 用数组array中的元素构造set
int array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4,
6, 8, 0 };
set<int> s(array, array + sizeof(array) / sizeof(array[0]));
cout << s.size() << endl;
// 正向打印set中的元素，从打印结果中可以看出：set可去重
for (auto& e : s)
cout << e << " ";
cout << endl;
// 使用迭代器逆向打印set中的元素
for (auto it = s.rbegin(); it != s.rend(); ++it)
cout << *it << " ";
cout << endl;
// set中值为3的元素出现了几次
cout << s.count(3) << endl;
}
注意事项：
与 map/multimap 不同， map/multimap 中存储的是真正的键值对 <key, value> ， set 中只放value ，但在底层实际存放的是由 <value, value> 构成的键值对。
set 中插入元素时，只需要插入 value 即可，不需要构造键值对。
set 中的元素不可以重复 ( 因此可以使用 set 进行去重 ) 。
使用 set 的迭代器遍历 set 中的元素，可以得到有序序列
set 中的元素默认按照小于来比较
set 中查找某个元素，时间复杂度为： log2 n
set 中的元素不允许修改 ( 为什么 ? --- 麻烦 排序的维护，唯一性的维护，时间复杂度的维护)
set 中的底层使用二叉搜索树 ( 红黑树 ) 来实现。
二、map的介绍
介绍：
map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元 素。
在map中，键值key通常用于排序和唯一地标识元素，而值value中存储与此键值key关联 的内容。
键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类 型value_type绑定在一起，为其取别名称为pair
在内部，map中的元素总是按照键值key进行比较排序的。
map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序 对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
map通常被实现为二叉搜索树(平衡二叉搜索树(红黑树))。
迭代器
begin()和end() begin:首元素的位置，end最后一个元素的下一个位置
rbegin()和rend() 反向迭代器，rbegin在end位置，rend在begin位置，其++和–操作与begin和end操作移动相反
修改操作
1、pair insert ( const value_type& x ) 在map中插入键值对x，注意x是一个键值 对，返回值也是键值对：iterator代表新插入 元素的位置，bool代表释放插入成功
2、void erase ( iterator position )删除position位置上的元素
3、size_type erase ( const key_type& x )删除键值为x的元素
4、void erase ( iterator first, iterator last )删除[first, last)区间中的元素
5、const_iterator find ( const key_type& x ) const 在map中插入key为x的元素，找到返回该元 素的位置的const迭代器，否则返回end
6、size_type count ( const key_type& x ) const 返回key为x的键值在map中的个数，注意 map中key是唯一的，因此该函数的返回值 要么为0，要么为1，因此也可以用该函数来判断一个key是否在map中
下面是两个使用实例
可以用map来查找
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main() {
map<string, string> dict;
dict.insert(pair<string,string>("insert", "插入"));
dict.insert(pair<string, string>("erase", "删除"));
dict.insert(pair<string, string>("left", "左边"));
dict.insert(pair<string, string>("string", "字符串"));
string str;
while (cin >> str)
{
auto ret = dict.find(str);
if (ret!=dict.end())
{
cout <<ret->first <<":" << ret->second << endl;
}
else
{
cout << "单词拼写错误" << endl;
}
}
return 0;
}
我们可以用map来统计出现的次数，如下：
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main() {
string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" };
// 统计水果出现的次
map<string, int> countTree;
for (auto str : strs)
{
countTree[str]++;
}
for (auto m : countTree)
{
cout << m.first << ":" << m.second << endl;
}
return 0;
}
使用注意：
map中的的元素是键值对
map中的key是唯一的，并且不能修改
默认按照小于的方式对key进行比较
map中的元素如果用迭代器去遍历，可以得到一个有序的序列
map的底层为平衡搜索树(红黑树)，查找效率比较高O(log_2 N)
支持 [] 操作符，operator[] 中实际进行插入查找。
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在底层用二叉搜索树(红黑树)来实现
使用：
3.2.2 multimap的使用
multimap中的接口可以参考map，功能都是类似的。
注意：
multimap中的key是可以重复的。
multimap中的元素默认将key按照小于来比较
multimap中没有重载operator[]操作(思考下为什么?)。
使用时与map包含的头文件相同