SGI STL 标准库 set map multiset multimap 8

github源码分析仓库

set


set特性 所有元素会根据元素的键值自动排序。set元素的键值就是实值,实值就是键值。set不允许两个元素有相同的键值。
set无法通过迭代器改变set元素的值,因为set元素值就是键值,关系到set元素的排列规则。set的迭代器set<T>::iterator被定义为底层RB-tree的const_iterator,杜绝写入操作。
set当进行元素新增操作或删除操作时,除了被删除元素的迭代器,操作之前的所有迭代器,在操作完成后依然有效。
set以RB-tree作为底层容器,set几乎所有的操作,都是转调用RB-tree的操作。
set使用RB-tree的insert_unique(),因为set不允许相同键值存在。

map


map特性 所有元素会根据元素的键值进行排序。map的所有元素都是pair,同时拥有实值和键值。pair的第一个元素被视为键值,第二个元素被视为实值。map不允许两个元素拥有相同的键值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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) {}

#ifdef __STL_MEMBER_TEMPLATES
template <class _U1, class _U2>
pair(const pair<_U1, _U2>& __p) : first(__p.first), second(__p.second) {}
#endif
};

可以通过迭代器修改map元素的实值,但不能通过迭代器修改map元素的键值,因为map元素的键值关系到其排序,而其实值不影响。
对map进行新增、删除操作,不会影响迭代器的有效性,被删除元素的迭代器除外。
map以RB-tree作为底层容器。
map的insert()转调用RB-tree的insert_unique()函数,保证元素的键值唯一。
map的下标操作符,用法有两种,可作为左值运用(内容可被修改),也可作右值使用(内容不可被修改)。左值和右值都适用的关键在于返回值采用传引用的传递方式。

multiset


multiset和set的特性与用法完全相同,唯一的差别在于它允许键值重复,因为它的插入采用的是底层容器RB-tree的insert_equal()

multimap


multimap和map的特性与用法完全相同,唯一的差别在于它允许键值重复,因为它的插入采用的是底层容器RB-tree的insert_equal()