vector

主要代码位于 stl_vector.h
较为简单，本身就是个动态数组。结构较为简单

1
2
3
4
5
6
7
8
9
10
11
template<typename _Tp, typename _Alloc>
struct _Vector_base
{
    ...
    struct _Vector_impl : public _Tp_alloc_type
    {
	pointer _M_start;
	pointer _M_finish;
	pointer _M_end_of_storage;
    }
}

因为是连续地址空间，所以迭代器直接就是正常的指针，分别表示目前使用的头，尾与可用的尾指针。为了降低空间配置的成本，vector配置的空间一般会大于所需的空间，实际上就是在分配大于当前容量时，会分配当前容量二倍的空间，这个可以通过代码来试一下，后面也会调试源码来看到。

Constructors

  1. 指定空间大小及初值。such as: vector v(3,0); 
    1
    2
    3
    4
    vector(size_type __n, const value_type& __value,
        const allocator_type& __a = allocator_type())
    : _Base(__n, __a)
    { _M_fill_initialize(__n, __value); }

_Base(n,a) 会分配空间并设置好迭代器的位置

1
2
3
_Vector_base(size_t __n, const allocator_type& __a)
: _M_impl(__a)
{ _M_create_storage(__n); }

_M_fill_initialize(n, value) 会将初值填充进去并调整迭代器位置

1
2
3
4
5
6
7
void
_M_fill_initialize(size_type __n, const value_type& __value)
{
std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value, 
                _M_get_Tp_allocator());
this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
}

  1. 当有初值进行初始化时。such as: vector v = {1，2};
    1
    2
    3
    4
    5
    6
    7
    vector(initializer_list<value_type> __l,
        const allocator_type& __a = allocator_type())
    : _Base(__a)
    {
    _M_range_initialize(__l.begin(), __l.end(),
            random_access_iterator_tag());
    }

将初值复制进分配的空间中

1
2
3
4
5
6
7
8
9
10
11
12
13
template<typename _ForwardIterator>
void
_M_range_initialize(_ForwardIterator __first,
        _ForwardIterator __last, std::forward_iterator_tag)
{
    const size_type __n = std::distance(__first, __last);
    this->_M_impl._M_start = this->_M_allocate(__n);
    this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
    this->_M_impl._M_finish =
    std::__uninitialized_copy_a(__first, __last,
                this->_M_impl._M_start,
                _M_get_Tp_allocator());
}

push_back && pop_back

  1. push_back
    1
    2
    3
    void
    push_back(value_type&& __x)
    { emplace_back(std::move(__x)); }

进入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<typename _Tp, typename _Alloc>
template<typename... _Args>
    void
    vector<_Tp, _Alloc>::
    emplace_back(_Args&&... __args)
    {
if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
    {
    _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
                    std::forward<_Args>(__args)...);
    ++this->_M_impl._M_finish;
    }
else
    _M_emplace_back_aux(std::forward<_Args>(__args)...);
    }

就是检测下是否到达容量。如果还有剩余，则调用construct将元素置入并将尾迭代器向后，否则调用_M_emplace_back_aux

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
template<typename _Tp, typename _Alloc>
template<typename... _Args>
    void
    vector<_Tp, _Alloc>::
    _M_emplace_back_aux(_Args&&... __args)
    {
const size_type __len =
    _M_check_len(size_type(1), "vector::_M_emplace_back_aux"); //计算新空间所需大小

//暂时使用的指向新vector的迭代器
pointer __new_start(this->_M_allocate(__len));
pointer __new_finish(__new_start);
__try
    {
    //将原vector的内容拷贝到新的vector
    _Alloc_traits::construct(this->_M_impl, __new_start + size(),
                    std::forward<_Args>(__args)...);
    __new_finish = 0;

    __new_finish
        = std::__uninitialized_move_if_noexcept_a
        (this->_M_impl._M_start, this->_M_impl._M_finish,
        __new_start, _M_get_Tp_allocator());

    ++__new_finish;
    }
__catch(...)
    {
    if (!__new_finish)
        _Alloc_traits::destroy(this->_M_impl, __new_start + size());
    else
        std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
    _M_deallocate(__new_start, __len);
    __throw_exception_again;
    }
//释放原vector
std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
            _M_get_Tp_allocator());
_M_deallocate(this->_M_impl._M_start,
            this->_M_impl._M_end_of_storage
            - this->_M_impl._M_start);
//更新迭代器
this->_M_impl._M_start = __new_start;
this->_M_impl._M_finish = __new_finish;
this->_M_impl._M_end_of_storage = __new_start + __len;
    }

  • 这里学习到的一点是： vector 迭代器的更新（空间重配置，迭代器便需要更新）。
  1. pop_back

就是单纯的移动迭代器指针之后撤销元素

1
2
3
4
5
6
void
pop_back() _GLIBCXX_NOEXCEPT
{
--this->_M_impl._M_finish;
_Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
}

insert

接口

1
2
3
iterator
insert(const_iterator __position, value_type&& __x)
{ return emplace(__position, std::move(__x)); }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typename vector<_Tp, _Alloc>::iterator
vector<_Tp, _Alloc>::
emplace(const_iterator __position, _Args&&... __args)
{
    //若留有空间且插入为末尾，则直接按push_back中的操作进行
const size_type __n = __position - begin();
if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
&& __position == end())
{
_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
                std::forward<_Args>(__args)...);
++this->_M_impl._M_finish;
}
else
_M_insert_aux(begin() + (__position - cbegin()),
    std::forward<_Args>(__args)...);
return iterator(this->_M_impl._M_start + __n);
}

否则进入细节的插入函数_M_insert_aux

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
void
vector<_Tp, _Alloc>::
_M_insert_aux(iterator __position, const _Tp& __x)
{
    //若还有空间
    if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
{
    _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
                    _GLIBCXX_MOVE(*(this->_M_impl._M_finish
                                - 1)));
    ++this->_M_impl._M_finish;
    _GLIBCXX_MOVE_BACKWARD3(__position.base(),
                this->_M_impl._M_finish - 2,
                this->_M_impl._M_finish - 1);
    *__position = _Tp(std::forward<_Args>(__args)...);
}
    else
{
    const size_type __len =
    _M_check_len(size_type(1), "vector::_M_insert_aux"); //新长度
    const size_type __elems_before = __position - begin();
    //临时新迭代器
    pointer __new_start(this->_M_allocate(__len));
    pointer __new_finish(__new_start);
    __try
    {
        //将添加的元素置入位置
        _Alloc_traits::construct(this->_M_impl,
                            __new_start + __elems_before,
                    std::forward<_Args>(__args)...);
        __new_finish = 0;
        //原先前半部分的元素
        __new_finish
    = std::__uninitialized_move_if_noexcept_a
    (this->_M_impl._M_start, __position.base(),
        __new_start, _M_get_Tp_allocator());

        ++__new_finish;
        //原先后半部分的元素
        __new_finish
    = std::__uninitialized_move_if_noexcept_a
    (__position.base(), this->_M_impl._M_finish,
        __new_finish, _M_get_Tp_allocator());
    }
        __catch(...)
    {
        if (!__new_finish)
    _Alloc_traits::destroy(this->_M_impl,
                            __new_start + __elems_before);
        else
    std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
        _M_deallocate(__new_start, __len);
        __throw_exception_again;
    }

    //释放原vector，更新迭代器
    std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
        _M_get_Tp_allocator());
    _M_deallocate(this->_M_impl._M_start,
        this->_M_impl._M_end_of_storage
        - this->_M_impl._M_start);
    this->_M_impl._M_start = __new_start;
    this->_M_impl._M_finish = __new_finish;
    this->_M_impl._M_end_of_storage = __new_start + __len;
}
}