map和set

? ? ? ? C++中有各种容器，其中有一种名为关联式容器，通过键值对的方式来记录对象，其中map和set就是经典的关联式容器，它们在数据的检索时的效率比序列式容器更高。

键值对

? ? ? ? 是一种表示具有一一对应关系的数据结构，一般包含 key 和 value 两个成员，key 表示键值，value 表示与 key 对应的信息，现实中的英汉互译字典就使用了键值对的结构。

树型结构的关联式容器

? ? ? ? 在STL中，STL实现了两种不同结构的关联式容器：树型和哈希式结构，其中树型结构的关联式容器共有四种：map,set,multimap 和 multiset 四种。

? ? ? ??它们的共同点是底层采用的红黑树的结构，容器内是一种有序的结构。

set

set介绍

• set是按一定顺序存储元素的容器
• 在set中，元素value也用来标示它自己（key是value，值也是value），并且value都是唯一的，set不能修改元素，但是能够插入或者删除它们
• 在内部，set按照元素对象所指定的严格排序标准来进行排序
• set 通过 key 来访问元素的速度比 unordered_set 要慢，但他们允许按顺序直接对元素迭代
• set 在底层采用红黑数实现的

? ? ? ? 相比于map，set 只用value作为键值对，可以视作 <value ,value> 构成的键值对，因此set插入元素的时候不用构造键值对。

? ? ? ? 此外，set 不允许重复的元素存在，可以使用set 进行去重。

? ? ? ? set底层默认采用从小到大排序，因而迭代set的元素能得到一个有序序列。

set的构造

• set 的构造和大多数容器构造一样，可以拷贝，可以构造一个空set。
• set 的构造的第二个参数 comp 一般有默认的缺省参数，即 set 将数据从小到大排序时采用的函数。我们可以通过修改这个参数来使 set 从大到小排序。
• 当 set 的 value 类型是我们自定义类型时，这个 comp 也需要我们自己传入进去，一般是函数指针或者仿函数的形式。
• alloc 是STL提供的一个空间配置器，用来管理 set 的空间

set的迭代器和容量函数

这些函数和迭代器的使用方式和之前的容器都一样，因此不再赘述。

set的修改

这里面只有emplace和emplace_hint需要了解一下

emplace

这个函数返回一个 pair 类型，pair 的 first 为 iterator，seconde 为 bool 类型。

而且插入数据时不需要构建一个pair，内部会通过传入数据自动构建一个pair然后插入到set中。

不过当 set 中没有这个数据时，emplace 返回的 pair 的 first 是指向这个数据位置的迭代器，seconde 值为1，而有这个数据时，返回的 pair?的 first 是指向这个数据位置的迭代器，seconde 值为0；

#include<set>
#include<string>
#include<iostream>

using namespace std;

int main()
{
	set<string> s;
	pair<set<string>::iterator, bool> is = s.emplace("abcd");
	cout << is.first->c_str() << " : " << is.second << endl;
	 is = s.emplace("abcd");
	cout << is.first->c_str() << " : " << is.second << endl;
	return 0;
}

?

emplace_hint

#include<set>
#include<string>
#include<iostream>

using namespace std;

int main()
{
	set<string> s;
	set<string>::iterator is = s.emplace_hint(s.begin(),"abcd");
	cout << is->c_str() << endl;
	is = s.emplace_hint(s.begin(),"abcd");
	cout << is->c_str() << endl;

	return 0;
}

?

而这个函数只会返回一个指向插入数据的迭代器，并且我们可以指定插入的位置。

不过由于set需要保持顺序，因此插入的数据不一定在我们指定的位置。?

set的操作

find函数能够找到对应数据的迭代器。

count返回key对应值的个数，不过set的key和value相同，因此这里返回的不是0就是1.?

map

map介绍

• map是一个关联式容器，按特定的次序存储键值对
• key用来标示元素，value则是与key对应的内容，二者一起称为 pair
• map内部通过key来进行排序
• map访问单个元素速度慢与unordered_map，但是可以通过顺序直接迭代元素
• map支持下标访问，在 [] 中放入key，可以得到对应的value
• map底层为红黑树

map的模版参数类型

?

• ?key：键值对中key的类型
• value：键值对中value的类型
• Compare：map元素排序时采用的比较函数，一般是按小于比较，当Key和T是自定义类型时，这个比较函数需要我们自己传入
• Alloc：STL的空间配置器，用来申请底层空间

map的构造

这个构造函数也和set一样，因此不再赘述

map的迭代器和容量函数

?这些函数也和之前容器类似，也不再赘述

map的元素访问

?通过 [] 访问时，若key值存在，则得到value，不存在，则将key的value设置为默认值，然后插入到map中 。

通过 at 访问，若存在key值，则得到value,不存在则直接报异常

map的修改

map的empalce和emplace_hint和set的一样，只不过形式不同

emplace

#include<iostream>
#include<map>
#include<string>

using namespace std;

int main()
{
	map<string, string> m;
	pair<map<string, string>::iterator,bool> it = m.emplace("csdn", "https://blog.csdn.net/qq_37529913/article/details/118771777");
	cout << it.first->first.c_str() << " : " << it.first->second.c_str()<<" : "<< it.second << endl;
	return 0;
}

?同样的，存在则bool值为1，否则为0.

emplace_hint

#include<iostream>
#include<map>
#include<string>

using namespace std;

int main()
{
	map<string, string> m;
	map<string, string>::iterator it = m.emplace_hint(m.begin(),"csdn","https://blog.csdn.net/qq_37529913/article/details/118771777");
	cout << it->first.c_str() << " : " <<it->second.c_str()<< endl;
	return 0;
}

这个函数也可以设置插入的位置，不过map为了保持顺序，可能插入的位置和设置的位置不同。

multiset

• multiset按特定的顺序储存元素，key值可以重复
• 储存的元素不能修改，但是能够删除和插入
• 内部的元素按内部比较规则产生的严格若排序准则进行排序
• 该容器访问当个元素的速度比unordered_map的速度要慢，但迭代遍历时会得到一个有序序列
• 底层采用的红黑树结构

注意：

1. multiset的底层储存的 <value,value>的键值对
2. 它的插入接口只需要插入即可，不需要判断是否重复了
3. 和set不同，它的key值可以重复
4. 通过迭代器遍历，能得到有序的序列
5. 元素不能修改
6. 能够对数据进行排序

mulitimap

• 关联式容器，按特定顺序存储键值对，key值可以重复
• 通常按key值排序，value则存储和key关联的内容
• 内部通过内部比较对象，按严格弱排序的标准对key进行排序
• 单个元素的访问速度比unordered_map慢，使用迭代器遍历能够得到关于key有序的序列
• 底层用红黑树实现

注意：该容器的key值可以重复，正因如此，该容器不能像map一样通过下标访问。