当前位置：首页 > ds >正文

CPP学习之map和set

ds 2025/8/30 11:37:28

1. 关联式容器

在之前博客中我们提到过序列式容器：vector, list, deque, forward_list等，其底层都是线性数据结构。
关联式容器存储的是键值对–<key, value>，与序列式容器仅存储值–key不一样，在数据检索时比序列式容器效率更高。

2. 键值对

键值对<key, value>，key与value形成映射关系，比如建立英汉字典，key为英文单词，对应的value就是中文意思。

SGI-STL中关于键值对的定义：

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)
{}
};

3. 树形结构的关联式容器

树形结构的关联式容器有以下四种：set、multiset、map、multiset。
这四种容器的底层数据结构是平衡搜索树(红黑树)，元素的序列是有序的。

3.1 set

3.1.1 容器性质：

按照次序存储；
set的key就是value（<value, value>），而且每个value都是唯一的，容器内的元素不能修改（元素都是const类型）,但可以进行插入和删除；
元素内部按照特定严格弱排序准则进行排序；
set底层数据结构是红黑树；
set内元素不可重复；
容器内查找元素的时间复杂度为O(logN)；
用set的迭代器迭代容器，得到的是有序序列。

注意：multiset可以存储相同的元素，不会去重。

3.1.2 使用：

set容器相关功能具体请参考：set -C++ Reference

// 各容器中，涉及到区间的函数，操作的都是左闭右开
// set 和 multiset，一个排序去重，一个排序不去重
// 在multiset中，find找的是中序第一个，其count的使用比set的count更有意义
// set的iterator都是const修饰过的，这样是为了防止内部树结构被破坏void test_1()
{set<int> s1; //排序+去重s1.insert(1);s1.insert(2);s1.insert(3);s1.insert(4);if (s1.find(2) != s1.end()) //set找内容方式1{cout << "找到了" << endl;}if (s1.count(3)) //set找内容方式2{cout << "找到了" << endl;}set<int>::iterator sit = s1.begin();while (sit != s1.end()){cout << *(sit++) << " ";}cout << endl;}void test_2()
{int arr[] = { 1,2,3,4,5,6,7,8,9 };set<int> s1;for (auto e : arr){s1.insert(e * 10);}for (auto e : s1){cout << e << " ";}cout << endl;set<int>::iterator itlow, itup;//itlow和itup组成左闭右开区间itlow = s1.lower_bound(30); //此处是30，>=号itup = s1.upper_bound(70); //此处是80，因为是>号s1.erase(itlow, itup);for (auto e : s1){cout << e << " "; //80没被删除，这就是左闭右开}cout << endl;s1.insert(50);s1.insert(50);s1.insert(50);s1.insert(50);pair<set<int>::iterator, set<int>::iterator> ret;ret = s1.equal_range(50); //pair存两个迭代器，第一个指向最后的50，第二个指向80set<int>::iterator itlow_bound = ret.first;auto itup_bound = ret.second;cout << *itlow_bound << endl;cout << *itup_bound << endl;}void test_3()
{int arr[] = { 1,2,3,4,5,6,7,8,9 };multiset<int> s1; //排序不去重for (auto e : arr){s1.insert(e * 10);}s1.insert(50);s1.insert(50);s1.insert(50);for (auto e : s1){cout << e << " ";}cout << endl;pair<multiset<int>::iterator, multiset<int>::iterator> ret;ret = s1.equal_range(50); //存放了multiset里指向第一个50和第一个60的迭代器auto itlow_bound = ret.first;auto itup_bound = ret.second;cout << *itlow_bound << endl;cout << *itup_bound << endl;s1.erase(itlow_bound, itup_bound); //删除s1内所有的50for (auto e : s1){cout << e << " ";}cout << endl;}

3.2 map

3.2.1 容器性质

map是存储键值对的容器<key, value>;
key和value的类型可以不同，key与value成映射关系。为了将键值对这种元素存入map中，我们使用结构体pair将键值对绑定在一起；
在容器内，元素按照key进行排序，但同样地不允许存入相同的key，不同key可以存入相同的value；
map支持下标访问符：value == map[key]，其中value与key是绑定的；
map通常被实现为搜索二叉树，更准确的说是红黑树。

注意：multiset可以存储相同的键，不会去重。

3.2.2 使用

map容器相关功能具体请参考：map - C++ Reference

// 关于map
// C++11之后支持多参数的构造函数的隐式类型转换
// 因为C++返回参数只有1个，所以我们可以用结构体来包含多参数然后返回，map存储的内容就是一个个这样的结构体
// 键值对，用make_pair或者隐式类型转换构造出键值对结构存入map中最为方便
// first为键，second为值，键不可修改，值可以；插入一个键相同，但值不相同，则不会插入进去，而且值也不修改
// map最关键的函数：[]重载，既可以插入数据，也可以修改数据，还能访问数据
void test_4()
{map<string, string> dict; //键值对dict.insert({ "apple", "苹果" }); //隐式类型转换，C++11后支持dict.insert(make_pair("peach", "桃子")); //C++98后支持,建议用这种方式pair<string, string> kv = { "banana", "香蕉" };dict.insert(kv);dict.insert(pair<string, string>("melon", "甜瓜"));map<string, string>::iterator it = dict.begin();while (it != dict.end()){cout << it->first << " " << it->second << endl;it++;}}void test_5()
{map<string, int> count_map;string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };for (auto& e : arr){auto it = count_map.find(e); //找到就返回对应迭代器，找不到就返回count_map的endif (it == count_map.end()){count_map.insert(make_pair(e, 1));}else{it->second++;}}//for (auto& e : arr)//{//	count_map[e]++; //map的中括号可搜索内容并返回映射值//}for (auto& e : count_map){cout << e.first << ":" << e.second << endl;}
}