STL容器们

发表于 | 分类于 |

c++中stl涉及到的容器类（或struct）有很多，具体都是什么原理呢？

std::array

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
  template<typename _Tp, std::size_t _Nm>
      struct __array_traits
      {
        typedef _Tp _Type[_Nm];
        typedef __is_swappable<_Tp> _Is_swappable;
        typedef __is_nothrow_swappable<_Tp> _Is_nothrow_swappable;

        static constexpr _Tp&
        _S_ref(const _Type& __t, std::size_t __n) noexcept
        { return const_cast<_Tp&>(__t[__n]); }

        static constexpr _Tp*
        _S_ptr(const _Type& __t) noexcept
        { return const_cast<_Tp*>(__t); }
      };
......
  template<typename _Tp, std::size_t _Nm>
      struct array
      {
        typedef _Tp                                     value_type;
        typedef value_type*                             pointer;
        typedef const value_type*                       const_pointer;
        typedef value_type&                             reference;
        typedef const value_type&                       const_reference;
        typedef value_type*                             iterator;
        typedef const value_type*                       const_iterator;
        typedef std::size_t                             size_type;
        typedef std::ptrdiff_t                          difference_type;
        typedef std::reverse_iterator<iterator>         reverse_iterator;
        typedef std::reverse_iterator<const_iterator>   const_reverse_iterator;

        // Support for zero-sized arrays mandatory.
        typedef _GLIBCXX_STD_C::__array_traits<_Tp, _Nm> _AT_Type;
        typename _AT_Type::_Type                         _M_elems;

        // No explicit construct/copy/destroy for aggregate type.
......

看这里typename _AT_Type::_Type _M_elems;再看这里typedef _Tp _Type[_Nm];。懂了吗，就是在栈上分配一个大小固定的数组。

std::vector

vector也是一个数组，只是不是分配在栈上的，而是分配在堆上的。

看这里有一个_Alloc默认使用的是std::allocator<_Tp>，这就是在堆上分配内存用的。

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
  /**
     *  @brief A standard container which offers fixed time access to
     *  individual elements in any order.
     *  
     *  @ingroup sequences
     *  
     *  @tparam _Tp  Type of element.
     *  @tparam _Alloc  Allocator type, defaults to allocator<_Tp>.
     *  
     *  Meets the requirements of a <a href="tables.html#65">container</a>, a
     *  <a href="tables.html#66">reversible container</a>, and a
     *  <a href="tables.html#67">sequence</a>, including the
     *  <a href="tables.html#68">optional sequence requirements</a> with the
     *  %exception of @c push_front and @c pop_front.
     *  
     *  In some terminology a %vector can be described as a dynamic
     *  C-style array, it offers fast and efficient access to individual
     *  elements in any order and saves the user from worrying about
     *  memory and size allocation.  Subscripting ( @c [] ) access is
     *  also provided as with C-style arrays.
  */
  template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
  class vector : protected _Vector_base<_Tp, _Alloc>
  {
#ifdef _GLIBCXX_CONCEPT_CHECKS
    // Concept requirements.
    typedef typename _Alloc::value_type               _Alloc_value_type;
# if __cplusplus < 201103L
    __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
# endif
    __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
#endif

#if __cplusplus >= 201103L
    static_assert(is_same<typename remove_cv<_Tp>::type, _Tp>::value,
        "std::vector must have a non-const, non-volatile value_type");
# if __cplusplus > 201703L || defined __STRICT_ANSI__
    static_assert(is_same<typename _Alloc::value_type, _Tp>::value,
        "std::vector must have the same value_type as its allocator");
# endif
#endif

    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;
......

再看这里定义了三个指针，用的是typedef typename _Base::pointer pointer;类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
_GLIBCXX_BEGIN_NAMESPACE_CONTAINER

  /// See bits/stl_deque.h's _Deque_base for an explanation.
  template<typename _Tp, typename _Alloc>
  struct _Vector_base
  {
    typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
      rebind<_Tp>::other _Tp_alloc_type;
    typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer
      pointer;

    struct _Vector_impl_data
    {
      pointer _M_start;
      pointer _M_finish;
      pointer _M_end_of_storage;

      _Vector_impl_data() _GLIBCXX_NOEXCEPT
      : _M_start(), _M_finish(), _M_end_of_storage()
      { }
......

指针分别叫：pointer _M_start;、pointer _M_finish;、pointer _M_end_of_storage; 之前不叫这个的，现在都改了。。。无所谓了，含义没变。。。

vector在堆上申请了一块内存，用于存放数组元素。用_M_start表示数组开始的位置，用_M_finish数据结束的位置，用_M_end_of_storage 表示这块内存容量结束的位置。

  • 当vector容量不足时，需要进行扩容，扩容会引发内存拷贝。
  • 当向vector插入、删除某些元素时，由于采用连续存储方式，也会引发内存拷贝。

扩容

刚刚提到了扩容，如果一个vector容量不足了需要扩容，应该扩多少呢？这个根据reserve()的值来决定。如果你没有设置的话，按你存入的数据量进行扩容。如果你设置了这个值，那么每次扩reserve()个。

list

To be countinue…