STL浅析——序列式容器vector的元素操作: pop_back()、ease()、clear() 和 insert()

81 阅读 0 评论 54 点赞

我是靠谱客的博主悦耳背包，这篇文章主要介绍STL浅析——序列式容器vector的元素操作: pop_back()、ease()、clear() 和 insert()，现在分享给大家，希望可以做个参考。

　　vector 容器的元素操作函数有很多，我就选取四个讲解一下，首先是pop_back()函数，pop() 函数的作用是将尾端元素拿掉并调整大小，并不涉及到容量的改变：

复制代码

1
2
3
4
5
void pop_back()

{
--_M_finish;　　//_M_finish是指向现有元素的最后一个元素的下一个cell地址，只需要减一，然后调用destory()即可
destroy(_M_finish);
}

　　ease() 函数作用是清除某一个元素，或者清除两个迭代器之间的所有元素，如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//清除某一个元素

iterator erase(iterator __position)
{
if (__position + 1 != end())
copy(__position + 1, _M_finish, __position);
--_M_finish;
destroy(_M_finish);
return __position;
}
//清除迭代器__first 和 __last之间的所有元素

iterator erase(iterator __first, iterator __last)
{
iterator __i = copy(__last, _M_finish, __first);　　//将__last到_M_finish（最后一个元素的下一个cell）所有元素copy到从__first开始的地方
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　//返回_M_finish对应的cell，在copy之后所在位置的迭代器，赋值给__i
　　　//然后销毁从__i到_M_finish的所有元素，并移动_M_finish到删除元素之后新元素序列的尾端的下一个cell

复制代码

1
　　destroy(__i, _M_finish); _M_finish = _M_finish - (__last - __first); return __first;
 }

　　第二个 erase 示意图如下：

　　insert函数是把元素插入到对应位置，该函数效率很低，特别是front插入，要移动所有元素退后一个位置，很花销时间，企业级数据尽量少用 vector 的 insert，以下是其源代码：

复制代码

template <class _Tp, class _Alloc>
void vector<_Tp, _Alloc>::_M_fill_insert(iterator __position, size_type __n,
const _Tp& __x)
{
if (__n != 0) //防止不插入元素而造成资源耗费

{
//备用空间大小大于或者等于新增元素个数
if (size_type(_M_end_of_storage - _M_finish) >= __n)
{
_Tp __x_copy = __x;
//

const size_type __elems_after = _M_finish - __position;
iterator __old_finish = _M_finish;　　　　　　　//我的技术太渣，理解倒是理解了，就是不知道为啥这么写。。。。
if (__elems_after > __n)
{
uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
_M_finish += __n;
copy_backward(__position, __old_finish - __n, __old_finish);
fill(__position, __position + __n, __x_copy);
}
else
{
uninitialized_fill_n(_M_finish, __n - __elems_after, __x_copy);
_M_finish += __n - __elems_after;
uninitialized_copy(__position, __old_finish, _M_finish);
_M_finish += __elems_after;
fill(__position, __old_finish, __x_copy);
}
//不明白为什么要比较__elems_after 和 _n，不是能够全体移动并且直接插入要插入的元素吗？所以
//感觉特别复杂，个人觉得可以改成：

uninitialized_copy(__position, _M_finish, __position + n);
_M_finish += __n;
fill(__position, __position + __n, __x_copy);
}
else
{
//备用空间大小小于新增元素个数，必须配置额外内存，那就用到空间是配置器了
const size_type __old_size = size();
//决定新的长度，为旧的长度的两倍，或者旧的长度+新的长度
const size_type __len = __old_size + max(__old_size, __n);
//开始调用空间配置器
iterator __new_start = _M_allocate(__len);
iterator __new_finish = __new_start;
__STL_TRY
{
//移动元素
//首先移动要插入点位置之前的所有元素到新的vector
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
//其次开始构造要插入的元素
__new_finish = uninitialized_fill_n(__new_finish, __n, __x);
//最后移动要插入点位置之后的所有元素到新的vector

__new_finish
= uninitialized_copy(__position, _M_finish, __new_finish);
}
__STL_UNWIND((destroy(__new_start,__new_finish);
//以下清除并且释放旧的vector

_M_deallocate(__new_start,__len)));
destroy(_M_start, _M_finish);
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
//移动起始点和水位
_M_start = __new_start;
_M_finish = __new_finish;
_M_end_of_storage = __new_start + __len;
}
}
}

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
template <class _Tp, class _Alloc>
void vector<_Tp, _Alloc>::_M_fill_insert(iterator __position, size_type __n,
const _Tp& __x)
{
if (__n != 0) //防止不插入元素而造成资源耗费

{
//备用空间大小大于或者等于新增元素个数
if (size_type(_M_end_of_storage - _M_finish) >= __n)
{
_Tp __x_copy = __x;
//

const size_type __elems_after = _M_finish - __position;
iterator __old_finish = _M_finish;
　　　　　　　//我的技术太渣，理解倒是理解了，就是不知道为啥这么写。。。。
if (__elems_after > __n)
{
uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
_M_finish += __n;
copy_backward(__position, __old_finish - __n, __old_finish);
fill(__position, __position + __n, __x_copy);
}
else
{
uninitialized_fill_n(_M_finish, __n - __elems_after, __x_copy);
_M_finish += __n - __elems_after;
uninitialized_copy(__position, __old_finish, _M_finish);
_M_finish += __elems_after;
fill(__position, __old_finish, __x_copy);
}
//不明白为什么要比较__elems_after 和 _n，不是能够全体移动并且直接插入要插入的元素吗？所以

//感觉特别复杂，个人觉得可以改成：

uninitialized_copy(__position, _M_finish, __position + n);
_M_finish += __n;
fill(__position, __position + __n, __x_copy);
}
else
{
//备用空间大小小于新增元素个数，必须配置额外内存，那就用到空间是配置器了
const size_type __old_size = size();
//决定新的长度，为旧的长度的两倍，或者旧的长度+新的长度
const size_type __len = __old_size + max(__old_size, __n);
//开始调用空间配置器
iterator __new_start = _M_allocate(__len);
iterator __new_finish = __new_start;
__STL_TRY
{
//移动元素
//首先移动要插入点位置之前的所有元素到新的vector
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
//其次开始构造要插入的元素
__new_finish = uninitialized_fill_n(__new_finish, __n, __x);
//最后移动要插入点位置之后的所有元素到新的vector

__new_finish
= uninitialized_copy(__position, _M_finish, __new_finish);
}
__STL_UNWIND((destroy(__new_start,__new_finish);
//以下清除并且释放旧的vector

_M_deallocate(__new_start,__len)));
destroy(_M_start, _M_finish);
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
//移动起始点和水位
_M_start = __new_start;
_M_finish = __new_finish;
_M_end_of_storage = __new_start + __len;
}
}
}