C++ STL 容器设计与实现分析 -- array

1、array（C++11）

array 是固定长度的数组，定义时就指定长度，一旦定义长度不能更改（不能扩容）。

  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 __array_traits<_Tp, _Nm> _AT_Type;
      typename _AT_Type::_Type                         _M_elems;
      /***/

• array 有两个模板参数：元素类型和元素个数，元素个数可以是 0
• pointer/reference/iterator 直接是元素类型相应类型

__array_traits 使用了模板偏特化支持 array 元素个数可以为 0。当元素个数为 0 时，定义了一个空类 _Type。_S_ref() 和 _S_ptr() 使用 nullptr 构造返回值。

  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>
   struct __array_traits<_Tp, 0>
   {
     struct _Type { };
     typedef true_type _Is_swappable;
     typedef true_type _Is_nothrow_swappable;

     static constexpr _Tp&
     _S_ref(const _Type&, std::size_t) noexcept
     { return *static_cast<_Tp*>(nullptr); }

     static constexpr _Tp*
     _S_ptr(const _Type&) noexcept
     { return nullptr; }
   };

1.1、data()

如果 array 元素个数为 0，data() 返回 nullptr，否则返回数组首地址。

      [[__gnu__::__const__, __nodiscard__]]
      _GLIBCXX17_CONSTEXPR pointer
      data() noexcept
      { return _AT_Type::_S_ptr(_M_elems); }

1.2、begin()/end()/front()/back()

begin() 和 end() 返回 iterator，从定义可知，迭代器就是原始指针。

      [[__gnu__::__const__, __nodiscard__]]
      _GLIBCXX17_CONSTEXPR iterator
      begin() noexcept
      { return iterator(data()); }

      [[__gnu__::__const__, __nodiscard__]]
      _GLIBCXX17_CONSTEXPR iterator
      end() noexcept
      { return iterator(data() + _Nm); }

front() 和 back() 返回的是 reference。非 const 和 const 类型实现不同，非 const 类型借助 begin() 和 end() 实现，而 const 类型使用 _S_ref() 实现。

      [[__nodiscard__]]
      _GLIBCXX17_CONSTEXPR reference
      front() noexcept
      {
    __glibcxx_requires_nonempty();
    return *begin();
      }

      [[__nodiscard__]]
      constexpr const_reference
      front() const noexcept
      {
#if __cplusplus >= 201402L
    __glibcxx_requires_nonempty();
#endif
    return _AT_Type::_S_ref(_M_elems, 0);
      }

      [[__nodiscard__]]
      _GLIBCXX17_CONSTEXPR reference
      back() noexcept
      {
    __glibcxx_requires_nonempty();
    return _Nm ? *(end() - 1) : *end();
      }

      [[__nodiscard__]]
      constexpr const_reference
      back() const noexcept
      {
#if __cplusplus >= 201402L
    __glibcxx_requires_nonempty();
#endif
    return _Nm ? _AT_Type::_S_ref(_M_elems, _Nm - 1)
                : _AT_Type::_S_ref(_M_elems, 0);
      }

1.3、operator[]/at

      // Element access.
      [[__nodiscard__]]
      _GLIBCXX17_CONSTEXPR reference
      operator[](size_type __n) noexcept
      {
    __glibcxx_requires_subscript(__n);
    return _AT_Type::_S_ref(_M_elems, __n);
      }

      _GLIBCXX17_CONSTEXPR reference
      at(size_type __n)
      {
    if (__n >= _Nm)
      std::__throw_out_of_range_fmt(__N("array::at: __n (which is %zu) "
                        ">= _Nm (which is %zu)"),
                    __n, _Nm);
    return _AT_Type::_S_ref(_M_elems, __n);
      }

欢迎关注公众号“源知源为”，阅读更多技术干货