Summary

STL 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
template<class _Ty, class _A = allocator<_Ty> >
class vector 
{
public:
	typedef vector<_Ty, _A>     _Myt;
	typedef _A                  allocator_type;
	typedef _A::size_type       size_type;
	typedef _A::difference_type difference_type;
	typedef _A::pointer         _Tptr;
	typedef _A::const_pointer   _Ctptr;
	typedef _A::reference       reference;
	typedef _A::const_reference const_reference;
	typedef _A::value_type      value_type;
	typedef _Tptr               iterator;                //vector迭代器就是本身的指针
	typedef _Ctptr              const_iterator;
	
protect:	
	_A allocator;                //空间配置器
	iterator _First, _Last, _End;//正在使用的头，正在使用的尾，空间的尾
	...
};

构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
explicit vector(const _A& _Al = _A())                 //简单的初始化成员变量
	: allocator(_Al), _First(0), _Last(0), _End(0) {}
	
explicit vector(size_type _N, const _Ty& _V = _Ty(),  //初始化_N个_TY变量
	const _A& _Al = _A())
	: allocator(_Al)
	{_First = allocator.allocate(_N, (void *)0);
	_Ufill(_First, _N, _V);                       //这个函数后面会有，就是从_F开始构造_N个_V                   
	_Last = _First + _N;
	_End = _Last; }
	
vector(const _Myt& _X)                           //拷贝构造函数
	: allocator(_X.allocator)
	{_First = allocator.allocate(_X.size(), (void *)0);
	_Last = _Ucopy(_X.begin(), _X.end(), _First);
	_End = _Last; }
	
typedef const_iterator _It;
vector(_It _F, _It _L, const _A& _Al = _A())     //构造vector并在开始位置插入_F到_L间的数据
	: allocator(_Al), _First(0), _Last(0), _End(0)
	{insert(begin(), _F, _L); }

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
		
void resize(size_type _N, const _Ty& _X = _Ty())  //resize手动改变vector容量
	{if (size() < _N)
		insert(end(), _N - size(), _X);
	else if (_N < size())
		erase(begin() + _N, end()); }
size_type size() const //已用大小
	{return (_First == 0 ? 0 : _Last - _First); }

bool empty() const
	{return (size() == 0); }

reference operator[](size_type _P)
	{return (*(begin() + _P)); }

void push_back(const _Ty& _X)     //在容器的最后插入一个元素
	{insert(end(), _X); }
void pop_back()                   //删除最后一个元素
	{erase(end() - 1); }

iterator insert(iterator _P, const _Ty& _X = _Ty()) //插入一个,返回的迭代器指向的是
	{size_type _O = _P - begin();
	insert(_P, 1, _X);
	return (begin() + _O); }
	
void insert(iterator _P, size_type _M, const _Ty& _X) //从_P开始插入_M个_X元素
	{if (_End - _Last < _M)
		{size_type _N = size() + (_M < size() ? size() : _M);
		iterator _S = allocator.allocate(_N, (void *)0);
		iterator _Q = _Ucopy(_First, _P, _S);
		_Ufill(_Q, _M, _X);
		_Ucopy(_P, _Last, _Q + _M);
		_Destroy(_First, _Last);
		allocator.deallocate(_First, _End - _First);
		_End = _S + _N;
		_Last = _S + size() + _M;
		_First = _S; }
	else if (_Last - _P < _M)
		{_Ucopy(_P, _Last, _P + _M);
		_Ufill(_Last, _M - (_Last - _P), _X);
		fill(_P, _Last, _X);
		_Last += _M; }
	else if (0 < _M)
		{_Ucopy(_Last - _M, _Last, _Last);
		copy_backward(_P, _Last - _M, _Last);
		fill(_P, _P + _M, _X);
		_Last += _M; }}
		
void insert(iterator _P, _It _F, _It _L)
	{size_type _M = 0;
	_Distance(_F, _L, _M);
	if (_End - _Last < _M)
		{size_type _N = size() + (_M < size() ? size() : _M);
		iterator _S = allocator.allocate(_N, (void *)0);
		iterator _Q = _Ucopy(_First, _P, _S);
		_Q = _Ucopy(_F, _L, _Q);
		_Ucopy(_P, _Last, _Q);
		_Destroy(_First, _Last);
		allocator.deallocate(_First, _End - _First);
		_End = _S + _N;
		_Last = _S + size() + _M;
		_First = _S; }
	else if (_Last - _P < _M)
		{_Ucopy(_P, _Last, _P + _M);
		_Ucopy(_F + (_Last - _P), _L, _Last);
		copy(_F, _F + (_Last - _P), _P);
		_Last += _M; }
	else if (0 < _M)
		{_Ucopy(_Last - _M, _Last, _Last);
		copy_backward(_P, _Last - _M, _Last);
		copy(_F, _L, _P);
		_Last += _M; }}
iterator erase(iterator _P)
	{copy(_P + 1, end(), _P);    // 从—_p+1开始往前挪
	_Destroy(_Last - 1, _Last);
	--_Last;
	return (_P); }
iterator erase(iterator _F, iterator _L)
	{iterator _S = copy(_L, end(), _F);
	_Destroy(_S, end());
	_Last = _S;
	return (_F); }
void clear()
	{erase(begin(), end()); }

protected:
void _Destroy(iterator _F, iterator _L)
	{for (; _F != _L; ++_F)
		allocator.destroy(_F); }
iterator _Ucopy(const_iterator _F, const_iterator _L,
	iterator _P)
	{for (; _F != _L; ++_P, ++_F)
		allocator.construct(_P, *_F);
	return (_P); }
void _Ufill(iterator _F, size_type _N, const _Ty &_X)
	{for (; 0 < _N; --_N, ++_F)
		allocator.construct(_F, _X); }
void _Xran() const
	{_THROW(out_of_range, "invalid vector<T> subscript"); }

size_type capacity() const //容量
{return (_First == 0 ? 0 : _End - _First); }