なまもの備忘録

気になったことをつらつらと書いていきます

STL std::arrayの実装を読む(読めていない)

訳あって2次元コンテナの実装を目論んだのだがどのようにすればいいかよくわからない。 何か参考になるようなソースコードを探すことにしたのだが、そこで、STLのarrayは配列を単にラップしただけ、という話を思い出した。 これは参考にするにちょうど良いのではないだろうか? と言うことで、arrayの実装の解読に挑戦しようと思う。管理人の基礎知識は非常に薄っぺらいので途中で挫折するかもしないが、とにかく今のところは全部読み通す気でいる。

実装の場所

実装を読む、といったが、まず読むべき実装を見つけなければならない。参考までに書いておくと、管理人のOSはMacOS Sierra ver 10.12.6だ。以前かすかに/usr/include以下にSTLの実装を見かけた記憶があるので探してみたのだが、c++ディレクトリはあったものの、vectorはあれどarrayが見つからなかった。はて、と思い/usr/local/include/を探したところ、c++/5.3.0ディレクトリの中にarrayがある。どうやらこれを読めば良さそうだ。読むファイルすら見つけられずに挫折しなくてよかった。

ここで少し話がそれるが、/usrと/usr/localの差が気になったので書いておこう。僕はずっと、ディレクトリ構成などと言うものはOS開発者の気まぐれで決まるのだと思っていたが、どうやらそうではないらしい。/usrだの、/etcだののディレクトリ構成をちゃんと定めている「標準」が存在するのだ。例えばUNIXオペレーティングシステムにはFHS(Filesystem Hierarchy Standard)と言う規格が存在する。 このFHSによれば、/usrとは

/usr is the second major section of the filesystem. /usr is shareable, read-only data. That means that /usr should be shareable between various FHS-compliant hosts and must not be written to. Any information that is host-specific or varies with time is stored elsewhere.

/usr以下のファイルは基本的にread-onlyであるべきで、また、ホスト(ユーザーアカウントくらいのイメージでいいのだろうか)によらない情報が格納されているべき、と言うことらしい。OSアップデートなどで変わるのもこの領域(これに/usr/local以下は入っていないというのがまた紛らわしいのだが)だそうだ。まあOS共通のシステムが入っている、くらいの認識でいい気がする。

一方、/usr/localは

The /usr/local hierarchy is for use by the system administrator when installing software locally. It needs to be safe from being overwritten when the system software is updated. It may be used for programs and data that are shareable amongst a group of hosts, but not found in /usr.

こちらは、ローカルなソフトウェア(特定のユーザーしか使わないと言う意味?)を置いておく場所、みたいのもののようだ。OSアップデートなどでも変わることはない。「ホスト」だの「ローカル」だの、定義のよくわからない言葉が並んでいて正確に意味が取れない、という感じだがまあこれくらいでいいだろう。これ以上調べていると記事の趣旨が変わってしまう。

要するに、僕の使っているC++の実装はOS X標準のよりも新しいバージョンのもの、ということのようだ。

実装

さて、本題に入ろう。/usr/local/include/c++/5.3.0/arrayの内容を見ていこうと思う。ところで、てっきり.hppなどの拡張子がついていると思っていただけに拡張子がないのに戸惑ったが、冷静に考えてみれば#include のように読み込んでいるのだから当然か。

はじめのコメント部分を読み飛ばして、ヘッダを少し眺めてみる。

#ifndef _GLIBCXX_ARRAY
#define _GLIBCXX_ARRAY 1

#pragma GCC system_header

#if __cplusplus < 201103L
# include <bits/c++0x_warning.h>
#else

#include <stdexcept>
#include <bits/stl_algobase.h>
#include <bits/range_access.h>

パッと見てわかるのは冗長インクルードガードと例外処理のためのだろうか。あとはどうしても必要になり次第見ていくことにして、とりあえず先に進む。

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

      static constexpr _Tp*
      _S_ptr(const _Type& __t) noexcept
      { return const_cast<_Tp*>(__t); }
    };

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

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

さて、こいつはなんなんだろう。namespaceと、その下の_GLIBCXX_BEGIN_NAMESPACE_CONTAINER(プリプロセッサマクロで定義された文字列だろう)はいいとしてその下だ。構造体_array_traitsを定義しているのはわかるのだが、しょっぱなからarrayの構造体かクラスが出てくると思っていたばかりに戸惑ってしまった。

まずはじめのtypedef _Tp _Type[_Nm]だが、これは確か配列のtypedefだ。typedefは基本的に

typedef 古い型名 新しい型名

と書くものだが、配列の時だけ

typedef 配列要素の古い型名 新しい型名[配列要素の個数]

という書き方になる。紛らわしいしusingを使って欲しいが、文句を言っても仕方がないか。

つまりここでは、テンプレレート第1引数の型の要素を第2引数個持った配列を_Typeと定義し直していることになる。arrayの中身のそのものという雰囲気の部分が出てきたぞ。

次に、その下の関数を見てみる。

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

これはなんだろう。どうやら配列の要素型の参照(_Tp&)を返すメンバ関数のよう。staticなので静的メンバ関数ということもわかる。静的メンバ関数とは、構造体やクラスの型の方と結びついている関数で、つまり、オブジェクトを作っていない段階でも呼び出すことができるものだ。対比して、オブジェクトに結びつけて使うメンバ関数は動的メンバ関数と呼ばれたりする。関数内部でconst_castが使われているので、どうも第1引数として渡した配列要素の参照、の第2引数番目のconstを外すための関数、らしい。constexprが付いているのは、この関数についてはコンパイル時に扱う型の情報が全てで揃うからだろう。

さて、noexceptだけよく分からない。これはなんだ?

c++日本語リファレンスによれば、C++11から追加された機能みたいだ。

throwキーワードによる例外仕様の代替。関数がどの例外を送出する可能性があるかを列挙するのではなく、例外を送出する可能性があるかないかのみを指定する。例外を送出する可能性がある関数にはnoexcept(false)を指定し、例外を送出する可能性がない関数にはnoexcept(true)もしくはnoexceptを指定する

この関数は例外を送出する可能性がない、ということを言っているらしい。なるほど、これでこの関数については大体わかったんじゃないだろうか。これが分かれば、その下の関数も自ずと何をしているのか分かる。同じことを配列そのもののポインタについてやっているだけだ。

では、二つ目の構造体はなんなのだろう。

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

と宣言されていることから、どうやら上で定義した構造体のテンプレート引数が0個の場合について部分特殊化していることがわかる。 中身まで見ていこう

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

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

まず初の行の、struct _Type {}についてだ。はじめ、上で定義した型_Typeを下で使っているのかと思い、そんなことができるのか??と小一時間頭を悩ませたのだが、なんのことはない、特に何もしない構造_Typeを宣言しているだけだった。 関数の方は、内部でnullptrのcastをしている。空の配列のキャストをしようとしているので、エラーのような情報を返したいのだろうが、これはどういうことなのだろうか。c++日本語リファレンスを見るに、単に特定の型のポインタが空なことはnullptrを特定の型のポインタに入れることによって表すみたいだ。ただ不思議なのは、代入するだけでも暗黙に型変換されるはずのnullptrがわざわざ明示的にstatic_castされていることだ。しかもその後に関節参照演算子を作用させている。これってコンパイルエラーで落ちるんじゃないの?どういうこと?むしろこの部分特殊化された関数が呼ばれる場合は必ずコンパイルエラーで落ちるようになっているのだろうか。(追記:後日職場の先輩に聞いたのだが、これは未定義動作を確実に表現するためのもの出そうだ。大きさ0の配列へのアクセスは標準に未定義であることが記されているらしい。)

試しに

template<typename T>
T& func(T x)
{
    return *static_cast<T*>(nullptr);
}

int main(){
    func(10);
    return 0;
}

をコンパイルしてみると

test.cpp:8:12: warning: binding dereferenced null pointer to reference has
      undefined behavior [-Wnull-dereference]
    return *static_cast<T*>(nullptr);
           ^~~~~~~~~~~~~~~~~~~~~~~~~
test.cpp:12:5: note: in instantiation of function template specialization
      'func<int>' requested here
    func(10);
    ^

のようにコンパイルできてしまう。その上関数内で起こっているのはint型ポインタへキャストされたnullptrへのでリファレンスにも関わらずコンパイラはnullptrへのデリファレンスと主張している。(追記:コンパイル時にコンパイラが未定義だと教えてくれている。未定義動作であることを表したいのであれば、実装は目的にかなっているものだと言える。)

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

次の関数は割と分かりやすい。単に配列の要素型の空のポインタを返しているだけだ。

さて、ここを超えるとarrayの実装らしいところが見えてくる。やっとだ。とりあえず全体をざっと見てみよう。

    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.

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

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

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

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

      reference
      at(size_type __n)
      { ... }

      constexpr const_reference
      at(size_type __n) const
      { ... }

      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
      { ... }

      pointer
      data() noexcept
      { return _AT_Type::_S_ptr(_M_elems); }

      const_pointer
      data() const noexcept
      { return _AT_Type::_S_ptr(_M_elems); }
    };

おお!それっぽいぞ。やっと求めていたものに巡り会えた。一部{ … }でで書かれている部分は実装を省略している。この部分もいずれは見ていけたらいいが、今はとりあえず置いておきたい。

さてまず気になるのは、この構造体、コンストラクタが明示的に定義されていないのだ。はて、arrayは統一初期化記法による初期化ができたと思うのだが、これはデフォルトコンストラクタがなくてもできるのだろうか。統一初期化記法による初期化とは下記のような初期化のことだ。

std::array<int, 4> ar{1, 2, 3, 4};

今回はメンバ変数が配列一つだからいいものの、複数あった場合、ユーザー定義のコンストラクタがないとどの配列を初期化すれば良いのか分からなくなってしまわないだろうか。それとも、今回のような、メンバ変数に配列が一個だけある場合だけ特別扱いされているのか?

今回のarrayのようなコンパイラ自動生成のコンストラクタしか持たない(正確にはメンバ変数も同様の性質を持っている必要があるが)型のことを「POD型」と言ったりする。この概念の説明は(http://nekko1119.hatenablog.com/entry/20120709/1341800447)の記事がとても分かりやすかった。しかし、POD型の統一初期化記法を調べて見てもいまいち欲しい情報が出てこない。しばらくあてどもなくインターネットを彷徨っていたのだが、MicrosoftのC++リファレンスページに「集約の初期化」という話を見つけた。

集約の初期化は、リストの初期化の一形態であり、次のような配列またはクラス型 (多くの場合は構造体や共用体) に使用されます。

  • プライベートまたはプロテクト メンバーでない。

  • 明示的に既定化または削除したコンストラクターを除いて、ユーザー定義のコンストラクターがない。

  • 基底クラスを持たない。

  • 仮想メンバー関数がない。

  • 非静的メンバーの中かっこまたは等号の初期化子がない。

まさにarrayクラスじゃないか。どうもこれは集約(aggregate)に相当するクラスらしい。それを知った上でコードをよく見てみれば、確かにコメントに// No explicit construct/copy/destroy for aggregate type.と書いてある。コメントはちゃんと読むべきだな。

リンク先の解説を読んで貰えればわかると思うが、aggregate typeに対する統一初期化は早くに宣言された変数から順に初期化されていくらしい。そして、配列がある場合はその配列も先頭から埋められていく(この話は別記事aggregate typeの初期化子リストによる初期化で試している)。今回の場合、後で見ていくが、メンバ変数は_AT_Type::_Type型の_M_elemsだけなので_M_elemsが先頭から順に埋められていくことになる。なるほど。コンストラクタがないのはむしろ統一初期化記法を適用できるようにするためなのか。

arrayを読み切るみたいな大言壮語を吐いてましたけど、今読めてるのはここまでです。ん〜先は長い。

また後日更新しようと思います。