1.序列式、关联式容器

2.键值对

3.set

3.1set的简介

3.2set的常用函数

4.multiset

5.map

5.1map的简介

5.2map的常用函数

6.multimap

7.练习题

1.序列式、关联式容器

vector、deque、list、forward_list、array等是C++STL中的序列式容器

其核心特性是 元素按插入顺序存储，支持高效的顺序访问或随机访问

set、map、multiset、multimap等是C++STL中的关联式容器

其核心特性是 元素通过键（key）进行排序和快速查找，而不是像序列式容器那样按插入顺序存储

2.键值对

键值对是一种数据结构，由唯一的键 Key 和对应的值 Value 组成
键 Key ：唯一标识符，用于快速定位数据且必须是不可变类型(如字符串、数字、元组等)

值 Value ：存储的实际数据，可以是任意类型(字符串、数字、列表、字典等)

映射关系：一个键对应一个值，形成 key: value 的结构

键值对主要通过 标准模板库（STL） 中的 std::pair 和关联容器（如 std::map、std::unordered_map）实现，下面是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){}};

容器更详细的使用请参考cplusplus.com - The C++ Resources Network

3.set

3.1set的简介

set容器实际上就是二叉搜索树应用中说的 K模型

T: set中存放元素的类型(实际在底层存储的键值对)

Compare(仿函数)：set中元素默认按照小于来比较

Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理(后续讲解)

3.2set的常用函数

set自带默认构造、迭代器区间构造、拷贝构造等成员函数

(1)insert

set支持单个元素插入、在特定位置后插入以及迭代器区间范围内元素的插入

重点讲讲单个元素插入的返回值

插入元素不在set中，返回pair<插入元素在set中的迭代器，true>

插入元素在set中，返回pair<插入元素在set中的迭代器，false>

从上面我们可以得出结论

set中的每个元素只能出现一次(重复插入会被忽略)

(2)

set 是基于红黑树（一种平衡二叉搜索树）实现的，遍历方式是中序遍历且由于元素默认是按小于比较的，迭代器打印序列就是升序序列

插入元素Key不可修改

(3)find

//查找高度次
s.find(5);
//暴力查找，最多N次
find(s.begin(), s.end(), 5);

set中的find函数是根据元素大小比较查找的，最多查找树高度次

算法库中的find函数是遍历查找的，最多查找元素个数次

两者:找到了，返回该位置的迭代器，找不到返回 end()

(4)count

set 中的count 也可以用来查找，返回的是元素个数

找到了返回1，找不到返回0

	if (s.count(5)){cout << "找到了" << endl;}

(5)erase

set支持特定位置的删除、特定元素的删除以及迭代器区间范围内元素的删除

特定位置的删除，传入的 position 应属于[ first，last )，否则系统会崩溃

正确做法
	auto pos = s.find(50);//不能越界访问	if (pos != s.end())s.erase(pos);
特定元素的删除，函数返回删除的数量，这里当然是0或1啦

迭代器区间范围内元素的删除，范围一定要准确，否则程序会崩溃或出现未定义行为

(6)lower_bound

iterator lower_bound (const value_type& val) const;

该函数返回大于等于val的第一个元素的迭代器，找不到时返回 end()

(7)upper_bound

iterator upper_bound (const value_type& val) const;

该函数返回大于val 的第一个元素的迭代器，找不到时返回 end()

set与multiset使用一致

(8)equal_range

pair<iterator,iterator> equal_range (const value_type& val) const;

pair.fisrt 就是 lower_bound 的返回值

pair.second 就是 upper_bound 的返回值

set与multiset使用一致

4.multiset

multiset与set的最大区别就是 multiset可以存储多个相同大小的元素

multiset的插入、查找、删除等与set类似，这里不再赘述

5.map

5.1map的简介

set容器实际上就是二叉搜索树应用中说的 KV模型

key: 键值对中key的类型
T：键值对中value的类型
Compare(仿函数): 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)
Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的
空间配置器(后续讲解)
注意：在使用map时，需要包含头文件。

5.2map的常用函数

map自带默认构造、迭代器区间构造、拷贝构造等成员函数

(1)insert

map插入的是一个键值对pair

map支持单个pair插入、在特定位置后插入以及迭代器区间范围内pair的插入

重点讲讲单个pair插入的返回值

插入pair的pair.fistr不在map中，返回一个键值对pair<插入pair在map中的迭代器，true>

插入pair的pair.fistr在map中，返回一个键值对pair<插入pair在map中的迭代器，false>

map中存储的是键值对pair，且pair.first均不相同

map<string, string> dict;
pair<string, string> kv("insert", "插入");
dict.insert(kv);
dict.insert(pair<string, string>("copy", "复制"));
dict.insert(make_pair("right", "右边"));
dict.insert({ "pig", "猪" });

以上4中方式都可以完成插入:有名键值对、匿名键值对、调用函数创建键值对、多参数构造函数创建键值对(C++11)

template <class T1,class T2>pair<T1,T2> make_pair (T1 x, T2 y){return ( pair<T1,T2>(x,y) );}

make_pair 函数通常可成为内联函数，消耗较小

(2)

map 是基于红黑树（一种平衡二叉搜索树）实现的，遍历方式是中序遍历且由于元素默认是按小于比较的(比较的是键值对中的键值Key，即第一个元素)，迭代器打印序列就是升序序列

()map的其余函数与set类似，这里不再赘述，下面详解map的operator[]函数

函数的类似实现

value& operator[](const Key& x)
{auto ret = insert(make_pair(x, value());return (ret.first)->second;
}

ret接收键值对<x，value()>插入的返回值：

如果x不在map中，使用value的默认构造与x组成键值对并插入

如果x在map中，不插入

ret：<在map中指向x所在键值对的迭代器，true(插入成功)\false(插入失败)>

(ret.first)->second就是x所在键值对中的value

这样 [] 就可以实现插入和修改的功能