简介
C++ STL Vector 是经典的连续存储空间的数据。它有两个模板参数:
_Alloc
vector
的实现比较简单,其实也不简单。它考虑了很多的性能优化,例如对于简单类型复制构造使用更高效的 uninitialized_copy/fill
; 扩张内存时,其内存扩张策略;兼容不同的 allocator (这部分工作感觉很多容器都会考虑)
实现细节
_M_start
_M_finish
_M_end_of_storage
这三个指针指向的是当前 vector 存储的空间和位置信息,这些在迭代器部分提供非常方便的实现。例如 begin
可以返回 _M_start
, size()
实现为 end() - begin()
,本质还是指针间的运算。
增加元素的操作
-
push_back
-
insert
-
insert(iterator __pos)
-
insert(iterator __pos, const _Tp& __x)
-
insert(iterator __pos, InputIterator __first, InputIterator __last)
-
insert(iterator __pos, size_type __n, const _Tp& __x)
push_back
操作在 _M_end_of_storage > _M_finish
时,只需要做下移动即可。其它情况需要做内存的扩张。
vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x) {
/* _M_finish != _M_end_of_storage */
/* 增加 _M_finish, 然后反向复制,最后在 __position 位置插入元素*/
/* new_size = old_size == 0 ? 1 : 2 * old_size */
/* 复制 _M_start->__position */
/* 复制 __position->_M_finish */
/* 赋值 __position 位置的值 */
}
疑惑点:
- 为什么要调用一下
construct
?
- 那部分
_M_end_of_storage
标记的只是内存空间,并没有初始化,所以必须先 construct
,然后再复制
-
else
分支中调用了: uninitialized_copy
,函数内部会根据情况去调用复制构造函数
- 复制一份
__x
: 放置变量会被覆盖吗?
- 放置传入的引用是在
copy_backward
的方位之内
删除元素的操作
pop_back
的实现比较简单,标记下 _M_finish
,然后 destroy
掉之前位置的元素即可。 erase
的实现 是类似的,只不过从末位换到一个任意位置,或者区间。注意 erase
返回的是删除元素的下一个位置。该 返回值主要用于遍历删除。
/* delete all elements in an array of int */
void delete_ele(vector array, int target) {
auto beg = array.begin();
auto end = array.end();
while (beg != end) {
if (*beg == target) {
beg = erase(beg);
} else {
++beg;
}
}
}
其它操作
-
assign
-
assign
会替换掉整个 vector
的内容
- 有直接插入值和插入一个区间两种实现
-
swap
-
swap
的实现其实比较简单,就是交换之前存储的三个状态值即可。
- comparison
- 比较的实现主要是实现
==
和 <
。前者使用 equal
实现,后者是 lexicographical_compare
本文完
This work is licensed under a
CC A-S 4.0 International License
.
以上所述就是小编给大家介绍的《C++ STL Vector》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 我们 的支持!