STL源码解析--vector

CPP开发前沿

发布于 2021-11-25 14:54:05

1.1K0

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构造和内存原理

参考下面这篇文章，再次不在重复造轮子,链接如下：

从vector扩容看STL空间分配器的本质

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 -

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-11-22，如有侵权请联系 cloudcommunity@tencent.com 删除

容器

java

编程算法

c++

本文分享自 CPP开发前沿微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度

STL源码解析--vector

STL源码解析--vector

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐