一、set/multiset的使用

set是单一个key值的一个容器，其特点如下：
（1）key值不支持修改
（2）不允许插入相同的值，若要插入相同的值则需使用multiset
（3）底层使用红黑树
不支持修改的主要原因就是在于底层使用的是红黑树，我有一篇博客写的是红黑树的一个底层是没有平衡的二叉搜索树，在二叉搜索树中严格遵循每一棵树根节点的左子树必须小于根节点，右子树必须大于根节点，若修改则会破坏整个树的结构，导致此树没有任何意义。

1.1基本结构

在https://legacy.cplusplus.com/这个文档中对于set容器的结构如下表述：

整体设计为一个类模板，方便构造不同类型的set。
第一个模板参数T，就是key，控制整个set存储的类型；第二个模板参数Compare，是控制set容器的比较逻辑，一般不会指定参数，使用缺省值的情况居多；第三个模板参数Alloc，是容器自带的内存池，控制容器的分配和释放，一般不用管；

1.2构造函数

第一个是空构造，第二个是迭代器区间构造，第三个是拷贝构造，第四个涉及右值引用不说明，第五个是列表initializer_list构造，可以通过{ }形式进行一组值的直接构造。

代码演示：

 // 1.空构造
 std::set<int> s1;  // 构造一个没有任何元素对象s1

 // 2.迭代器区间构造
 std::vector<int> v = { 3,4,2,6,5,7,8,10,9 };
 std::set<int> s2(v.begin(), v.end());    // 不同容器但相同类型可以构造

 std::set<int> s3(s2.begin(), s2.end());  // 相同容器相同类型也可以构造

 // 3.拷贝构造
 std::set<int> s4(s3);     // 将s3深拷贝给给s4

 // 5.列表构造
 std::set<std::string> s5({ "苹果","香蕉","梨" });

注意：对于拷贝构造，建议是少用，因为set的拷贝涉及深拷贝，并且底层还是红黑树这么复杂的结构，它的拷贝构造性能上是远不如其他容器的拷贝构造的，若遇到必须使用拷贝的地方，可以注意一下是否可以使用引用，以减少拷贝负担。

1.3赋值运算符重载

第一个是赋值一个对象，第二个不谈，第三个是将列表赋值给给set对象。

代码演示：

// 1.赋值一个对象
std::set<std::string> s6 = s5;

// 3.赋值一个列表
std::set<std::string> s7 = { "苹果","香蕉","梨" };    // 对比构造当中的写法，这个写法更普遍一点

1.4迭代器的使用

这里只介绍普通迭代器，其他的迭代器都是在普通迭代器进行限制，并且使用方式也和普通迭代器类似。

代码演示：

// 此处演示set的普通迭代器演示，其余迭代器使用方式类似

// 初始化列表构造一个s集合
std::set<std::string> s = { "苹果","香蕉","梨","水蜜桃","西瓜" };

//std::set<std::string>::iterator it1 = s.begin();    
// 嫌迭代器类型太长可以使用auto代替
auto it1 = s.begin();
while (it1 != s.end())
{
    // set的迭代器都不支持修改
    // *it1 = 1;

    std::cout << *it1 << " ";
    it1++;
}

输出：梨 水蜜桃 苹果 西瓜 香蕉
注意，set的迭代器遍历最后的结果是一个升序序列，因为使用的中序遍历。

1.5常用方法的使用

(1)empty

empty方法的返回值是一个bool类型，意味着容器为空返回false，容器非空返回true。

代码演示：

// empty --- 判空
// 非空返回true，空返回false

std::set<std::string> s1;     // 空set集合
std::set<std::string> s2 = { "苹果","香蕉","梨","水蜜桃","西瓜" };    // 非空set集合

if (!s1.empty())
    std::cout << "set非空" << std::endl;
else
    std::cout << "set为空" << std::endl;    // s1输出"set为空"

if (!s2.empty())
    std::cout << "set非空" << std::endl;    // s2输出"set非空"
else
    std::cout << "set为空" << std::endl;

(2)size

size方法的返回值类型是一个typedef后的类型，原型是unsigned int，也就是size_t类型，是一个无符号整型，此方法用来计算容器中有多少个元素。

代码演示：

// size --- 计算容器元素个数
// 返回一个size_t类型的返回值

// 对s1，s2进行判断

std::cout << "s1的size：" << s1.size() << std::endl;       // 输出s1的size：0
std::cout << "s2的size：" << s2.size() << std::endl;       // 输出s2的size：5

(3)insert

insert方法中，第一个是直接插入一个值，第二个是在一个迭代器位置上插入值，第三个是插入一段迭代器区间。实际使用当中，使用最多的也就只有第一个，其他的使用频率不高。
注意，第一个single element的返回值是pair类型，这个其实就是一个结构体类型（叫为类也行）里面封装有key和value，在后续map里会单独讲解它。

代码演示：

// insert --- 插入
// 这里只演示直接插入一个值的用法，其他的用法使用频率不高

std::set<int> s = { 3,2,5,6,4,9,7,8,1,10 };

for (auto e : s)
    std::cout << e << " ";      // 输出1,2,3,4,5,6,7,8,9,10
std::cout << std::endl;

s.insert(11);
s.insert(-1);

for (auto e : s)
    std::cout << e << " ";      // 输出-1,1,2,3,4,5,6,7,8,9,10,11

(4)erase

erase方法中第一个是删除一个迭代器位置的值，第二个是直接删除一个给定的值，第三个是删除一段迭代器区间，同样也就第二个使用的最多。
注意第二个用法的返回值类型是size_t类型，基于此可以简易进行是否删除成功的判断，并且这个返回类型是服务multiset的，可以返回对象中有多少个重复的元素。

代码演示：

// erase --- 删除
// 这里只演示删除一个给定值的用法

std::set<int> s = { 3,2,5,6,4,9,7,8,1,10 };

if (s.erase(10))   // 删除s中存在的值10
    std::cout << "删除成功" << std::endl;            // 这里输出删除成功
else
    std::cout << "删除失败，没有这个值" << std::endl;

if (s.erase(100))   // 删除s中不存在的值100
    std::cout << "删除成功" << std::endl;
else
    std::cout << "删除失败，没有这个值" << std::endl;  // 这里输出删除失败

(5)find

find方法返回值是一个迭代器位置。

代码演示：

// find --- 查找
// 此方法返回值是一个迭代器

std::set<int> s = { 3,2,5,6,4,9,7,8,1,10 };

auto retit1 = s.find(3);
if (retit1 != s.end())
{
    std::cout << "找到了" << std::endl;         // 查找3这里输出找到了
}
else
{
    std::cout << "没找到" << std::endl;
}

auto retit2 = s.find(100);
if (retit2 != s.end())
{
    std::cout << "找到了" << std::endl;
}
else
{
    std::cout << "没找到" << std::endl;         // 查找100这里输出没找到
}

(6)count

count方法返回的是一个size_t类型的返回值，传入参数是给定的值，其实用法上和find是相似的，给定值存在返回1，不存在返回0。

代码演示：

// count --- 功能上来说也是查找
// 此方法返回值是一个size_t类型的对象
// 存在返回1，不存在返回0

std::set<int> s = { 3,2,5,6,4,9,7,8,1,10 };

size_t size = s.count(3);    // 这里size = 1

if (s.count(3))
{
    std::cout << "找到了" << std::endl;         // 查找3这里输出找到了
}
else
{
    std::cout << "没找到" << std::endl;
}

if (s.count(100))
{
    std::cout << "找到了" << std::endl;
}
else
{
    std::cout << "没找到" << std::endl;         // 查找100这里输出没找到
}

swap，clear方法就不再演示了，使用方式和之前学习过的容器没有太大差别。

(7)lower_bound / upper_bound

这两个都是返回迭代器对象的方法：

lower_bound返回的是第一个不小于(>=)给定值的迭代器
当值存在时，返回当前值位置的迭代器
当值不存在时，返回第一个大于当前值位置的迭代器
当所有值都小于给定值时，返回end

upper_bound返回的是第一个大于(>)给定值的迭代器
当值存在时，返回大于当前位置第一个值的迭代器
当值不存在时，返回end

代码演示：

// 此处演示lower_bound和upper_bound

std::set<int> s = { 2,4,3,5,6,1,8,7,9,10 };

// [3,6]
auto retit1 = s.lower_bound(3);
// lower_bound返回3位置的迭代器
auto retit2 = s.upper_bound(6);
// upper_bound返回第一个大于6位置的迭代器，也就是7位置的迭代器

for (auto it1 = retit1; it1 != retit2; it1++)
{
    std::cout << *it1 << " ";    // 输出区间为[3,6]，输出迭代器区间是左闭右开即[3,7)
}
std::cout << std::endl;

s.erase(retit1, retit2);            // 删除区间[3,6]

for (auto e : s)
{
    std::cout << e << " ";       // 输出：1,2,7,8,9,10
}

二、map的使用

map的使用介绍和set的大差不差，不过在map这里要将pair这个类结构，不同于set的单key结构，map是key-value的键值对形式存储元素的。

2.1pair类型

pair类型是一个类模板，因为map是键值对的形式存储元素，在迭代器遍历map对象，访问其中的元素的时候，会将其拷贝给迭代器对象，但是map是多参数，不能一次返回多个单一参数，所以map底层将元素封装成一个叫pair类型的类模板，这样在访问元素的时候就不会出现上述那样的情况了，并且这个pair类型不止运用在存储元素，后面介绍到insert方法的时候，他还会再出现的。

(1)成员变量

所以我们要访问key时，就是访问上述的first成员；访问value时，就是访问上述的second成员。

(2)make_pair

在这个类型里只学习这一个make_pair构造pair对象的方法。

本身就只是一个依靠传递过来的参数去构造了一个pair类型对象出来的方法。

代码演示：

// 先介绍pair类型
// pair是自定义的一个结构，其成员有两个，first，scen
//typedef pair<const Key, T> value_type;

std::pair<std::string, std::string> p1;
std::pair<std::string, std::string> p2("string", "字符串"); 
std::pair<std::string, std::string> p3("bool", "布尔值");
std::pair<std::string, std::string> p4("left", "左边");
std::pair<std::string, std::string> p5("right", "右边");

std::cout << "key: " << p2.first << " " << "value: " << p2.second << std::endl;
// 输出key: string value: 字符串

2.2基本结构

map和set的结构非常相似，第一个模板参数就是key，第二个就是value(这上面定义的是T)，剩下的和set是一模一样的。

2.3构造函数

同样不关注右值引用相关的第四个构造方式，第一个构造一个空的map对象，第二个通过一段迭代器区间构造map对象，第三个拷贝构造，第五个是初始化列表构造，在map这里第五个构造用的特别的多。

代码演示：

// 构造函数

// 1.空构造
std::map<int, int> m1;

// 2.迭代器区间构造
// 注意：map对象需要的是pair类型的对象
std::vector<std::pair<int, int>> v = { {1,100},{2,200},{3,300} };      // 这里使用了多参数的隐式类型转换
std::map<int, int> m2(v.begin(), v.end());

// 3.拷贝构造
std::map<int, int> m3(m2);

// 5.初始化列表构造
// 使用上面构造的一堆pair对象进行构造
std::map<std::string, std::string> m4 = { p1,p2,p3,p4,p5 };             // 但是一般不会这样表示map的构造

// 更多的是结合隐式类型转换，直接在{ }中进行构造，省略了显示写pair构造的过程
std::map<std::string, std::string> m5 = { {"string", "字符串"},{"bool", "布尔值"},{"left", "左边"},{"right", "右边"} };

2.4访问遍历相关

(1)迭代器

map实现的是双向迭代器，并且key不支持修改，value支持修改。

std::map<std::string, std::string> m = { {"string", "字符串"},{"bool", "布尔值"},{"left", "左边"},{"right", "右边"} };

// 1.迭代器
std::map<std::string, std::string>::iterator it1 = m.begin();
while (it1 != m.end())
{
	// key不支持修改
	// it1->first = "ddd";

	// value支持修改
	// it1->second = "ooo";

	std::cout << it1->first << ":" << it1->second << std::endl;  // 或者(*it1).first访问
	it1++;
}

(2)operator[]

// 2.operator[] --- 单一输出key对应的value
for (auto& e : m)
{
	std::cout << m[e.first] << std::endl;
}

std::cout << std::endl;

(3)结构化绑定

C++17支持一个叫结构化绑定的一种语法，也就是将map对象m赋值给给自定义的[k,v]结构，k对应key，v对应value。

//3.结构化绑定 --- C++17
for (auto& [k, v] : m)
{
	std::cout << k << ":" << v << std::endl;
}

上述三种遍历方式运行结果如下：

2.5常用方法/重载

map的常用方法就不再和set一样一一列举了，使用方式都和set是类似的，这里专门去将有差别的方法/重载。

(1)insert

正常看这就是一个插入一个pair类型的数据，但是结合返回值，它的返回值也是一个pair，但是和我们在构造那里将的pair有不一样的地方，这里是一个迭代器对象和bool的组合，接下来让我仔细去讲讲这个insert方法。

首先我们正常插入map对象中没有的key-value，就和其他容器的insert方法是一样的，正常插入；当插入map中存在的key时，不会进行插入，此时返回值pair对象的second存储的就是false，不允许进行插入操作，下面的代码进行了演示。

代码演示：

// insert方法

std::map<int, int> m = { {1,100},{2,200},{3,300} };

// 正常插入使用
// 这里需要插入一个pair类型的数据
// 要么显示构造一个pair类型的对象，去插入
// 要么通过make_pair方法，隐去类型，构造一个pair类型的对象
// 最推荐的还是使用隐式类型转换，简单，方便

std::pair<int, int> p(4, 400);       // 显示构造
m.insert(p);

m.insert(std::make_pair(5, 500));    // make_pair方法构造

m.insert({ 6,600 });                 // 隐式类型转换

// 还可以判断插入是否成功，因为key具有唯一性

if ((m.insert({ 6,000 }).second == true))
{
	std::cout << "插入成功" << std::endl;
}
else if ((m.insert({ 6,000 }).second == false))
{
	// 插入失败不会覆盖原来的value值
	std::cout << "插入失败，key值已存在" << std::endl;
	std::cout << "实际的value = " << (m.insert({ 6,000 }).first)->second << std::endl;
}

(2)operator[]

map也支持[]的使用，不过和vector这些连续存储结构的不同。

这个重载的调用等同于：

解读一下这一串长代码：
首先调用这个函数的对象调用insert函数，使用make_pair生成一个pair类型的k-value的对象，去插入到调用这个函数的对象中去，我们知道insert是有返回值的，.first就是访问插入位置的iterator，*iterator解引用拿到这个位置的数据是pair类型的k-value，.second访问的就是value。

用法：
(1)当访问存在的key值时，返回这个key对应的value值
(2)当访问存在的key值时，并且也对其进行重新赋值，则key对应的value值会更新成新赋值的value。
(3)当访问不存在的key值时，没有对其进行赋值，会根据map的参数模板类型默认初始化value
(4)当访问不存在的key值时，且对其进行赋值，就是一个插入功能

代码演示：

// 此处演示operator[]

std::map<std::string, std::string> m = { {"bool", "布尔值"},{"left", "左边"},{"right", "右边"} };

// 传入存在的key值
std::cout << m["bool"] << std::endl;    // 访问对应的value值，打印布尔值

// 传入存在的key值，也传新的value
m["bool"] = "xxx";         // 功能是修改key的value值

// 传入不存在的key值
m["array"] = "数组";       // 功能类似与insert插入
m["string"];              // 不给定value时会根据map的模板类型默认初始化value，这里就是个空串

// 范围for只遍历value
for (auto& e : m)
{
	std::cout << m[e.first] << std::endl;
}

//结构化绑定C++17
for (auto& [k, v] : m)
{
	std::cout << m[k] << std::endl;
}

调试结果：