【C++】set/map（重点解析）

目录

一、关联式容器和序列式容器

二、C++中的键值对——pair 

1.概念

2.定义

3.构造pair

三.set

1.construct构造

2.iterator迭代器

3.insert插入

4.erase删除 

5.find查找

6.lower_bound和upper_bound

7.count

四.multiset

五.map

1.insert

2.operator[]

---

一、关联式容器和序列式容器

关联式容器：如其名，关联式表现在其基于键值对(<key,value>结构)的概念，通过键(key)来唯一标识元素，主要包括set、map、multiset、multimap等，它具有如下特征：

• 内部使用二叉搜索树（通常是红黑树）或类似的数据结构来保持元素的有序性
• 插入删除查找等操作的平均时间复杂度是O(logN)

序列式容器： 基于线性结构，元素在容器中的位取决于插入的顺序，主要包括vector、list、deque、array等，插入删除查找的平均时间复杂度因容器而异，最坏情况下为O(N)

---

二、C++中的键值对——pair 

1.概念

键值是一种数据结构，通常用于表示关联关系，由两部分组成，键（Key）和值（Value），两者紧密关联，例如名字——学号的对应模式，此时Key就为学号(int类型)，Value为名字(String类型)，排序以学号（键）为基准，同时每一个键都唯一对应一个值。

2.定义

pair是C++标准库中提供的一个简单实现，它包含在头文件<utility>中，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.构造pair

事实上，若你想构造一个pair<int,string>类，可以有以下三种方法：

auto p1 = pair<int, string>(1, "ysh");
auto p2 = make_pair(2, "zyh");
auto p3 = pair<int, string>{ 3,"xx" };

在一个存储类型为<int,string>键值对的map中插入数据时，就可以这样写：

map<int, string> m;
m.insert(pair<int,string>(1,"ysh"));
m.insert(make_pair(2, "zyh"));
m.insert({ 3,"xx" });
//毫无疑问，直接用{}构造是最简单的

---

三.set

set是按照一定次序储存元素的容器，它存储的就是单一的元素，当然也可以看作key和value是相同的，都是类型T（这是方便和map对比，毕竟都是基于键值对的容器），特性如下：

• 每个value必须是唯一的，这对应了set的去重功能
• 底层是二叉搜索树（红黑树）实现的，对应了O(logN)的效率

1.construct构造

一般使用迭代器区间构造，如下使用vector迭代器来进行构造

set<int> s1;
vector<int> v = { 1,2,3,4,5 };
set<int> s2(v.begin(), v.end());//利用迭代区间
set<int> s3 = s2;//拷贝构造

2.iterator迭代器

由于set的底层是二叉搜索树，因此遍历set所使用的迭代器也是遵循中序遍历的，二叉搜索树的中序遍历是有序的，则set的begin()返回迭代器就是其中最小的值，而end()则是对应最大值。

同时还有一个需要注意的小点，二叉搜索树实际是三叉树，树的节点间通过指针相连，那么这里而言，删除一个节点，不会使其他节点的迭代器失效。类似不会失效的有List,但像vector这种顺序结构就会导致失效。

3.insert插入

set是不允许插入重复的键值的，因此插入有可能会失败， 同时还会返回对应位置迭代器，因此这里返回值为pair<iterator,bool>类型

• 如果插入值不存在，则插入成功，返回指向该位置的迭代器和true
• 如果插入值已经存在，则插入失败，返回指向已存在元素位置的迭代器和false

相同的值无法被插入，因此set可以应用于去重操作

4.erase删除 

需要说明的是迭代器区间删除遵循的原则是 左闭右开 ， 也就是说first对应的会被删除，而last对应的不会被删除，这里可以配合后续要讲的lower_bound和upper_bound使用

5.find查找

find用于在set中查找指定键值的元素，并返回指向该元素的迭代器，若元素不存在，则返回end()

值得注意的是std中本身也有find查找函数，不过该查找是根据迭代器遍历查找，也就是说其查找的效率是O（N），而set自带量身定制的find，该find根据二叉搜索树的规则进行查找，能达到O(logN)的效率，使用定制的显然更好

 6.lower_bound和upper_bound

lower_bound返回的是大于等于参数的迭代器，而upper返回的是大于该参数的迭代器，注意不是一个大于一个小于，区别仅仅是有无取等，此两函数常用于区间的删除，例如：

vector<int> v{ 10,20,30,40,50,60,70,80,90,100 };
set<int> s(v.begin(), v.end());
//lower_bound找＞=30的，即30
auto itlow = s.lower_bound(30);
//upper_bound找>50的，即60
auto itup = s.upper_bound(50);
//删除遵循左闭右开，即删除30,40,50
//60是开区间不用删除
s.erase(itlow, itup);
for (auto e : s)
{cout << e << " ";
}
cout << endl;

 7.count

count实际是用来统计该值在set中出现的次数的，但set不允许插入重复的键值，因此只有可能有0和1两种返回值，计数更多用于multiset中，不过根据该特性，倒是能设计出一个很简单的检验一个值是否存在于set中，如下操作：

---

四.multiset

multiset与set唯一的不同点就在于其multi前缀上，这表明multiset是允许键值重复的，即可以包含多个键值相同的元素。

其余操作和set别无二致，不过需要注意的是erase一个有多个节点的值时，会一次性将所有节点全部删除，如下：

---

五.map

map同样作为关联式容器，这就是标准的存储键值对的容器了，它按照特定的次序（按照Key来比较）储存由键Key和值value组合而成的元素。

map本身和set相差不多，接下来只提及一些差异点。

1.insert

前文在pair讲究中就已讲到，插入键值对有很多方法，有以下三种，不过还是用{}构造最简单

map<string, string> m1;//空的m1.insert(pair<string, string>("sort", "排序"));//匿名对象
m1.insert(make_pair("apple", "苹果"));//使用make_pair函数
m1.insert({ "apple", "苹果" });// C++11 多参数隐式类型转换(构造函数支持)

其实在insert的官方讲解中就有一句，还可以使用[]来进行插入，接下来就进行[]的讲解 

2.operator[]

方括号[] 有两种用法

读取或插入元素时

• 若指定的键存在于map中，则返回与该键相关联的值value的引用
• 若指定的键不存在map中，则会插入一个新的键值对，其键key就为[]内部的key，而键则为默认构造对应的默认值，并返回该默认值的引用

 因此，方括号不仅是用于读取，还能进行插入操作

map<string, string> m1;//空的m1.insert(pair<string, string>("sort", "排序"));
m1.insert(make_pair("apple", "苹果"));
m1.insert({ "left", "左边" });
for (auto& kv : m1)
{cout << kv.first << ":" << kv.second << " ";
}
cout << endl;m1["right"];//right不存在，这是插入一个right（key）
m1["apple"] = "青苹果";//由于apple已经存在，这里是进行修改for (auto& kv : m1)
{cout << kv.first << ":" << kv.second << " ";
}
cout << endl;

最后，multimap和map和关系 与 multiset和set关系一致，这里就不多赘述了，本文结束