map和set的使用

关联式容器

在学习关联式容器之前，我们学习过的容器有vector、list、deque…这些容器称为序列式容器，单纯的存储数据存储的数据没有关联性。

即将学习的map 和set属于关联式容器，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高。

根据应用场景的不桶，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。下面一依次介绍每一个容器。

set

概述

关于set的文档介绍

set模板结构：

template < class T,                        // set::key_type/value_type
           class Compare = less<T>,        // set::key_compare/value_compare
           class Alloc = allocator<T>      // set::allocator_type
           > class set;

T: set中存放元素的类型，实际在底层存储<value, value>的键值对。 Compare：set中元素默认按照小于来比较 Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理

set简单使用

set的功能：1、实现搜索（key模型）2、排序+去重 另外set不允许修改。

insert+迭代器遍历

拷贝构造

1、空的set

2、迭代器区间构造（可以是其他容器的迭代器）

erase

find

返回对应的迭代器

在这里插入图片描述

find的就是去set容器中找到对应键值并返回他对应的迭代器，如果找不到，就会返回end( )迭代器

multiset

概述

关于multiset文档介绍

模板参数：

template < class T,                        // multiset::key_type/value_type
           class Compare = less<T>,        // multiset::key_compare/value_compare
           class Alloc = allocator<T> >    // multiset::allocator_type
           > class multiset;

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在底层用二叉搜索树(红黑树)来实现。

注意：multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重复的。

简单使用

insert

multiset允许冗余，而且完成排序功能，并且可以快速完成查找功能。

find

multiset中，相等值可以在左边 也可以在右边，看具体实现，find默认查找的是中序第一个。

这就说明了他找到的是第一个1，而搜索树的迭代器本身是利用中序去实现的，所以多个key的情况，返回的是中序的第一个key。

map

关于map文档介绍

模板结构；

template < class Key,                                     // map::key_type
           class T,                                       // map::mapped_type
           class Compare = less<Key>,                     // map::key_compare
           class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
           > class map;

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

1. map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
2. 在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:typedef pair<const key, T> value_type;
3. 在内部，map中的元素总是按照键值key进行比较排序的。
4. map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
5. map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
6. map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。

map 的简单使用

insert

在这里插入图片描述

void test_map1()
{
	map<string, string> dict;
	pair<string, string> kv1("sort", "排序");
	dict.insert(kv1); //有名对象
	dict.insert(pair<string, string>("left", "左边")); //匿名对象
	dict.insert(make_pair("right", "右边"));
	//隐式类型转换
	pair<string, string> kv2 = { "string","字符串" };
	dict.insert({ "string","字符串" }); 

}

map的迭代器

遍历：

范围for：

注意：iterator遍历时：key值不能修改，value值可以修改；const_iterator遍历时，key和value都不能修改。

erase

• 删除指定迭代器位置的键值对
• 删除键值为k的键值对，返回是否删除成功
• 删除一段迭代器区间。

find

在返回对应的迭代器，不在返回end

统计水果出现的次数：

count

给定一个key值，返回个数

重载operator[]

给key值，返回对应的value 相当于：(*((this->insert(make_pair(k,mapped_type()))).first)).second

key存在，插入失败，返回pair<存在key所在节点的迭代器，false> key不存在，插入成功，返回pair<新插入key所在节点的迭代器，true>

void test_map3()
{
	map<string, string> dict;
	dict.insert({ "string","字符串" });
	//插入
	dict["right"];
	//插入+修改
	dict["left"] = "左边";

	//“查找”
	cout << dict["string"] << endl;
	//修改
	dict["right"] = "右边";
}

[]给一个key，返回key对应的value的引用。

multimap

关于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在底层用二叉搜索树(红黑树)来实现。

注意：multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重复的