从零开始，打造自己的STL(二、vector)

发表于 | 更新于 | 分类于

vector的内存布局以及操作方式与array非常的类似，都是一段连续的内存空间。两者之间唯一的差距就是空间运用的灵活性。array的空间在配置好了之后就无法更改，它所存放的数据量是固定的，一但空间不够用之后需要重新配置一块更大的空间。vector则不然，它的内存空间会随着元素的加入自动扩充新的空间供给使用，这样使用起来就不需要担心空间是否够用了。

vector的内存结构

vector采用了连续内存空间的布局，那么它如何管理这块内存？如何做到内存的自增长呢？这一切要从它的内存结构来说起

mark

如上图所示，假如我们此时拥有8*sizeof(int)大小的空间，当然，内部存放的数据也为int了。vector定义了三个指针来管理这块空间。

start指向首元素所在的位置

finish指向最后一个有效元素所在的后一个位置，这样在新增元素的时候直接就可以放在finish所指的位置，然后再将finish自增即可。

end指向最后一个可用空间的后一个位置。

为何end不直接指向最后一个可用空间呢？

其一，当finish==end时，是否表示空间已经用完了呢，如果end指向的是最后一个可用空间的位置，显然此时还剩下最后一个空间没有被使用，这样对空间用尽的判断就不是很方便。其二，在我们遍历元素时，end指向可用空间的后一个位置能更加方便的作为循环的结束条件，岂不是非常的方便

1
2
for(; first != last; ++first)
    ....

这个应该就是STL中的前闭后开区间设计出来的原因吧，STL中的所有容器皆是采用的前闭后开区间的表示方法

说完了前闭后开区间，接下来说说start，finish这些是个什么东东

1
2
3
4
5
6
7
8
template<typename _Tp, typename _Alloc>
class vector
{
private:
    _Tp* _start;
    _Tp* _finish;
    _Tp* _end;
}

这就是这三个东东在STL源码当中的定义，他们皆是模板类型_Tp的指针，分别指向不同的位置而已。其实这三个东西也就是vector的迭代器了。因为vector本身内存布局的简单性，只需要通过原生指针就可以对里面的元素进行遍历与访问了。对于某些复杂的容器，他的迭代器可能也会是一个封装好的类。但是所有迭代器的功能都是一样的。提供对容器元素的访问

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
template<typename _Tp, typename _Alloc>
class vector
{
public:
    vector(const _Alloc&):_m_start(nullptr), _m_finish(nullptr), _m_end(nullptr){}
    vector(size_t _n, const _Alloc&) :_m_start(nullptr), _m_finish(nullptr), _m_end(nullptr)
    {
	_m_start = _M_allocate(_n);
	_m_finish = _m_start;
	_m_end = _m_start + _n;
    } 
protected:
    _Tp *_m_start;
    _Tp *_m_finish;
    _Tp *_m_end;

    typedef simple_alloc<_Tp, _Alloc> _m_data_allocator;

    _Tp* _M_allocate(size_t _n)
    {
	return _m_data_allocator::allocate(_n);
    }
};

在这里我们先看两个简单一点的构造，第一个构造函数简单粗暴，啥也没做。第二个构造函数其实就是分配了n*sizeof(Tp)大小的空间，大家可以吧_M_allocate这个函数想象成malloc。具体内容涉及到分配器的东西，留到下一章分享。

vector的底层通过malloc分配空间（或者也可能是operator new）。众所周知，malloc函数是不会调用类的构造函数的。如果我传递进去的模板参数是一个类类型，这样岂不是出大问题了。其实不然，STL直接将空间分配与元素构造分离开来。对于内置类型，无需进行构造的调用一个方法，需要进行构造的类型调用另一个方法，这样岂不是极大的提高了效率。

空间已经分配好了，接下来该进行元素的填充了。

1
2
3
4
vector(size_type _n, const value_type &_val):_Base(_n)
{
    _m_finish = uninitialized_fill_n(_m_start, _n, _val);
}

这个构造函数通过其基类先分配好n个大小的空间，在通过填充函数在这n个空间中填充值val并改变finish的指向。所有带uninitialized开头的是一套函数。故名思议，是对未初始化的元素进行的操作。何叫未初始化，就是未进行构造的元素。当然，它内部会有一套机制（POD）来确定该种类型的元素是否需要进行构造。因为其机制较为复杂，我们先只看需要构造的函数如何实现。其实这两者之前并无本质区别，只是在效率上进行了优化

1
2
3
4
5
6
7
8
9
template<typename _ForwardIter, typename _Size, typename _Tp>
_ForwardIter uninitialized_fill_n(_ForwardIter _first, _Size _n, const _Tp& _val)
{
	_ForwardIter _cur = _first;
	for (; _n > 0; --_n, ++_cur)
		construct(&*_cur, _val);

	return _cur;
}

函数其实非常简单易懂，在进行元素构造的时候&*cur这种操作可能会使人有些费解，实际上，它是先调用了迭代器的operator()，再取的地址。具体原因如下。迭代器的op()操作都是取出其中的数据元素，而我们此时显然要对迭代器中的数据进行操作。而直接取一个迭代器的地址并不能代表其中的数据地址。进行构造的底层实现通过placement new完成。

vector的元素操作

一. 添加元素

添加元素整体分为两种情况：空间充足与空间不充足。

如果空间足够，自然就很好解决了，直接将这些元素填充到后面的空间中，再改变finish的指向即可。

如果空间不够，这就要涉及到vector空间自增长的奥秘了。其实原理非常的简单，重新申请一块新空间，将原空间的数据copy进新空间，添加数据，销毁原空间。做法其实和array空间不够时一样，只是vector将其封装好了之后就不需要我们操心这么多了。当然，空间的增长也是需要一定的技巧的。不然我每次空间不够，都只申请比原空间大1的空间，这样反复的申请释放极大的浪费效率，不值当。在vector中，每次的自增长都会是原空间的两倍，甚至更多。源码如下

1
2
size_type _old_size = size();
size_type _len = _old_size + (_old_size > _n ? _old_size : _n);

在vector中，添加元素一般通过接口push_back()完成

1
2
3
4
void push_back(const value_type &_val)
{
	insert(end(), 1，_val);
}

该操作即为在末尾处插入一个新元素，会调用下面的insert接口

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
void inset(iterator _pos, size_type _n, const value_type &_val)
{
    if ((size_type)(_m_end - _m_finish) < _n) // 空间不够
    {
        size_type _old_size = size();
	size_type _len = _old_size + (_old_size > _n ? _old_size : _n);
	iterator _new_start = _M_allocate(_len);
        // 拷贝[begin,pos)到new_start处
	iterator _new_finish = uninitialized_copy(begin(), _pos, _new_start);
	_new_finish = uninitialized_fill_n(_new_finish, _n, _val);
	_new_finish = uninitialized_copy(_pos, end(), _new_finish);
			
	destroy(begin(), end());
	_M_deallocate(_m_start);
	_m_start = _new_start;
	_m_finish = _new_finish; 
	_m_end = _m_start + _len;
    }
    else if ((size_type)(_m_finish - _pos) < _n)// 填充的值部分需要构造的情况
    {
	size_type _elems_after = _m_finish - _pos;
	uninitialized_fill_n(_m_finish, _n - _elems_after, _val);

	iterator _old_finish = _m_finish;
	_m_finish += (_n - _elems_after);

	uninitialized_copy(_pos, _old_finish, _m_finish);
	_m_finish += _elems_after;
	fill(_pos, _old_finish, _val);
    }
    else if (0 < _n) // 空间够, 填充的值不需要构造的情况
    {
	uninitialized_copy(_m_finish - _n, _m_finish, _m_finish);
	iterator _old_finish = _m_finish;
	_m_finish += _n;
	copy_backward(_pos, _old_finish - _n, _old_finish);
	fill_n(_pos, _n, _val);
    }
}

在进行插入操作的时候整体分为两种情况，空间充足和空间不充足的情况。空间足够的时候又分为两种。插入的元素需要进行构造和不需要进行构造的情况。
上面提到过，STL中空间的分配和元素的构造是分离开来的，下面以两幅图来解释一下什么是部分需要构造和不需要构造

mark

假如在此种情况下，我需要在pos处插入n个元素，那么肯定需要把[pos, finish) 处的元素像后移动n位，再从pos开始填充n个val。

mark

从代码中可以看到

  1. 先将finish处也就是图中的old_finish处构造填充了值val

  2. 改变finish的指向之后，再将[pos, old_finish) 出的元素构造拷贝到现在finish所在的位置

  3. 直接填充[pos, old_finish) 的值为val。此时并没有调用需要进行构造的函数（uninitialized系列）
    图中红色的代表需要进行构造的位置，可以看到，是否进行构造针对的是地址空间，而不是元素的值。
    当然，对于push_back()这个函数来说，它永远只可能出现空间不足或者填充的元素需要进行构造的情况。

二. 删除元素

删除元素相对来说简单一点，因为它不会改变原有的空间，只需要将待删除元素的后面的元素向前移动即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void pop_back()
{
	erase(end() - 1);
}

iterator erase(iterator _pos)
{
	if (_pos + 1 != end())
	    copy(_pos + 1, _m_finish, _pos);

	--_m_finish;
	destroy(_m_finish);
	return _pos;
}

删除尾部元素的时候，其实仅仅只是改变了一下finish的指向，并调用了一下析构函数，代码中的destroy并不是释放了那块元素空间。而且对于单个的元素来说，它的空间并不能被释放。可想而知，pop_back()的效率还是相当之高的。

三. 元素访问

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
iterator begin()
{
	return _m_start;
}
const_iterator begin() const
{
	return _m_start;
}

iterator end()
{
	return _m_finish;
}
const_iterator end()const
{
	return _m_finish;
}

reverse_iterator rbegin()
{
	return reverse_iterator(end());
}
const_reverse_iterator rbegin()const
{
	return const_reverse_iterator(end());
}

reverse_iterator rend()
{
	return reverse_iterator(begin());
}
const_reverse_iterator rend()const
{
	return const_reverse_iterator(begin());
}

size_type size()const
{
	return size_type(end() - begin());
}

size_type max_size()const
{
	return (size_type(-1) / sizeof(value_type));
}

bool empty()const
{
	return _m_start == _m_finish;
}

reference at(size_type _n)
{
	return const_cast<reference> (static_cast<const vector&>(*this).at(_n));
}

const_reference at(size_type _n)const
{
	if (_n < size())
		return *(begin() + _n);
	else
	{
		throw std::out_of_range("out of array range");
	}
}

reference front()
{
	return *(begin());
}

const_reference front()const
{
	return *(begin());
}

reference back()
{
	return *(end() - 1);
}

const_reference back()const
{
	return *(end() - 1);
}

const_reference operator[](size_type _index)const
{
	return *(begin() + _index);
}
reference operator[](size_type _index)
{
	return *(begin() + _index);
}

size_type capacity()
{
	return _m_start == nullptr ? 0 : _m_end - _m_start;
}

从代码中可以看到，在元素访问中有很多精妙的地方。

  1. begin() 和 end() 所夹的区间即为有效的元素区间，通过事先设计好的结构可以直接的访问到

  2. 有效元素的个数直接通过两个指针相减就直接得出

  3. 判断vector是否为空直接通过begin()==end() 就可得出
    这些实现简单，效率奇高的接口都是通过STL精妙的设计自然得出的

STL设计的精妙和实现的巧妙相信从这里面已经可以管中窥豹，关于里面相信的代码和算法大家可以参照SGI的STL

接下来，我将会分享STL隐藏在幕后的一个组件——空间分配器。