libc++源码分析之std::vector

发表于 分类于 本文字数： 2.9k 阅读时长 ≈ 11 分钟

std::vector

数据结构

__vector_base

vector的基类，定义了vector的数据结构，在vector内部是使用对象数组来实现的，end - begin表示size，end_cap - begin表示capacity。

1
2
3
4
5
6
7
8
class __vector_base
    : protected __vector_base_common<true>
{
public:
    pointer                                         __begin_; // 数组第一个对象的首地址
    pointer                                         __end_; // 数组下一个待存储的对象的首地址
    __compressed_pair<pointer, allocator_type> __end_cap_; // 数组内存尾指针
}

函数

构造函数

vector(initializer_list __il)

1
2
3
4
5
6
7
8
9
10
11
12
13
template <class _Tp, class _Allocator>
inline _LIBCPP_INLINE_VISIBILITY
vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il)
{
#if _LIBCPP_DEBUG_LEVEL == 2
    __get_db()->__insert_c(this);
#endif
    if (__il.size() > 0)
    {
        __vallocate(__il.size()); // 分配内存
        __construct_at_end(__il.begin(), __il.end(), __il.size()); // 拷贝数据
    }
}

vector(size_type __n, const value_type& __x)

1
2
3
4
5
6
7
8
9
10
11
12
template <class _Tp, class _Allocator>
vector<_Tp, _Allocator>::vector(size_type __n, const value_type& __x)
{
#if _LIBCPP_DEBUG_LEVEL == 2
    __get_db()->__insert_c(this);
#endif
    if (__n > 0)
    {
        __vallocate(__n); // 分配内存
        __construct_at_end(__n, __x); // 拷贝数据
    }
}

vector(const vector& __x)
拷贝构造会拷贝整个对象数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <class _Tp, class _Allocator>
vector<_Tp, _Allocator>::vector(const vector& __x)
    : __base(__alloc_traits::select_on_container_copy_construction(__x.__alloc()))
{
#if _LIBCPP_DEBUG_LEVEL == 2
    __get_db()->__insert_c(this);
#endif
    size_type __n = __x.size();
    if (__n > 0)
    {
        __vallocate(__n); // 分配内存
        __construct_at_end(__x.__begin_, __x.__end_, __n); // 拷贝数据
    }
}

vector(vector&& __x)
移动构造只是简单的拷贝对象数组的地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <class _Tp, class _Allocator>
inline _LIBCPP_INLINE_VISIBILITY
vector<_Tp, _Allocator>::vector(vector&& __x)
#if _LIBCPP_STD_VER > 14
        _NOEXCEPT
#else
        _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
#endif
    : __base(_VSTD::move(__x.__alloc()))
{
#if _LIBCPP_DEBUG_LEVEL == 2
    __get_db()->__insert_c(this);
    __get_db()->swap(this, &__x);
#endif
    this->__begin_ = __x.__begin_; // 拷贝数组地址
    this->__end_ = __x.__end_;
    this->__end_cap() = __x.__end_cap();
    __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr;
}

析构函数

~vector()

1
2
3
4
5
6
7
8
    _LIBCPP_INLINE_VISIBILITY
    ~vector()
    {
        __annotate_delete();
#if _LIBCPP_DEBUG_LEVEL == 2
        __get_db()->__erase_c(this);
#endif
    }

~__vector_base()
在基类的析构中，会对数据进行释放

1
2
3
4
5
6
7
8
9
template <class _Tp, class _Allocator>
__vector_base<_Tp, _Allocator>::~__vector_base()
{
    if (__begin_ != nullptr)
    {
        clear(); // 修改end指针，将size设置0，如果数组中存储的是对象，则调用对象的析构函数，如果是指针则跳过
        __alloc_traits::deallocate(__alloc(), __begin_, capacity()); // 释放分配的数组内存
    }
}

__vallocate

分配指针大小的Tp数组

1
2
3
4
5
6
7
8
9
10
template <class _Tp, class _Allocator>
void
vector<_Tp, _Allocator>::__vallocate(size_type __n)
{
    if (__n > max_size())
        this->__throw_length_error();
    this->__begin_ = this->__end_ = __alloc_traits::allocate(this->__alloc(), __n); // 分配Tp数组，将首地址保存到__begin，默认为空，所以__end也指向首地址
    this->__end_cap() = this->__begin_ + __n; // 保存分配的内存的尾指针
    __annotate_new(0);
}

__construct_at_end

__construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <class _Tp, class _Allocator>
template <class _ForwardIterator>
typename enable_if
<
    __is_cpp17_forward_iterator<_ForwardIterator>::value,
    void
>::type
vector<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n)
{
    _ConstructTransaction __tx(*this, __n);
    _VSTD::__construct_range_forward(this->__alloc(), __first, __last, __tx.__pos_); // 遍历填充，tx.pos为__end_指针，从end位置开始插入
}

template <class _Alloc, class _Iter, class _Ptr>
_LIBCPP_INLINE_VISIBILITY
void __construct_range_forward(_Alloc& __a, _Iter __begin1, _Iter __end1, _Ptr& __begin2) {
    typedef allocator_traits<_Alloc> _Traits;
    for (; __begin1 != __end1; ++__begin1, (void) ++__begin2) { 
        _Traits::construct(__a, _VSTD::__to_address(__begin2), *__begin1); // 循环拷贝数据
    }
}

__construct_at_end(size_type __n, const_reference __x)

1
2
3
4
5
6
7
8
9
10
11
template <class _Tp, class _Allocator>
inline
void
vector<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x)
{
    _ConstructTransaction __tx(*this, __n);
    const_pointer __new_end = __tx.__new_end_;
    for (pointer __pos = __tx.__pos_; __pos != __new_end; ++__pos, __tx.__pos_ = __pos) {
        __alloc_traits::construct(this->__alloc(), _VSTD::__to_address(__pos), __x); // 循环拷贝数据
    }
}

clear

clear函数会修改end指针，将size设置为0，如果数组中存储的是对象，则调用对象的析构函数，如果是指针则跳过，并不会影响capacity，也不会释放内存。

1
2
3
4
5
6
7
8
_LIBCPP_INLINE_VISIBILITY
void clear() _NOEXCEPT
{
    size_type __old_size = size();
    __base::clear(); // 主要逻辑都在基类函数中
    __annotate_shrink(__old_size);
    __invalidate_all_iterators();
}
1
2
3
4
_LIBCPP_INLINE_VISIBILITY
void clear() _NOEXCEPT {
    __destruct_at_end(__begin_); 
}
1
2
3
4
5
6
7
8
9
10
template <class _Tp, class _Allocator>
inline _LIBCPP_INLINE_VISIBILITY
void
__vector_base<_Tp, _Allocator>::__destruct_at_end(pointer __new_last) _NOEXCEPT
{
    pointer __soon_to_be_end = __end_;
    while (__new_last != __soon_to_be_end)
        __alloc_traits::destroy(__alloc(), _VSTD::__to_address(--__soon_to_be_end)); // 遍历已经存储的对象，如果该对象不是指针，则会调用对象的析构函数
    __end_ = __new_last; // 更新end，指向begin，size为0
}

operator=

operator=(vector&& __x) 

1
2
3
4
5
6
7
8
9
10
template <class _Tp, class _Allocator>
inline _LIBCPP_INLINE_VISIBILITY
vector<_Tp, _Allocator>&
vector<_Tp, _Allocator>::operator=(vector&& __x)
    _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value))
{
    __move_assign(__x, integral_constant<bool,
          __alloc_traits::propagate_on_container_move_assignment::value>()); // 销毁当前数组，拷贝x中数组的指针到当前对象，并将x中的数组置为空
    return *this;
}

operator=(const vector& __x)

1
2
3
4
5
6
7
8
9
10
11
12
template <class _Tp, class _Allocator>
inline _LIBCPP_INLINE_VISIBILITY
vector<_Tp, _Allocator>&
vector<_Tp, _Allocator>::operator=(const vector& __x)
{
    if (this != &__x)
    {
        __base::__copy_assign_alloc(__x);
        assign(__x.__begin_, __x.__end_); // 替换数据
    }
    return *this;
}

assign

清除当前数据，再将first到last的数据拷贝过来，不足会自动扩容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <class _Tp, class _Allocator>
template <class _InputIterator>
typename enable_if
<
     __is_cpp17_input_iterator  <_InputIterator>::value &&
    !__is_cpp17_forward_iterator<_InputIterator>::value &&
    is_constructible<
       _Tp,
       typename iterator_traits<_InputIterator>::reference>::value,
    void
>::type
vector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
{
    clear(); // 清空当前数组，重置end指向begin
    for (; __first != __last; ++__first)
        __emplace_back(*__first); // 拷贝插入到end位置
}

emplace_back

根据参数构造对象，并插入到end位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <class _Tp, class _Allocator>
template <class... _Args>
inline
#if _LIBCPP_STD_VER > 14
typename vector<_Tp, _Allocator>::reference
#else
void
#endif
vector<_Tp, _Allocator>::emplace_back(_Args&&... __args)
{
    if (this->__end_ < this->__end_cap()) 
    {
        __construct_one_at_end(_VSTD::forward<_Args>(__args)...); // 如果不需要扩容，则直接拷贝到end位置，end++
    }
    else
        __emplace_back_slow_path(_VSTD::forward<_Args>(__args)...); // 需要扩容
#if _LIBCPP_STD_VER > 14
    return this->back();
#endif
}

扩容前size为4，capacity为4
. . . .
split_buffer会分配一段内存，capacity为8，并将end指向下标为4的位置
。。。。。。。。
construct后，在end位置构造新对象
。。。。. 。。。
swap_out_circular_buffer会先将当前数组中的对象拷贝到split_buffer的数组中，然后再把当前数组与split_buffer中的数组进行交换
. . . . . 。。。
这样当前vector中保存的就是扩容后的新数组，在split_buffer中保存的就是旧数组，函数结束，split_buffer析构函数中会对旧数组进行销毁 

1
2
3
4
5
6
7
8
9
10
11
12
13
template <class _Tp, class _Allocator>
template <class... _Args>
void
vector<_Tp, _Allocator>::__emplace_back_slow_path(_Args&&... __args)
{
    allocator_type& __a = this->__alloc();
    //2倍扩容，capacity = 2 * capacity
    __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a); // 重新分配数组内存，从第size()位置开始存储
//    __v.emplace_back(_VSTD::forward<_Args>(__args)...);
    __alloc_traits::construct(__a, _VSTD::__to_address(__v.__end_), _VSTD::forward<_Args>(__args)...); // 将当前对象构造到size()位置
    __v.__end_++; // end指向size()+1
    __swap_out_circular_buffer(__v); // 将[0,size-1]的数据拷贝到split_buffer中，并将交换数组
}

emplace

根据参数构造对象，并插入到指定位置

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
template <class _Tp, class _Allocator>
template <class... _Args>
typename vector<_Tp, _Allocator>::iterator
vector<_Tp, _Allocator>::emplace(const_iterator __position, _Args&&... __args)
{
#if _LIBCPP_DEBUG_LEVEL == 2
    _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
        "vector::emplace(iterator, x) called with an iterator not"
        " referring to this vector");
#endif
    pointer __p = this->__begin_ + (__position - begin());
    if (this->__end_ < this->__end_cap())
    {  // 无需扩容
        if (__p == this->__end_)
        { // 插入到尾部
            __construct_one_at_end(_VSTD::forward<_Args>(__args)...);  // 插入到end
        }
        else
        {   // 插入到中间
            __temp_value<value_type, _Allocator> __tmp(this->__alloc(), _VSTD::forward<_Args>(__args)...); // 构造对象
            __move_range(__p, this->__end_, __p + 1);  // 将position后面的元素后移一位
            *__p = _VSTD::move(__tmp.get()); // 将构造的对象放入到position位置
        }
    }
    else
    {
        allocator_type& __a = this->__alloc();
        __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a); // 扩容，end位置指向position
        __v.emplace_back(_VSTD::forward<_Args>(__args)...); // 向end位置插入对象
        __p = __swap_out_circular_buffer(__v, __p); // 拷贝数据，交换数组
    }
    return __make_iter(__p);
}

size

1
2
3
4
_LIBCPP_INLINE_VISIBILITY
size_type size() const _NOEXCEPT {
    return static_cast<size_type>(this->__end_ - this->__begin_);
}

capacity

1
2
3
4
_LIBCPP_INLINE_VISIBILITY
size_type capacity() const _NOEXCEPT {
    return static_cast<size_type>(__end_cap() - __begin_);
}

empty

1
2
3
bool empty() const _NOEXCEPT {
    return this->__begin_ == this->__end_;
}

reserve

设置分配内存大小，设置的是cap大小，size不会变。

1
2
3
4
5
6
7
8
9
10
11
template <class _Tp, class _Allocator>
void
vector<_Tp, _Allocator>::reserve(size_type __n)
{
    if (__n > capacity())
    {
        allocator_type& __a = this->__alloc();
        __split_buffer<value_type, allocator_type&> __v(__n, size(), __a); // 扩容
        __swap_out_circular_buffer(__v); // 拷贝数据，并交换数组指针，__split_buffer析构时销毁旧数组
    }
}

shrink_to_fit

将capacity缩小为size大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <class _Tp, class _Allocator>
void
vector<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
{
    if (capacity() > size())
    {
#ifndef _LIBCPP_NO_EXCEPTIONS
        try
        {
#endif // _LIBCPP_NO_EXCEPTIONS
            allocator_type& __a = this->__alloc();
            __split_buffer<value_type, allocator_type&> __v(size(), size(), __a);
            __swap_out_circular_buffer(__v);
#ifndef _LIBCPP_NO_EXCEPTIONS
        }
        catch (...)
        {
        }
#endif // _LIBCPP_NO_EXCEPTIONS
    }
}

operator[]

1
2
3
4
5
6
7
8
template <class _Tp, class _Allocator>
inline _LIBCPP_INLINE_VISIBILITY
typename vector<_Tp, _Allocator>::reference
vector<_Tp, _Allocator>::operator[](size_type __n) _NOEXCEPT
{
    _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds");
    return this->__begin_[__n];
}

at

1
2
3
4
5
6
7
8
template <class _Tp, class _Allocator>
typename vector<_Tp, _Allocator>::reference
vector<_Tp, _Allocator>::at(size_type __n)
{
    if (__n >= size())
        this->__throw_out_of_range();
    return this->__begin_[__n];
}

push_back

将对象插入到end位置，和emplace_back逻辑一致，只是一个接收的对象，一个接收的构造对象的参数

1
2
3
4
5
6
7
8
9
10
11
12
template <class _Tp, class _Allocator>
inline _LIBCPP_INLINE_VISIBILITY
void
vector<_Tp, _Allocator>::push_back(const_reference __x)
{
    if (this->__end_ != this->__end_cap())
    {
        __construct_one_at_end(__x); // 直接插入到end
    }
    else
        __push_back_slow_path(__x); // 扩容
}

逻辑和__emplace_back_slow_path一致

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <class _Tp, class _Allocator>
template <class _Up>
void
#ifndef _LIBCPP_CXX03_LANG
vector<_Tp, _Allocator>::__push_back_slow_path(_Up&& __x)
#else
vector<_Tp, _Allocator>::__push_back_slow_path(_Up& __x)
#endif
{
    allocator_type& __a = this->__alloc();
    __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a); // 扩容
    // __v.push_back(_VSTD::forward<_Up>(__x));
    __alloc_traits::construct(__a, _VSTD::__to_address(__v.__end_), _VSTD::forward<_Up>(__x)); // 构造对象到end位置
    __v.__end_++; // end++
    __swap_out_circular_buffer(__v); // 交换数组
}

insert

插入对象到指定位置，和emplace逻辑一致，只是一个接收的对象，一个接收的构造对象的参数

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
template <class _Tp, class _Allocator>
typename vector<_Tp, _Allocator>::iterator
vector<_Tp, _Allocator>::insert(const_iterator __position, const_reference __x)
{
#if _LIBCPP_DEBUG_LEVEL == 2
    _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
        "vector::insert(iterator, x) called with an iterator not"
        " referring to this vector");
#endif
    pointer __p = this->__begin_ + (__position - begin());
    if (this->__end_ < this->__end_cap())
    { // 无需扩容
        if (__p == this->__end_)
        { // 插入到尾部
            __construct_one_at_end(__x); // 插入到end
        }
        else
        { // 插入到中间
            __move_range(__p, this->__end_, __p + 1); // 将position后面的元素后移一位
            const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
            if (__p <= __xr && __xr < this->__end_)
                ++__xr;
            *__p = *__xr; // 将构造的对象放入到position位置
        }
    }
    else
    {
        allocator_type& __a = this->__alloc();
        __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a); // 扩容，end位置指向position
        __v.push_back(__x); // 向end位置插入对象
        __p = __swap_out_circular_buffer(__v, __p); // 拷贝数据，交换数组
    }
    return __make_iter(__p);
}

erase

删除指定位置的对象，需要注意的是erase所触发的析构函数并不是删除的那个对象的析构函数，而是最后一个元素的析构函数。
假设vector中有元素1 2 3 4，此时删除2这个元素，那么首先erase会进行move操作，变成1 3 4 4，对于整个数组来说，最后一位的4明显应该为空且应该被销毁的，并且对于删除操作来说，一次删除只应该调用一次析构，所以此处选择调用最后一个4的析构，而并不是删除的2的析构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <class _Tp, class _Allocator>
inline _LIBCPP_INLINE_VISIBILITY
typename vector<_Tp, _Allocator>::iterator
vector<_Tp, _Allocator>::erase(const_iterator __position)
{
#if _LIBCPP_DEBUG_LEVEL == 2
    _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
        "vector::erase(iterator) called with an iterator not"
        " referring to this vector");
#endif
    _LIBCPP_ASSERT(__position != end(),
        "vector::erase(iterator) called with a non-dereferenceable iterator");
    difference_type __ps = __position - cbegin();
    pointer __p = this->__begin_ + __ps; // 计算position
    this->__destruct_at_end(_VSTD::move(__p + 1, this->__end_, __p)); // 通过std::move将[position+1, end-1]位置的元素移动到[position, end-2]位置，并调用end-1位置对象的析构函数
    this->__invalidate_iterators_past(__p-1);
    iterator __r = __make_iter(__p);
    return __r;
}

resize

设置添加的元素长度，设置的是size长度。

1
2
3
4
5
6
7
8
9
10
template <class _Tp, class _Allocator>
void
vector<_Tp, _Allocator>::resize(size_type __sz)
{
    size_type __cs = size();
    if (__cs < __sz)
        this->__append(__sz - __cs); // 如果当前size不足，则填充（通过无参构造构造出对象）
    else if (__cs > __sz)
        this->__destruct_at_end(this->__begin_ + __sz); // 如果当前size超出，重新调整end位置，并调用超出部分的析构函数
}

swap

交换两个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 <class _Tp, class _Allocator>
void
vector<_Tp, _Allocator>::swap(vector& __x)
#if _LIBCPP_STD_VER >= 14
    _NOEXCEPT
#else
    _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
                __is_nothrow_swappable<allocator_type>::value)
#endif
{
    _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value ||
                   this->__alloc() == __x.__alloc(),
                   "vector::swap: Either propagate_on_container_swap must be true"
                   " or the allocators must compare equal");
    _VSTD::swap(this->__begin_, __x.__begin_);
    _VSTD::swap(this->__end_, __x.__end_);
    _VSTD::swap(this->__end_cap(), __x.__end_cap());
    _VSTD::__swap_allocator(this->__alloc(), __x.__alloc(),
        integral_constant<bool,__alloc_traits::propagate_on_container_swap::value>());
#if _LIBCPP_DEBUG_LEVEL == 2
    __get_db()->swap(this, &__x);
#endif
}

std::vector<bool>

vector<bool>是vector对bool的特化，但是特殊的是，vector<bool>为了节省内存，其内部存储的并不是bool，因为一个bool占用了一个字节，而对于bool来说只有true和false，一位就可以表示，所以在vector<bool>中是按照位来存储的，而通过operator[]和at获取到的也并不是对应的bool值，而是其内部的一个bit_reference类。

1
typedef __bit_reference<vector>                  reference;

数据结构

vector<bool>

vector<bool>并没有继承vector_base基类，所以其数据结构是自己定义的，里面维护了一个size_t类型的数组，数组的每个元素有32位，可以存储32个值。

1
2
3
4
5
6
7
8
9
template <class _Allocator>
class _LIBCPP_TEMPLATE_VIS vector<bool, _Allocator>
    : private __vector_base_common<true>
{
public:
    __storage_pointer                                      __begin_; // size_t指针，32位，可以存储32个元素
    size_type                                              __size_;  // 存储元素的个数
    __compressed_pair<size_type, __storage_allocator> __cap_alloc_;
}

函数

operator[]

1
2
3
_LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n) {
    return __make_ref(__n);
}

每个元素都可以存储32个值，所以对于pos需要对__bits_per_word进行转换，当pos为40时，需要查找的数组的第2个元素也就是begin+1位置，而对应的位就是第8位。reference接收两个参数，一个是对应的元素，一个是对应的位。

1
2
3
reference __make_ref(size_type __pos) _NOEXCEPT {
    return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word); // 将外部位置转换为bit位置
}