libstdc++の実装の調べ方(dequeの場合)

C++のデータ構造の実装を調べたいと思った時のソースコードの追い方と簡単なTIPSです。

• Webベースでよい場合

stdlibc++はdoxygenがあるのでそれを見ればよいです。
例: std::_Deque_iterator
...のですが、データ構造の実装を調べる段階ではクラスの構造もよくわかっていないと思うので難しいかと思います。

• ソースコードのダウンロード / 探し方

gnu/gcc(例: 10.1.0)からtar.gzをダウンロードして伸張します。以下、dequeを調べてみます。

wget https://ftp.gnu.org/gnu/gcc/gcc-10.1.0/gcc-10.1.0.tar.gz
tar zxfv gcc-10.1.0.tar.gz
cd gcc-10.1.0
# 目当てのファイルを探す
find . | grep deque
  ...
  ./libstdc++-v3/include/std/deque
  ./libstdc++-v3/include/debug/deque
  ./libstdc++-v3/include/bits/stl_deque.h
  ./libstdc++-v3/include/bits/deque.tcc
  ./gcc/testsuite/gnat.dg/show_deques_priority.adb
  ./gcc/testsuite/gnat.dg/deques.ads

このうち、以下の２つに注目します。

• ./libstdc++-v3/include/bits/stl_deque.h

最初に読むべきファイルです。dequeの場合はクラス自体の構造体定義やメンバ変数がvirtualで定義されています。さらに、実装やTIPSの説明が含まれています。

• (ない場合もある)./libstdc++-v3/include/bits/deque.tcc
  tccには詳細なメンバ関数の実装が含まれています。例えば、dequeであれば

    deque<_Tp, _Alloc>::insert(iterator __position, const value_type& __x)
    {
      if (__position._M_cur == this->_M_impl._M_start._M_cur)
        {
          push_front(__x);
          return this->_M_impl._M_start;
        }
      else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
        {
          push_back(__x);
          iterator __tmp = this->_M_impl._M_finish;
          --__tmp;
          return __tmp;
        }
      else
        return _M_insert_aux(__position._M_const_cast(), __x);
   }
...

といったコードが含まれ、データ構造の挙動を知ることができます。

TIPS: libstdc特有のprefixを削って読む

先ほど紹介したコードは_M_や__が多く出現し読みにくいです。sedなどで不要そうなパターンを削除して読むと良いです。

cat ./libstdc++-v3/include/bits/deque.tcc | 
  sed -e 's/__//g' -e 's/_M_//g' -e 's/_S_//g' -e 's/difference_type//g' |
  less

以下のように読みやすくなりました。

    deque<_Tp, _Alloc>::insert(const_iterator position, const value_type& x)
    {
      if (position.cur == this->impl.start.cur)
        {
          push_front(x);
          return this->impl.start;
        }
      else if (position.cur == this->impl.finish.cur)
        {
          push_back(x);
          iterator tmp = this->impl.finish;
          --tmp;
          return tmp;
        }
      else
        return insert_aux(position.const_cast(), x);
   }

TIPS

• ほとんどのメモリ確保にはmallocが使われず、allocatorが使われることを知っておくと読みやすいです。
  allocatorについては 江添亮のC++入門 vectorの実装 : 基礎