C++之STL源码剖析

侯捷STL源码剖析笔记。
STL六大部件:

  • 容器(Container)
  • 分配器(Allocators)
  • 算法(Algorithms)
  • 迭代器(Iterators)
  • 适配器(Adapters)
  • 仿函数(Functors)

STL六大组件之间的关系


1
2
3
4
5
6
7
8
9
10
11
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
int ia[6] = {1, 2, 3, 4, 5, 6};
vector<int, allocator<int>> vi(ia, ia+6); // container allocator
cout << count_if(vi.begin(), vi.end(), notl(bind2nd(less<int>(), 40))); // algorithm, iterator, function adapter(negator), function adapter(binder), function object
}


OOP&GP

  • 面向对象:封装是基础,继承是手段,多态是目的。
  • 泛型编程:参数化类型是基础,模板是手段,通用是目的。
  • 面向对象的编程依赖运行时多态,泛型编程是编译时多态。

Allocators

分配器主要是用来分配空间的,STL里面的容器的空间都是由配置器来分配的,分配器的核心代码如下:
G4.9版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class allocator: public __allocator_base<_Tp>
{
...
}
template<typename _Tp>
class new_allocator
{
...
pointer allocate(size_type __n, const void* = 0)
{
if (__n > this->max_size())
std::__throw_bad_alloc();
return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
}
void
deallocate(pointer __p, size_type)
{ ::operator delete(__p); }
};


Iterator

迭代器提供一种方法,使之能按照顺序访问某个容器中所包含的各个元素,而又不需暴露容器内部的表述方式。
迭代器提供类似指针访问的特性,支持自增自减操作,*->操作。
traits萃取机,顾名思义就是获得对象的类型和属性,一般定义如下:

1
2
3
4
5
6
7
8
template <calss Iterator>
struct iterator_traits {
typedef typename Iterator::iterator_category iterator_category;
typedef typename Iterator::value_type value_type;
typedef typename Iterator::difference_type difference_type;
typedef typename Iterator::pointer pointer;
typedef typename Iterator::reference reference;
};


vector

vector的优势在于其动态空间,其空间随着元素的加入会自动扩充空间以容纳新的元素,对于vector也比较熟悉了,这里主要列出vector实现的一些结构和算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
tamplate <class T, class Alloc = alloc>
class vector {
public:
// vector的嵌套类型定义
typedef T value_type;
typedef value_type* pointer;
typedef value_type* iterator;
typedef value_type& reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef simple_alloc<value_type, Alloc> data_allocator;
protected:
iterator start; // 表示正在使用空间的头
iterator finish; // 表示正在使用空间的尾
iterator end_of_storage; // 表示目前可用空间的尾
void fill_initialize(size_type n, const T& value) {
start = allocate_and_fill(n, value);
finish = start + n;
end_of_storage = finish;
}
void insert_aux(iterator position, const T& x) {
if (finish != end_of_storage) { // 还有备用空间
construct(finish, * (finish - 1));
++finish;
T x_copy = x;
copy_backward(position, finish - 2, finish - 1);
*position = x_copy;
} else {
const size_type old_size = size();
const size_type len = old_size != 0 ? 2 * old_size : 1;
iterator new_start = data_allocator::allocate(len);
iterator new_finish = new_start;
try {
new_finish = uninitialized_copy(copy, position, new_start);
construct(new_finish, x);
++new_finish;
new_finish = uninitialized_copy(position, finish, new_finish);
}
catch(...) {
// 如果发生异常,释放申请的内存
destroy(new_start, new_finish);
data_allocator::deallocate(new_start, len);
throw;
}
destory(begin(), end());
deallocate();
start = new_start;
finish = new_finish;
end_of_storage = new_start + len;
}
}
public:
iterator begin() { return start; }
iterator end() { return finish; }
size_type size() const { return size_type(end() - begin()); }
size_type capacity() const {
return size_type(end_of_storage - begin()); }
bool empty() const { return begin() == end(); }
reference operator[](size_type n) { return *(begin() + n); }
// 构造函数 & 拷贝构造函数
vector() : start(0), finish(0), end_of_storage(0) { }
vector(size_type n, const T& value) { fill_initialize(n, value); }
vector(int n, const T& value) { fill_initialize(n, value); }
vector(long n, const T& value) { fill_initialize(n, value); }
explicit vector(size_type n) { fill_initialize(n, T()); }
~vector() {
destory(start, finish);
deallocate();
}
reference front() { return *begin(); }
reference back() { return *(end() - 1); }
void push_back(const T& x) {
if (finish != end_of_storage) { // 空间未满,直接插入
construct(finish, x);
++finish;
} else {
insert_aux(end(), x);
}
}
void pop_back() {
--finish;
destroy(finish);
}
iterator erase(iterator position) { // 删除操作
if (position + 1 != end()) {
copy(position + 1, finish, position);
}
--finish;
destroy(finish);
return position;
}
private:
iterator allocate_and_fill(size_type n, const T& x) {
iterator result = data_allocator::allocate(n);
uninitialized_fill_n(result, n, x);
return result;
}
};


list

STL中,将list设计为一个双向链表。其节点结构如下:

1
2
3
4
5
6
7
template <class T>
struct __list_node {
typedef void* void_pointer;
void_pointer prev;
void_pointer next;
T data;
};

list的迭代器设计:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
template<class T, class Ref, class Ptr>
struct __list_iterator {
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, Ref, Ptr> self;
typedef __list_node<T>* link_type;
__list_iterator(link_type x) : node(x) { }
__list_iterator() { }
__list_iterator(const iterator& x) : node(x.node) { }
link_type node;
bool operator==(const self& x) const { return node == x.node; }
bool operator!=(const self& x) const { return node == x.node; }
reference operator*() const { return (*node).data; }
pointer operator->() const { return &(operator*()); }
self& operator++() {
node = (link_type)((*node).next);
return *this;
}
self operator++(int) {
self tmp = *this;
++*this;
return tmp;
}
self& operator--() {
node = (link_type)((*node).prev);
return *this;
}
self operator--(int) {
self tmp = *this;
--*this;
return tmp;
}
}

list的数据结构:

1
2
3
4
5
6
7
8
9
10
11
12
template <class T, class Alloc = alloc>
class list {
protected:
typedef __list_node<T> list_node;
public:
typedef list_node* link_type;
iterator begin() { return ((*node).next); }
iterator end() { return node; }
bool empty() const { return node->next = node; }
...
protected:
link_type node;


deque

deque是一种双向开口的连续线性空间,可以在头尾两端分别做元素的插入和删除操作。deque和vector的最大差异在于:

  • deque允许在常数时间内对头端进行元素的插入或删除操作
  • deque没有容量的概念

deque的结构如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
template <class T, class Alloc = alloc, size_t BufSiz = 0>
class deque {
public:
typedef T value_type;
typedef value_type* pointer;
typedef __deque_iterator<T, T&, T*, BufSiz> iterator;
...
protected:
typedef pointer* map_pointer;
iterator start;
iterator finish;
map_pointer map;
size_type map_size;
public:
iterator begin() { return start; }
iterator end() { return finish; }
reference operator[] (size_type n) {
return start[difference_type(n)];
}
bool empty() const {
return finish == start;
}
...
};

deque的迭代器:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
template <class T, class Ref, class Ptrsize_t BufSiz>
struct __deque_iterator {
typedef __deque_iterator<T, T&, T*, BufSiz> iterator;
typedef __deque_iterator<T, const T& const T*, BufSiz> const_iterator;
...
typedef __deque_iterator self;
T* cur; // 此迭代器所指之缓冲区中的现行元素
T* first; // 此迭代器所指之缓冲区的头
T* last; // 此迭代器所指之缓冲区的尾
map_pointer node;
void set_node(map_pointer new_node) {
node = new_node;
first = *new_node;
last = first + difference_type(buffer_size());
}
self& operator++() {
++cur;
if (cur == last) {
set_node(node + 1);
cur = first;
}
return *this;
}
};

这种映射关系如下图:


set

set和map的底层实现都是红黑树,红黑树的节点定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef bool __rb_tree_color_type;
const __rb_tree_color_type __rb_tree_red = false;
const __rb_tree_color_type __rb_tree_black = true;
struct __rb_tree_node_base {
typedef __rb_tree_color_type color_type;
typedef __rb_tree_node_base* base_ptr;
color_type color; // 节点颜色,非红即黑
base_ptr parent;
base_ptr left;
base_ptr right;
}
template <class Value>
class __rb_tree_node : public __rb_tree_node_base {
typedef __tb_tree_node<Value> *link_type;
Value value_field;
}

红黑树的结构定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
template <class Key, class Value, class KeyOfValue, class Compareclass Alloc = alloc>
class rb_tree {
protected:
typedef __rb_tree_node_base* base_ptr;
typedef __rb_tree_node<Value> rb_tree_node;
...
public:
typedef rb_tree_node* link_type;
protected:
size_type node_count;
link_type header;
Compare key_compare;
};

对红黑树有一个大致了解后,再来看看set的源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set {
public:
typedef Key key_type;
typedef Key valu_type;
typedef Compare key_compare;
typedef Compare value_compare;
private:
template <class T>
struct identity : public unary_function<T, T> {
const T& operator()(const T& x) const { return x; }
}
typedef rb_tee<key_type, value_type, identity<value_type>, key_compare, Alloc> rep_type;;
rep_type t;
public:
...
typedef typename rep_type::const_iterator iterator;
// iterator为const,故不能改变set里面的值
...
};

map

map中的元素都是pair,定义如下:

1
2
3
4
5
6
7
8
9
10
11
template <typename T1, typename 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) { }
};

map的结构定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
public:
typedef Key Key_value; // 键值型别
typedef T data_type; // 数值类型
typedef T mapped_type;
typedef pair<const Key, T> value_type; // 元素型号
...
private:
typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type;
rep_type t;
...
};

参考资料:
STL源码剖析 侯捷