STL源码——关联式容器及其底层红黑树实现(上) 之关联式容器详细介绍

2023-11-07

在侯捷老师源码剖析一书中对关联式进行源码剖析前先花了不少篇幅介绍红黑树的原理，这是因为关联式容器的底层依赖于RB_Tree实现。
因此想尝试在下篇剖析红黑树的源码，在此之前，先复习一下各个关联式容器的方法及容器之间的不同之处或许对红黑树的剖析会有“带着问题看文章”的感觉。

map/multimap

map和multimap都需要#include<map>, 唯一不同就是map的键值key不可以重复，但是multimap可以，也因此map可以用[]运算符，而multimap不支持

map提供一对一的数据处理能力，map内部自建一棵红黑树(红黑树不是一种严格意义上的平衡二叉树)，红黑树对数据有自动排序的功能，所以在map内部的数据都是有序的

map/multimap的基本操作函数

begin() 返回指向头部的迭代器
clear() 删除所有元素
count() 返回指定元素出现的次数
empty() 是否为空，空则返回1
end() 返回指向尾部的迭代器
equal_range()返回特殊条目的迭代器对
erase() 删除一个元素
find() 查找一个元素
get_allocator() 返回配置器
insert() 插入元素
key_comp() 返回比较元素key的函数
value_comp() 返回比较元素value的函数
lower_bound() 返回键值 >= 给定元素的第一个位置 第一个小于或等于
upper_bound() 返回键值 > 给定元素的第一个位置 第一个小于
rbegin() 返回指向尾部的逆向迭代器
rend() 返回指向头部的逆向迭代器
size() 返回map中元素的个数
max_size() 返回可以容纳的最大元素个数
swap() 交换两个map

共有8个迭代器： begin、end、rbegin、rend 、cbegin、cend、crbegin、crend 两者的区别在于，后面一组一定返回const_iterator，而前面四个则根据map的类型返回iterator或者const_iterator。const情况下，不允许对值进行修改

map的插入操作

用insert插入pair数据

#include<map>
#include<string>
#include<iostream>
using namespace std;

int main()
{
	map<int, string> mapStudent
	mapStudent.insert(pair<int, string>(1, "amy"));
	mapStudent.insert(pair<int, string>(2, "john"));
	map<int, string>::iterator iter;
	for(iter = mapStudent.begin(); iter!=mapStudent.end(); iter++)
		cout<<iter->first<<''<<iter->second<<endl;
}

用insert函数插入value_type数据

value_type是一个typedef，是迭代器所指对象的类型

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

int main()
{
	map<int, string> mapStudent
	mapStudent.insert(map<int, string>::value_type(1, "amy"));
	mapStudent.insert(map<int, string>::value_type(2, "john"));
	map<int, string>::iterator iter;
	for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
		cout<<iter->first<<''<<iter->second<<endl;
}

用insert函数进行多个插入

插入单个键值对，并返回插入位置和成功标志，插入位置已经存在值时，插入失败

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

在指定位置插入，在不同位置插入效率是不一样的，因为设计到重排

iterator insert(const_iterator position, const value_type& val);

插入多个

void insert(InputIterator first, InputIterator last);

C++11之后支持列表插入多个

void insert(initializer_list<value_type> li);

用数组方式插入数据

#include<map>
#include<string>
#include<iostream>
using namespace std;
int main()
{
	map<int, string> mapStudent;
	mapStudent[1] = "amy";
	mapStudent[2] = "john";
	map<int, string>::iterator iter;
	for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
		cout<<iter->first<<''<<cout->second<<endl;
}

用insert插入数据时，在数据上会涉及到集合的唯一性这个概念，即当map中有这个key了这个数据就插入不进去了，但是数组方式就不同了，它可以覆盖之前关键字对应的值
检验可以用pair的第二个变量来知道是否插入成功。

排序

关于排序，map中的元素时自动按key升序排序，所以不能对map用sort函数， STL中默认是采用小于号来排序的，但是在遇到一些特殊情况时map就不能自动排序了，比如关键字是一个结构体或者自定义类，因为没有小于号操作涉及到的排序就会出现问题
可以用重载小于号和仿函数来解决

unordered_map

map底层使用红黑树，而unordered_map底层使用哈希表实现，查询的事件复杂度(从算法上讲)是O(1)，用哈希表，因此内部是无序的，数据是按照散列韩素插入的。当我们不需要内部有序时，就可以用这个实现；也是关联式容器，采用std::pair保存key-value形式的数据；
unordered_map库使用“桶”来存储元素，散列值相同的会被存储在一个桶里，当散列容器中有大量数据时，同一个桶里的数据也会增多，造成访问冲入，降低性能。为了提高散列容器的性能， unordered库会在插入元素时自动增加桶的数量，不需要用户指定，但是用户也可以在构造函数或者rehash()中指定最小的桶的数量

另外从占有内存上来说因为unordered_map采用hash结构，所以它的内存会高于map

set/multiset

会自动排序，搜索、移除和插入拥有对数复杂度。都以红黑树作为底层实现，set与map的不同在于set中的元素即是键值又是实值，set不匀速有两个元素有相同的键值，不能通过set的迭代器区修改set元素，当对容器中的元素进行插入或删除时，操作之前的所有迭代器在操作之后依然有效

同样，由于set元素时排好序的，且默认为升序，因此当set集合中的元素为结构体或自定义类时，该结构体或自定义类必须实现<的重载

multiset和set的差别唯一就是multiset允许键值重复

set常用成员函数

begin()–返回指向第一个元素的迭代器
clear()–清除所有元素
count()–返回某个值元素的个数
empty()–如果集合为空，返回true
end()–返回指向最后一个元素的迭代器
equal_range()–返回集合中与给定值相等的上下限的两个迭代器
erase()–删除集合中的元素
find()–返回一个指向被查找到元素的迭代器
get_allocator()–返回集合的分配器
insert()–在集合中插入元素
lower_bound()–返回指向大于（或等于）某值的第一个元素的迭代器
key_comp()–返回一个用于元素间值比较的函数
max_size()–返回集合能容纳的元素的最大限值
rbegin()–返回指向集合中最后一个元素的反向迭代器
rend()–返回指向集合中第一个元素的反向迭代器
size()–集合中元素的数目
swap()–交换两个集合变量
upper_bound()–返回大于某个值元素的迭代器
value_comp()–返回一个用于比较元素间的值的函数

set的insert函数返回值为一个对组(pair)：对组的第一个值first为set类型的迭代器：若插入成功，迭代器指向该元素，若插入失败，迭代器指向之前已经存在的元素；对组的第二个值seconde为bool类型：若插入成功，bool值为true，若插入失败，bool值为false

multiset的insert函数返回值为multiset类型的迭代器，指向新插入的元素。multiset允许插入相同的值，因此插入一定成功，不需要返回bool类型。

unordered_set

unordered_set和unordered_map内部实现是基于哈希表(hashtable)，两者的公共接口大致相同，以unordered_set为例:
使用unordered_set需要包含#include<unordered_set>头文件

下篇主要就学习红黑树，set和multiset的区别就在与红黑树的插入方式一个时insert_unique和insert_equal，而set和map的区别是map的所有元素都是pair而set的键值就是实值
set和map的几乎所欲行为都只是转调用RB-tree的操作行为而已

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)