STL源码解析--vector
STL很好用，用起来很顺手，这大概是STL给大家的第一印象同时也说明STL受到很多C++开发者的欢迎。
序列容器是指容器中的元素是可排序的，但并不能保证都是有序的。C++中提供了Array，STL中国提供vector、list、deque、stack、queue等常用的容器结构，本文将对这些容器的一些关键部分进行分析。
1 vector
一直以来很多人都把vector当做数组使用，主要是因为操作方式相似，但vector又比数组更加灵活，数组的大小是固定的，一旦声明，后面使用过程中就不能改变。vector不同，它是可以动态扩展的，空间不够时，底层会进行扩展，主动寻找一块更大的内存，除非物理内存不够，不然vector理论上可以无限扩展。
1.1 vector定义摘要
vector发展到今日，实现代码早已被人重构过很多次。相比侯捷老师源码分析书中摘录的代码也已经发生了很大的改变，下面是从GCC中的源码摘录，它来自stl_vactor.h头文件中。
template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
class vector : protected _Vector_base<_Tp, _Alloc>
{
public:
//STL类型的定义
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;
protected:
//STL空间适配器
using _Base::_M_allocate;
using _Base::_M_deallocate;
using _Base::_M_impl;
using _Base::_M_get_Tp_allocator;
};在vector中，还有三个变量他们分别指向使用空间的头、尾以及目前可以用空间的尾，定义如下：
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
{
};
template<typename _Tp> struct _Vector_base {
struct _Vector_impl { _Tp* _M_finish; };
_Vector_impl _M_impl;
};
template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
class vector : protected _Vector_base<_Tp, _Alloc>
{
}C++11后，vector的push_back方法通过调用emplace_back方法实现，实现源码为：
void push_back(value_type&& __x)
{
emplace_back(std::move(__x));
}
#if __cplusplus > 201402L
_GLIBCXX20_CONSTEXPR
reference
#else
void
#endif
emplace_back(_Args&&... __args);在C++11后，推荐大家使用emplace_back或者empalce插入数据，从实现方式来说，比push_back更加高效，因为empalce使用了move减少了内存的拷贝操作。
1.2 vector迭代器
在1.1给出的源码摘录中可以看到以下几行：
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;从上面的定义看出，vector的迭代器就是普通的指针，在实际使用时如果我们定义一个保存了整型数据的vector迭代器，实际上就是一个整型指针，如：
vector<int>::iterator it; //迭代器
int *it; //上面d额迭代器可以等价成此形式。1.3 vector数据结构
vector是连续的空间，有三个指针分别指向了vector容器不同的位置。如：
struct _Vector_impl_data
{
pointer _M_start; //指向使用空间的头
pointer _M_finish; //指向使用空间的尾
pointer _M_end_of_storage; //指向剩余空间的尾
};使用这三个指针可以方便获取vector中头、尾元素以及对容器进行运算。
//清空容器
void clear() _GLIBCXX_NOEXCEPT
{ _M_erase_at_end(this->_M_impl._M_start); }
//返回容器开始位置
iterator begin()
{ return iterator(this->_M_impl._M_start); }
//返回容器结束位置
iterator end()
{ return iterator(this->_M_impl._M_finish); }
//返回容器已使用大小
size_type size() const _GLIBCXX_NOEXCEPT
{ return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }
//返回容器空间大小
size_type capacity() const
{ return size_type(this->_M_impl._M_end_of_storage
- this->_M_impl._M_start); }1.4 vector构造和内存原理
参考下面这篇文章，再次不在重复造轮子,链接如下：
1.5 vector元素的操作
vector中提供的操作方法很多，再次不一一列举，仅提供常用的操作方法。
- pop_back,弹出末尾元素并重新调整容器大小
//pop元素
void pop_back()
{
__glibcxx_requires_nonempty();
--this->_M_impl._M_finish;
_Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
_GLIBCXX_ASAN_ANNOTATE_SHRINK(1);
}- empalce，C++11新增方法，提升了插入元素的性能，参数传入使用右值表达式，使用完美转发保证参数类型不变。
iterator emplace(const_iterator __position, _Args&&... __args)
{ return _M_emplace_aux(__position, std::forward<_Args>(__args)...); }- insert，插入元素，使用右值表达式，通过std::move移动构造减少内存拷贝。
iterator insert(const_iterator __position, value_type&& __x)
{ return _M_insert_rval(__position, std::move(__x)); }C++20后，push_back实现也是通过调用empalce_back方法，因此如果在编译时没有启用20还是11的话在容器插入元素时推荐使用emplace和emplace_back方法。
- EOF -
腾讯云开发者
