std::arrayを頑張って読もうとした.

おはようございます.N@Nです.スペード君がstd::array諸々の話をしていたので今回はstd::arrayについて少し話してみようかと思います.

僕のC++力ではどうなるのかわからない部分もあったため,ご教授くださる方が入ればぜひ…….また,予め断っておきますが,本記事は誤りが含まれている可能性が非常に高いのでお気をつけ下さい.

では早速,STLの1つであるstd::arrayのコードの一部を以下に記そう(インデントを揃えるため,一部半角スペースのみを追加した.また,これより上にも意味のある(__array_traits)部分があるが後述する).

  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;
「ウゥーッ!」(突如泡を吹き倒れる僕)

実装がそんなに膨大でない(コメントを除くと300行に満たない)std::arrayですら全てを読もうとすると,残念ながらかなり時間が掛かってしまうので軽く概略だけ触れるとしよう.

以下の文において,std::arrayはstd::arrayの実装そのもの(コード自身)を指し,arrayは配列(boost::arrayなどではなくstd::array)を指すとする.

また,必要ならば適宜std::array - cppreference.comを参照されたい.

参照しているstd::arrayはgcc 4.9.1のものである.

C++ template

ところでこのコードを読むためにはC++のtemplateの知識が必要だ. そのため,templateに関する知識が一切無い方のためtemplateに関して少し記述するとしよう. templateとは大雑把に言えば「型に依らず」「コンパイル時処理」を行う機能である.

ここでtemplateを用いず,2つの引数の値を加算する関数を見てみよう.

double add(double a, double b) {
  return a + b;
}

特に何の変哲もないコードだ(gcc 4.9.0-の場合,関数の引数にautoが使用できるがここではそれに触れない). しかしこれはdoubleという型に関数が束縛されている.これをtemplateを用いて記述してみよう.すると

template<typename T>
T add(T a, T b) {
  return a + b;
}

このようになる.比較してみればtemplate未経験者でも読むことができると思う.引数の型が両方共intならばint型の関数となるし,doubleならばdouble型の関数だ. typename TとあるようにTが型となる.

std::array

さて,先ほどのstd::arrayのコードを見てみよう.

  template<typename _Tp, std::size_t _Nm>
    struct array
    {

型が_Tpで,サイズが_Nmのarrayというtemplateクラスを生成していることが分かる(templateの記述の後にstructとあるためクラスである).続きの

      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;

はtypedefを用いて再定義しているだけなのでこの部分についての説明は省略する.更に下にいくと,

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

コメントを読む限り,サイズが0のarrayに対してのサポートだと思うが,よく分からなかった.

ここで__array_traitsというものが現れている.__array_traitsは最初に記した意味のある部分に相当するものだったので以下に記す.

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_CONTAINER

  template<typename _Tp, std::size_t _Nm>
    struct __array_traits
    {
      typedef _Tp _Type[_Nm];

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

 template<typename _Tp>
   struct __array_traits<_Tp, 0>
   {
     struct _Type { };

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

このコードとコメントを挟んで,先程のstruct arrayが書かれていた. traitとはa particular quality in your personality*1であり,即ち宣言したarrayの特徴である.

struct __array_traitsはtypedefにより型[サイズ]の形に定義している.そしてその下の関数_S_refで(constexpr宣言されているためコンパイル時定数である)型とサイズを,返す(と思う).

struct__array_traits<_Tp, 0>は宣言されたarrayのサイズが0だった場合で,これはnullptrを返すのだろうか(arrayのサイズが0でもwell-formedだ).

ともかく,一度struct __array_traitsを見たおかげで,本記事でその前に提示した_AT_Typeの意味はarrayの型とサイズであると推測できる.というわけで次を見ていこう.

関数

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

      // DR 776.
      void
      fill(const value_type& __u)
      { std::fill_n(begin(), size(), __u); }

      void
      swap(array& __other)
      noexcept(noexcept(swap(std::declval<_Tp&>(), std::declval<_Tp&>())))
      { std::swap_ranges(begin(), end(), __other.begin()); }

fill(const value_type& __u)は引数の値でarrayを満たす関数だ.

swap(array& __other)は引数のarrayと値を全て交換する関数だ.これは型とサイズが一致している必要がある.

ここを見る限りやはり_Tp&は型とサイズで良さそうだ.

また,begin()size()end()などはイテレータであり,それはstd::arrayの続きに記してあった.

イテレータ

      // Iterators.
      iterator
      begin() noexcept
      { return iterator(data()); }

      const_iterator
      begin() const noexcept
      { return const_iterator(data()); }

      iterator
      end() noexcept
      { return iterator(data() + _Nm); }

      const_iterator
      end() const noexcept
      { return const_iterator(data() + _Nm); }

      reverse_iterator 
      rbegin() noexcept
      { return reverse_iterator(end()); }

      const_reverse_iterator 
      rbegin() const noexcept
      { return const_reverse_iterator(end()); }

      reverse_iterator 
      rend() noexcept
      { return reverse_iterator(begin()); }

      const_reverse_iterator 
      rend() const noexcept
      { return const_reverse_iterator(begin()); }

      const_iterator
      cbegin() const noexcept
      { return const_iterator(data()); }

      const_iterator
      cend() const noexcept
      { return const_iterator(data() + _Nm); }

      const_reverse_iterator 
      crbegin() const noexcept
      { return const_reverse_iterator(end()); }

      const_reverse_iterator 
      crend() const noexcept
      { return const_reverse_iterator(begin()); }

まあ妥当といったところだ.普通の関数,const修飾した関数と並んでいるが,これに関しては数も多く単純であるため特に解説する必要も無いと思うので続けていこう.

サイズに関するもの

      // Capacity.
      constexpr size_type 
      size() const noexcept { return _Nm; }

      constexpr size_type 
      max_size() const noexcept { return _Nm; }

      constexpr bool 
      empty() const noexcept { return size() == 0; }

イテレータの次はサイズに関するものが記されてあった.

arrayのサイズを返すsize()

arrayの実装上の最大のサイズを返すmax_size()

arrayが空かどうかを判定するempty()

全てサイズに関するものだ.この部分は全てconstexpr宣言されておりコンパイル時定数となっている他,普通の関数と何ら変わりない.では次を見ていこう.以下からは要素へのアクセスだ.そろそろ半分だろうか.

アクセッサ

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

      constexpr const_reference
      operator[](size_type __n) const noexcept
      { return _AT_Type::_S_ref(_M_elems, __n); }

array[n]のようにアクセスする単純なアクセッサだ.const修飾してようと大して差はない,コンパイル時定数であるだけだ.そういえば結構前に_AT_Type_M_elemsが現れていたので続きに進む前にもう1度戻ってみよう.

  template<typename _Tp, std::size_t _Nm>
    struct __array_traits
    {
      typedef _Tp _Type[_Nm];

      static constexpr _Tp&
      _S_ref(const _Type& __t, std::size_t __n) noexcept
      { return const_cast<_Tp&>(__t[__n]); }
    };
      typedef _GLIBCXX_STD_C::__array_traits<_Tp, _Nm> _AT_Type;
      typename _AT_Type::_Type                         _M_elems;

array[n]のようにアクセスした場合返ってくるのはarrayの型でもサイズでもなくarrayのn-1番目に格納されている値である.サイズnに対し,n(以降)番目の要素にアクセスしようとするとそのアドレスの値を返す.

つまり,_AT_Type::_S_ref(_M_elems, __n)はarrayの__n番目の要素ということになる.

となると,_M_elemsはarrayの要素だろうか.array自身と言うべきなのだろうか.次に進もう.

      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);
      }

      constexpr const_reference
      at(size_type __n) const
      {
    // Result of conditional expression must be an lvalue so use
    // boolean ? lvalue : (throw-expr, lvalue)
    return __n < _Nm ? _AT_Type::_S_ref(_M_elems, __n)
      : (std::__throw_out_of_range_fmt(__N("array::at: __n (which is %zu) "
                           ">= _Nm (which is %zu)"),
                       __n, _Nm),
         _AT_Type::_S_ref(_M_elems, 0));
      }

arrayはn-1番目の要素にアクセスする方法として,array[n]array.at(n)がある.これは後者だ.サイズnに対し,n(以降)番目の要素にアクセスしようとするとプログラムが中断する.

constexpr宣言された方はif文ではなく,三項演算子を用いている.C++14においてはconstexpr宣言した関数内での条件分岐の使用が可能となっているが,C++11ではそうではない.そのため,gcc 4.9.2(未確認)やそれ以降のコンパイラにおいてはif文が用いられているのかもしれない.

さて,参考程度に次の

    std::array<int, 3> a = {0, 1, 2};
    std::cout << a[10] << std::endl;

を実行した場合,684321288が出力された.また,以下の

    std::array<int, 3> a = {0, 1, 2};
    std::cout << a.at(10) << std::endl;

を実行した場合,

terminate called after throwing an instance of 'std::out_of_range'
  what():  array::at: __n (which is 10) >= _Nm (which is 3)

となった.実装と照らし合わせればこの辺りはよく分かるだろう.さあ,続きだ.

      reference 
      front() noexcept
      { return *begin(); }

      constexpr const_reference 
      front() const noexcept
      { return _AT_Type::_S_ref(_M_elems, 0); }

      reference 
      back() noexcept
      { return _Nm ? *(end() - 1) : *end(); }

      constexpr const_reference 
      back() const noexcept
      { 
    return _Nm ? _AT_Type::_S_ref(_M_elems, _Nm - 1) 
               : _AT_Type::_S_ref(_M_elems, 0);
      }

      pointer
      data() noexcept
      { return std::__addressof(_AT_Type::_S_ref(_M_elems, 0)); }

      const_pointer
      data() const noexcept
      { return std::__addressof(_AT_Type::_S_ref(_M_elems, 0)); }
    };

begin()end()イテレータであって,普段プログラムを書くとき,要素にアクセスするために使う関数ではない.

そのような場合は,front()back()を使う.

data()C++11で追加された機能だ.この辺りはC++のリファレンスが詳しいのでそちらに譲る,こっちは次へと進もう.

演算子

  // Array comparisons.
  template<typename _Tp, std::size_t _Nm>
    inline bool 
    operator==(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two)
    { return std::equal(__one.begin(), __one.end(), __two.begin()); }

  template<typename _Tp, std::size_t _Nm>
    inline bool
    operator!=(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two)
    { return !(__one == __two); }

  template<typename _Tp, std::size_t _Nm>
    inline bool
    operator<(const array<_Tp, _Nm>& __a, const array<_Tp, _Nm>& __b)
    { 
      return std::lexicographical_compare(__a.begin(), __a.end(),
                      __b.begin(), __b.end()); 
    }

  template<typename _Tp, std::size_t _Nm>
    inline bool
    operator>(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two)
    { return __two < __one; }

  template<typename _Tp, std::size_t _Nm>
    inline bool
    operator<=(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two)
    { return !(__one > __two); }

  template<typename _Tp, std::size_t _Nm>
    inline bool
    operator>=(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two)
    { return !(__one < __two); }

見て分かる通り,演算子の定義だ.定義されている演算子==!=<><=>=であるがそれぞれ比較するarrayの型とサイズが等しい必要がある.

そういえばいつだったか<=>=は小さい(resp. 大きい)の否定(大きい(resp. 小さい)か等しい)であると聞いた記憶があるがその通りの実装である.

ところで<の実装だけstd::lexicographical_compareを用いた比較となっているが、これは<の実装を用いて><=>=を実装しているためである. とりあえず次に進もう.ゴールはもう近い.

特殊な関数

  // Specialized algorithms.
  template<typename _Tp, std::size_t _Nm>
    inline void
    swap(array<_Tp, _Nm>& __one, array<_Tp, _Nm>& __two)
    noexcept(noexcept(__one.swap(__two)))
    { __one.swap(__two); }

  template<std::size_t _Int, typename _Tp, std::size_t _Nm>
    constexpr _Tp&
    get(array<_Tp, _Nm>& __arr) noexcept
    {
      static_assert(_Int < _Nm, "index is out of bounds");
      return _GLIBCXX_STD_C::__array_traits<_Tp, _Nm>::
    _S_ref(__arr._M_elems, _Int);
    }

  template<std::size_t _Int, typename _Tp, std::size_t _Nm>
    constexpr _Tp&&
    get(array<_Tp, _Nm>&& __arr) noexcept
    {
      static_assert(_Int < _Nm, "index is out of bounds");
      return std::move(get<_Int>(__arr));
    }

  template<std::size_t _Int, typename _Tp, std::size_t _Nm>
    constexpr const _Tp&
    get(const array<_Tp, _Nm>& __arr) noexcept
    {
      static_assert(_Int < _Nm, "index is out of bounds");
      return _GLIBCXX_STD_C::__array_traits<_Tp, _Nm>::
    _S_ref(__arr._M_elems, _Int);
    }

_GLIBCXX_END_NAMESPACE_CONTAINER
} // namespace std

以上でようやく長かったstdに属する部分が終了だ.最後は特殊な関数だ.

さて,またswap()が出てきた.とりあえず2つを並べてみよう.

      void
      swap(array& __other)
      noexcept(noexcept(swap(std::declval<_Tp&>(), std::declval<_Tp&>())))
      { std::swap_ranges(begin(), end(), __other.begin()); }
  template<typename _Tp, std::size_t _Nm>
    inline void
    swap(array<_Tp, _Nm>& __one, array<_Tp, _Nm>& __two)
    noexcept(noexcept(__one.swap(__two)))
    { __one.swap(__two); }

何の事はない,唯のstd::swapだ.つまり,

    std::array<int, 3> a = {0, 1, 2};
    std::array<int, 3> b = {3, 4, 5};
    a.swap(b);
    std::swap(a, b);

こうして2つの値たちは元通りだ.

さてget()に関しても述べたいところではあるがそろそろ文書が長くなりダレてくるので省略しよう.閲覧者にはリファレンスがあるんだ.さあ,もうすぐ終わりだ.

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

  // Tuple interface to class template array.

  /// tuple_size
  template<typename _Tp> 
    class tuple_size;

  template<typename _Tp, std::size_t _Nm>
    struct tuple_size<_GLIBCXX_STD_C::array<_Tp, _Nm>>
    : public integral_constant<std::size_t, _Nm> { };

  /// tuple_element
  template<std::size_t _Int, typename _Tp>
    class tuple_element;

  template<std::size_t _Int, typename _Tp, std::size_t _Nm>
    struct tuple_element<_Int, _GLIBCXX_STD_C::array<_Tp, _Nm>>
    {
      static_assert(_Int < _Nm, "index is out of bounds");
      typedef _Tp type;
    };

_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std

arrayのtemplateクラスのためのタプルインターフェースだ.std::tupleはstd::arrayをincludeしているため,どちらかと言うと,arrayのtemplateクラス「による」タプルインターフェースというべきな気もするが……どうなのだろうか…….

残念ながらこれに関して私ははっきり言えるほどの理解力も知識もない.

これ以外の部分はファイルのincludeや定義なのでこれでstd::arrayの実装を見終えた,とする.

終わりに

長い.思ったより長かった.疲れました.

実際,複数のヘッダファイルをincludeしてるからまだ続きはあるけど……キリがないので終わりとします.

実装を見ることで自身のtemplate力,C++力の低さを実感できたしいい機会だったと思います.