C++ STL 容器设计与实现分析 -- vector
2、vector
vector 属于动态数组，自动控制存储空间，根据需要进行扩展和收缩。通常拥有额外的空间以处理未来的增长，这样，每次插入元素时，不需要每次重新分配内存，仅在附加内存耗尽时才重新分配。
可使用 capacity() 查看分配的内存总量，也可以调用 shrink_to_fit() 将额外的内存返回给系统。如果事先知道元素数量，可调用 reserve(n) 一次性分配内存。
vector 继承于 _Vector_base，_Vector_base 只有一个 _Vector_impl 类型的成员变量。
template<typename _Tp, typename _Alloc>
struct _Vector_base
{
struct _Vector_impl_data
{
pointer _M_start;
pointer _M_finish;
pointer _M_end_of_storage;
/* ... */
};
struct _Vector_impl
: public _Tp_alloc_type, public _Vector_impl_data
{
/* ... */
};
public:
_Vector_impl _M_impl;
/* ... */
};
template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
class vector : protected _Vector_base<_Tp, _Alloc>
{
/* ... */
};
抽丝剥茧，vector 实现只用到三个指针：
- _M_start：内存起始地址
- _M_finish：vector 结束地址
- _M_end_of_storage：内存结束地址
2.1、 _Vector_base
_Vector_base 负责管理 vector 内存的申请与释放。
_M_allocate() 和 _M_deallocate() 两个函数分别负责申请和释放内存，_M_create_storage(n) 申请 n 个对象的空间，然后初始化三个指针成员。
_GLIBCXX20_CONSTEXPR
pointer
_M_allocate(size_t __n)
{
typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
return __n != 0 ? _Tr::allocate(_M_impl, __n) : pointer();
}
_GLIBCXX20_CONSTEXPR
void
_M_deallocate(pointer __p, size_t __n)
{
typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
if (__p)
_Tr::deallocate(_M_impl, __p, __n);
}
protected:
_GLIBCXX20_CONSTEXPR
void
_M_create_storage(size_t __n)
{
this->_M_impl._M_start = this->_M_allocate(__n);
this->_M_impl._M_finish = this->_M_impl._M_start;
this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
}
_Vector_base 构造函数调用 _M_create_storage() 函数申请 n 个对象空间。
_GLIBCXX20_CONSTEXPR
_Vector_base(size_t __n, const allocator_type& __a)
: _M_impl(__a)
{ _M_create_storage(__n); }
2.2、vector::type
template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
class vector : protected _Vector_base<_Tp, _Alloc>
{
typedef _Vector_base<_Tp, _Alloc> _Base;
typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Alloc_traits;
public:
typedef _Tp value_type;
typedef typename _Base::pointer pointer;
typedef typename _Alloc_traits::const_pointer const_pointer;
typedef typename _Alloc_traits::reference reference;
typedef typename _Alloc_traits::const_reference const_reference;
typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;
typedef __gnu_cxx::__normal_iterator<const_pointer, vector>
const_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef _Alloc allocator_type;
/* ... */
};
2.3、vector::ctor
构造函数分析三种
2.3.1、vector(n)
当构造函数指定了 vector 的大小，首先基类 _Vector_base 申请 n 个元素的内存空间（不调用元素构造函数），然后 vector 构造函数将调用 _M_default_initialize() 函数给申请的 n 个对象初始化。
vector(size_type __n, const allocator_type& __a = allocator_type())
: _Base(_S_check_init_len(__n, __a), __a)
{ _M_default_initialize(__n); }
_M_default_initialize()
_GLIBCXX20_CONSTEXPR
void
_M_default_initialize(size_type __n)
{
this->_M_impl._M_finish =
std::__uninitialized_default_n_a(this->_M_impl._M_start, __n,
_M_get_Tp_allocator());
}
template<typename _ForwardIterator, typename _Size, typename _Tp>
_GLIBCXX20_CONSTEXPR
inline _ForwardIterator
__uninitialized_default_n_a(_ForwardIterator __first, _Size __n,
allocator<_Tp>&)
{ return std::__uninitialized_default_n(__first, __n); }
template<typename _ForwardIterator, typename _Size>
_GLIBCXX20_CONSTEXPR
inline _ForwardIterator
__uninitialized_default_n(_ForwardIterator __first, _Size __n)
{
typedef typename iterator_traits<_ForwardIterator>::value_type
_ValueType;
// See uninitialized_fill_n for the conditions for using std::fill_n.
constexpr bool __can_fill
= __and_<is_integral<_Size>, is_copy_assignable<_ValueType>>::value;
return __uninitialized_default_n_1<__is_trivial(_ValueType)
&& __can_fill>::
__uninit_default_n(__first, __n);
}
__uninitialized_default_n_1 尽可能调用 std::fill_n 处理。
template<bool _TrivialValueType>
struct __uninitialized_default_n_1
{
template<typename _ForwardIterator, typename _Size>
_GLIBCXX20_CONSTEXPR
static _ForwardIterator
__uninit_default_n(_ForwardIterator __first, _Size __n)
{
_ForwardIterator __cur = __first;
__try
{
for (; __n > 0; --__n, (void) ++__cur)
std::_Construct(std::__addressof(*__cur));
return __cur;
}
__catch(...)
{
std::_Destroy(__first, __cur);
__throw_exception_again;
}
}
};
template<>
struct __uninitialized_default_n_1<true>
{
template<typename _ForwardIterator, typename _Size>
_GLIBCXX20_CONSTEXPR
static _ForwardIterator
__uninit_default_n(_ForwardIterator __first, _Size __n)
{
if (__n > 0)
{
typename iterator_traits<_ForwardIterator>::value_type* __val
= std::__addressof(*__first);
std::_Construct(__val); // 构造 first
++__first; // 剩余元素拷贝
__first = std::fill_n(__first, __n - 1, *__val);
}
return __first;
}
};
2.3.2、vector(n, val)
当构造函数指定元素个数和值时，最终 std::uninitialized_fill_n() 会被调用，初始化对象的值。
_GLIBCXX20_CONSTEXPR
vector(size_type __n, const value_type& __value,
const allocator_type& __a = allocator_type())
: _Base(_S_check_init_len(__n, __a), __a)
{ _M_fill_initialize(__n, __value); }
_GLIBCXX20_CONSTEXPR
void
_M_fill_initialize(size_type __n, const value_type& __value)
{
this->_M_impl._M_finish =
std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
_M_get_Tp_allocator());
}
template<typename _ForwardIterator, typename _Size, typename _Tp,
typename _Tp2>
_GLIBCXX20_CONSTEXPR
inline _ForwardIterator
__uninitialized_fill_n_a(_ForwardIterator __first, _Size __n,
const _Tp& __x, allocator<_Tp2>&)
{
#ifdef __cpp_lib_is_constant_evaluated
/* ... */
#endif
return std::uninitialized_fill_n(__first, __n, __x);
}
2.3.3、vector(first, last)
template<typename _InputIterator,
typename = std::_RequireInputIter<_InputIterator>>
_GLIBCXX20_CONSTEXPR
vector(_InputIterator __first, _InputIterator __last,
const allocator_type& __a = allocator_type())
: _Base(__a)
{
_M_range_initialize(__first, __last,
std::__iterator_category(__first));
}
template<typename _InputIterator>
_GLIBCXX20_CONSTEXPR
void
_M_range_initialize(_InputIterator __first, _InputIterator __last,
std::input_iterator_tag)
{
__try {
for (; __first != __last; ++__first)
#if __cplusplus >= 201103L
emplace_back(*__first); // 逐一执行 emplace_back
#else
#endif
} __catch(...) {
clear();
__throw_exception_again;
}
}
template<typename _ForwardIterator>
_GLIBCXX20_CONSTEXPR
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(_S_check_init_len(__n, _M_get_Tp_allocator()));
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()); // 拷贝元素
}
2.4、vector::dctor
vector 的析构函数调用 std::_Destroy() 函数将 [start, finish) 范围的对象析构。std::_Destroy() 根据对象类型做优化：如果对象的析构函数是 default 或者编译器自动生成的，std::_Destroy() 什么都不做，否则依次调用对象的析构函数。
_GLIBCXX20_CONSTEXPR
~vector() _GLIBCXX_NOEXCEPT
{
std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
_M_get_Tp_allocator());
_GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC;
}
2.5、push_back
如果有剩余空间，在末尾的位置构造一个对象
void
push_back(const value_type& __x)
{
if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
{
_GLIBCXX_ASAN_ANNOTATE_GROW(1);
_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
__x);
++this->_M_impl._M_finish;
_GLIBCXX_ASAN_ANNOTATE_GREW(1);
}
else
_M_realloc_insert(end(), __x);
}
否则调用 _M_realloc_insert() 进行扩容
- 调用 _M_check_len() 函数计算新的长度
- 在新的内存地址构造新插入的元素
- 将就的元素拷贝到新内存
- 旧元素析构，旧内存释放
在元素构造和拷贝过程中，如果有任何异常抛出，已经构造的对象将被析构。
#if __cplusplus >= 201103L
template<typename _Tp, typename _Alloc>
template<typename... _Args>
_GLIBCXX20_CONSTEXPR
void
vector<_Tp, _Alloc>::
_M_realloc_insert(iterator __position, _Args&&... __args)
#else
/* ... */
#endif
{
const size_type __len =
_M_check_len(size_type(1), "vector::_M_realloc_insert");
pointer __old_start = this->_M_impl._M_start;
pointer __old_finish = this->_M_impl._M_finish;
const size_type __elems_before = __position - begin();
pointer __new_start(this->_M_allocate(__len)); // 扩容
pointer __new_finish(__new_start);
__try
{
// The order of the three operations is dictated by the C++11
// case, where the moves could alter a new element belonging
// to the existing vector. This is an issue only for callers
// taking the element by lvalue ref (see last bullet of C++11
// [res.on.arguments]).
_Alloc_traits::construct(this->_M_impl,
__new_start + __elems_before,
#if __cplusplus >= 201103L
std::forward<_Args>(__args)...); // 构造插入元素
#else
__x);
#endif
__new_finish = pointer();
#if __cplusplus >= 201103L
if _GLIBCXX17_CONSTEXPR (_S_use_relocate())
{
__new_finish = _S_relocate(__old_start, __position.base(),
__new_start, _M_get_Tp_allocator()); // 拷贝旧元素
++__new_finish;
__new_finish = _S_relocate(__position.base(), __old_finish,
__new_finish, _M_get_Tp_allocator()); // 拷贝旧元素
}
else
#endif
{
__new_finish
= std::__uninitialized_move_if_noexcept_a
(__old_start, __position.base(),
__new_start, _M_get_Tp_allocator());
++__new_finish;
__new_finish
= std::__uninitialized_move_if_noexcept_a
(__position.base(), __old_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;
}
#if __cplusplus >= 201103L
if _GLIBCXX17_CONSTEXPR (!_S_use_relocate())
#endif
std::_Destroy(__old_start, __old_finish, _M_get_Tp_allocator());
_GLIBCXX_ASAN_ANNOTATE_REINIT;
_M_deallocate(__old_start,
this->_M_impl._M_end_of_storage - __old_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;
}
_M_check_len() 函数可以看到，新的 size 时原来的两倍
_GLIBCXX20_CONSTEXPR
size_type
_M_check_len(size_type __n, const char* __s) const
{
if (max_size() - size() < __n)
__throw_length_error(__N(__s));
const size_type __len = size() + (std::max)(size(), __n);
return (__len < size() || __len > max_size()) ? max_size() : __len;
}
emplace_back() 和 push_back() 类似，只不过 emplace_back() 调用的构造函数，push_back() 调用赋值构造函数。
#if __cplusplus >= 201103L
template<typename _Tp, typename _Alloc>
template<typename... _Args>
#if __cplusplus > 201402L
_GLIBCXX20_CONSTEXPR
typename vector<_Tp, _Alloc>::reference
#else
void
#endif
vector<_Tp, _Alloc>::
emplace_back(_Args&&... __args)
{
if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
{
_GLIBCXX_ASAN_ANNOTATE_GROW(1);
_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
std::forward<_Args>(__args)...);
++this->_M_impl._M_finish;
_GLIBCXX_ASAN_ANNOTATE_GREW(1);
}
else
_M_realloc_insert(end(), std::forward<_Args>(__args)...);
#if __cplusplus > 201402L
return back();
#endif
}
#endif
2.6、pop_back()
_GLIBCXX20_CONSTEXPR
void
pop_back() _GLIBCXX_NOEXCEPT
{
__glibcxx_requires_nonempty();
--this->_M_impl._M_finish;
_Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
_GLIBCXX_ASAN_ANNOTATE_SHRINK(1);
}
2.7、insert()
vector::insert() 函数有多种类型，如果剩余空间不能够存放插入元素，需要扩容后。
2.7.1、insert(pos, val) / vector::insert(pos, rval)
insert() 函数接受左值和右值参数，两者处理逻辑相同。
- 还有剩余空间末尾插入，在末尾构造中间插入，调用 _M_insert_aux() 函数处理
- _M_realloc_insert() 扩容插入
插入的元素可能是 vector 中已有的元素，而 _M_insert_aux() 内部会移动元素（如果元素支持移动语义操作，使用移动语义），所以当传入参数是左值时，为了放置移动后元素失效，需要构造一个临时变量，当作拷贝。
template<typename _Tp, typename _Alloc>
_GLIBCXX20_CONSTEXPR
typename vector<_Tp, _Alloc>::iterator
vector<_Tp, _Alloc>::
#if __cplusplus >= 201103L
insert(const_iterator __position, const value_type& __x)
#else
/* ... */
#endif
{
const size_type __n = __position - begin();
if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
if (__position == end()) // 插入位置在末尾，直接构造
{
_GLIBCXX_ASAN_ANNOTATE_GROW(1);
_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
__x);
++this->_M_impl._M_finish;
_GLIBCXX_ASAN_ANNOTATE_GREW(1);
}
else
{
#if __cplusplus >= 201103L
const auto __pos = begin() + (__position - cbegin());
// __x could be an existing element of this vector, so make a
// copy of it before _M_insert_aux moves elements around.
_Temporary_value __x_copy(this, __x); // 构造一个临时变量
_M_insert_aux(__pos, std::move(__x_copy._M_val())); // 移动后插入
#else
/* ... */
#endif
}
else
#if __cplusplus >= 201103L
_M_realloc_insert(begin() + (__position - cbegin()), __x); // 扩容
#else
/* ... */
#endif
return iterator(this->_M_impl._M_start + __n);
}
传入 insert() 函数的是右值，和传入左值的 insert() 逻辑相同
_GLIBCXX20_CONSTEXPR
iterator
insert(const_iterator __position, value_type&& __x)
{ return _M_insert_rval(__position, std::move(__x)); }
template<typename _Tp, typename _Alloc>
_GLIBCXX20_CONSTEXPR
auto
vector<_Tp, _Alloc>::
_M_insert_rval(const_iterator __position, value_type&& __v) -> iterator
{
const auto __n = __position - cbegin();
if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
if (__position == cend())
{
_GLIBCXX_ASAN_ANNOTATE_GROW(1);
_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
std::move(__v));
++this->_M_impl._M_finish;
_GLIBCXX_ASAN_ANNOTATE_GREW(1);
}
else
_M_insert_aux(begin() + __n, std::move(__v));
else
_M_realloc_insert(begin() + __n, std::move(__v));
return iterator(this->_M_impl._M_start + __n);
}
_M_insert_aux() 函数首先将末尾元素移动，然后再为插入元素腾地方，最后插入元素。
template<typename _Tp, typename _Alloc>
template<typename _Arg>
_GLIBCXX20_CONSTEXPR
void
vector<_Tp, _Alloc>::
_M_insert_aux(iterator __position, _Arg&& __arg)
{
_GLIBCXX_ASAN_ANNOTATE_GROW(1);
_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_ASAN_ANNOTATE_GREW(1);
#if __cplusplus < 201103L
/* ... */
#endif // 将 [pos, finish - 2) 移动到 [pos + 1, finish - 1)
_GLIBCXX_MOVE_BACKWARD3(__position.base(),
this->_M_impl._M_finish - 2,
this->_M_impl._M_finish - 1);
#if __cplusplus < 201103L
*__position = __x_copy; // 插入元素
#else
/* ... */
#endif
}
_M_realloc_insert() 的逻辑如下
- 2 被扩容
- 在插入位置出构造插入元素
- 移动原 vector 的元素
- 析构原 vector 元素，释放原 vector 内存
如果在构造或者移动元素过程中出现异常，新内存上所有已经构造的函数都会被析构，内存也被释放。
2.7.2、insert(pos, n, val)
_GLIBCXX20_CONSTEXPR
iterator
insert(const_iterator __position, size_type __n, const value_type& __x)
{
difference_type __offset = __position - cbegin();
_M_fill_insert(begin() + __offset, __n, __x);
return begin() + __offset;
}
_M_fill_insert() 定义如下，逻辑大致和 _M_realloc_insert() 相同
template<typename _Tp, typename _Alloc>
_GLIBCXX20_CONSTEXPR
void
vector<_Tp, _Alloc>::
_M_fill_insert(iterator __position, size_type __n, const value_type& __x)
{
if (__n != 0)
{
if (size_type(this->_M_impl._M_end_of_storage
- this->_M_impl._M_finish) >= __n)
{ // 剩余空间能够存放 n 数据
#if __cplusplus < 201103L
value_type __x_copy = __x;
#else
_Temporary_value __tmp(this, __x);
value_type& __x_copy = __tmp._M_val();
#endif
const size_type __elems_after = end() - __position;
pointer __old_finish(this->_M_impl._M_finish);
if (__elems_after > __n) // initialized 空间大于 n
{
_GLIBCXX_ASAN_ANNOTATE_GROW(__n);
std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
this->_M_impl._M_finish,
this->_M_impl._M_finish,
_M_get_Tp_allocator()); // 腾出位置
this->_M_impl._M_finish += __n;
_GLIBCXX_ASAN_ANNOTATE_GREW(__n);
_GLIBCXX_MOVE_BACKWARD3(__position.base(),
__old_finish - __n, __old_finish);
std::fill(__position.base(), __position.base() + __n,
__x_copy); // 填充插入元素
}
else // initialized 空间小于 n
{
_GLIBCXX_ASAN_ANNOTATE_GROW(__n);
this->_M_impl._M_finish =
std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
__n - __elems_after,
__x_copy,
_M_get_Tp_allocator()); // 在内存上构造一部分
_GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after);
std::__uninitialized_move_a(__position.base(), __old_finish,
this->_M_impl._M_finish,
_M_get_Tp_allocator()); // 腾位置
this->_M_impl._M_finish += __elems_after;
_GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after);
std::fill(__position.base(), __old_finish, __x_copy); // 填充数据
}
}
else // 扩容
{
const size_type __len =
_M_check_len(__n, "vector::_M_fill_insert");
const size_type __elems_before = __position - begin();
pointer __new_start(this->_M_allocate(__len));
pointer __new_finish(__new_start);
__try
{
// See _M_realloc_insert above.
std::__uninitialized_fill_n_a(__new_start + __elems_before,
__n, __x,
_M_get_Tp_allocator()); // 插入元素
__new_finish = pointer();
__new_finish
= std::__uninitialized_move_if_noexcept_a
(this->_M_impl._M_start, __position.base(),
__new_start, _M_get_Tp_allocator()); // 拷贝原来的元素
__new_finish += __n;
__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)
std::_Destroy(__new_start + __elems_before,
__new_start + __elems_before + __n,
_M_get_Tp_allocator());
else
std::_Destroy(__new_start, __new_finish,
_M_get_Tp_allocator());
_M_deallocate(__new_start, __len);
__throw_exception_again;
}
std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
_M_get_Tp_allocator());
_GLIBCXX_ASAN_ANNOTATE_REINIT;
_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;
}
}
}
欢迎关注公众号“源知源为”，阅读更多技术干货
#C++##STL##vector#C/C++基础 文章被收录于专栏
C/C++ 语言基础
