KJHの博客

map与multimap的区别等同于set 与multiset的区别。

一、map

map的特性是，所有元素都会根据元素的键值自动被排序。map中的所有元素都是pair（意味着两个元素），同时拥有实质（value）和键值（key）。pair的第一元素被视为键值，第二元素被视为实质。回忆set，set 中的所有元素都是单个的（实值就是键值，键值就是实值）。map不允许两个元素拥有相同的键值。

下面是pair的定义

1
2
3
4
5
6
7
8
9

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) {}
};

从上可以看出，pair 包含两个类型（可以相同，也可以不相同）的公共元素。

标准的STL关联式容器分为set（集合）和map（映射表）两大类，以及两大类的衍生体multiset（多键集合）和multimap（多键映射表）（还有一些不在标准规格之列的关联式容器）。这些容器的底层机制均以RB-tree（红黑树）完成。

一、set

set 的特性是，所有元素都会根据元素的键值自动被排序，set 只拥有一个元素，它的键值就是实值，实值就是键值，并且set 不允许两个元素有相同的键值。

由于，set 元素值就是其键值，关系到 set 元素的排列规则，所以我们不能通过set 的迭代器来改变set 的元素值。标准的STL set 是以RB-tree 为底层机制，几乎所有的 set 操作行为，都只是转调用 RB-tree 的操作行为而已。

红黑树概述

历史上 AVL 树流行的另一变种是红黑树（red-black tree）。对红黑树的操作能保证在最坏情况下动态几何操作的时间为 O(logN) 。之前介绍过AVL 树，该树都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。但 RB-Tree 出来之后，便很少有应用场合用到 AVL 。

这里在探索STL源码时学习红黑树的，由于STL中的关联式容器默认的底层实现都是红黑树，以及 Linux 内核中包括进程队列等结构也是基于红黑树的。所以有必要掌握红黑树的实现原理和源码实现。

红黑树是二叉查找树，但在每个节点上增加了一位存储位表示该节点的颜色，具体可以是 RED 或 BLACK。通过对任一条从根到叶子的路径上各节点着色方式的限制，红黑树确保了没有一条路径会比其他路径长到两倍，因而基本上是平衡的。它所追求的的是局部平衡而不是AVL树中的非常严格的平衡。

红黑树在二叉查找树的基础上还必须满足以下着色规则：

1. 每个节点不是红色就是黑色
2. 根节点为黑色
3. 如果节点为红，其子节点必须为黑（一条路径上不能出现连续的两个红色节点）
4. 任一节点至NULL（树尾端）的任何路径，所含之黑节点数必须相同

根据规则4，新增节点必须为红；根据规则3，新增节点之父点必须为黑。当新节点根据二叉查找树的规则（键值大小）到达其插入点，却未能符合上述条件，就必须调整颜色并旋转树形。AVL 树插入节点后如果不满足其平衡条件，需要旋转树形。红黑树并不是基于 AVL 树的，它是在二叉查找树的基础上。

那么红黑树的基本平衡又是如何保证的呢？红黑树的着色法则，根据上面的规则，一条路径上不能出现连续的两个红色节点，必须有黑色节点间隔开来，然后红黑树的每条路径中所含黑色节点的数目必须相同，这样就限制每条路径之间的高度差，从而达到接近平衡的目的。

体会string 的强大。现今世界的数据处理大部分就是字符串处理，作为使用STL的程序员自然应该去了解 string 这个特殊容器。

这里就不同篇介绍string 了，只给出常用部分函数接口的内部实现。在应用string 的时候，只需要包含头文件 就行了

C++ 标准中string 类的特性与 vector<> 很相似，有以下几点区别：string 总会在末尾存放NULL 字符；string 需要借助 char_traits<>::assign,char_traits<>::copy 和char_traits<>::move 来复制元素，另外string 还额外提供了一些接口函数。

string（basic_string）类空间的分配（构造和析构）和vector<> 很相似，这里就不说了。这里只介绍几个重要函数

1
2
3
4
5
6
7
8
9
10
11

// ------------------------------------------------------------
// Class basic_string.  
// Class invariants:
// (1) [start, finish) is a valid range.
// (2) Each iterator in [start, finish) points to a valid object
//     of type value_type.
// (3) *finish is a valid object of type value_type; in particular,
//     it is value_type().
// (4) [finish + 1, end_of_storage) is a valid range.
// (5) Each iterator in [finish + 1, end_of_storage) points to 
//     unininitialized memory.

哈希表是一个很重要的数据结构，在各大场合均有应用，比如在内核网络栈中的 sock_array 的结构。

之前也学习过哈希表 ，建议看此文之前，先看前面用C++实现的简洁的哈希表。这里通过剖析SGI STL 中的hashtable 来进一步探索hashtable。

SGI STL 中哈希表采用链接法解决冲突。结构中维护了一个 vector，vector 中每一个元素称为一个桶（bucket），它包含的是一个链表的第一个节点。

哈希表的思想这里就不赘述了，直接通过STL 的源码来剖心其内部实现。

一、 hash table 的节点定义：

1
2
3
4
5

template <class Value>
struct __hashtable_node
  __hashtable_node* next; //下一个节点
  Value val; //键值
};

bucket 所维护的正是上述的 hash table node。

​

从上图可知，buckets vector 中存放的是bucket，然后每个bucket 存放链表（如果有的话）。通俗的说bucket 就是动态array 中的一个元素。