STL源码剖析 关联式容器

发布于:2021-10-27 02:14:16

上一章的篇幅有点长,这里简单记录一下利用了红黑树为底层机制的几个关联式容器。


set /multiset

set特性是,所有元素会根据元素的键值自动被排序,set元素的键值就是实值,实值就是键值,不允许两个元素有相同的键值。
不能通过set的迭代器改变set的元素值,因为其值是其键值,关系到set元素的排列,如果改变set元素值会严*苹祍et组织,在原理上,setiterator被定义为红黑树中的const_iterator,就是杜绝写入操作。
set的迭代器经过increase或者erase后,操作之前的所有迭代器在操作之后都依然有效,当然被删除的迭代器是个例外。
set所有的操作行为都只是调用RB-tree的操作行为而已。
set使用RB-tree的insert_unique(),因为其不允许相同的键值 ,multiset允许相同的键值,其使用insert_equal().
面对关联式容器,应该使用其提供的find函数,会比STL算法find()更有效率,因为STL算法find()只是循序搜索。


map/multimap

mapd的特性是所有元素都会根据元素的键值自动被排序,map的所有元素都是pair,同时拥有实值和键值,pair的第一元素视为键值,第二元素视为实值,map不允许两个元素拥有相同的键值。在源码中,typedef pair value_type;
中pair的定义如下:


template
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),scond(b){};
};

不能通过map的迭代器改变map的元素键值,因为会关系到map的排列规则,但是可以修正元素的实值。
map的迭代器经过increase或者erase后,操作之前的所有迭代器在操作之后都依然有效,当然被删除的迭代器是个例外。


在map的源码中,有一个比较难理解的地方


T& operator[](const key_type&k)
{
return (*((insert(value_type(k,T()))).first)).second;
}

insert() 返回的是pair , 所以.first取出的类型是iterator, 而在map中插入的是pair类型 ,所以*()取出的是pair, 再取其second则为实值


multimap的特性与map完全相同,唯一差别是是它允许键值重复,因为它的插入操作是采用底层机制RB-tree的insert_equal()

相关推荐

最新更新

猜你喜欢