ものすごく雑にlibstdc++のvectorの実装でcapacity決めているところを追う

std::vectorのメンバ関数push_back/emplace_backなどを使っているときにlibstdc++の実装だとcapacityが倍づつ増えていくのですが、それがソースコードのどこに該当するか調べました。

C++ の string と vector の reserve() の挙動 - bkブログ 2009年のこの記事によれば

その代わり、「指数的な成長ポリシー」は _M_insert_aux() の中で実装されています。

のこと。ただ、その後C++11やらC++14やらが来るうちに実装もちょっと変わって、_M_check_lenというのが担当するようになったようです。

      // Called by _M_fill_insert, _M_insert_aux etc.
      size_type
      _M_check_len(size_type __n, const char* __s) const
      {
        if (max_size() - size() < __n)
          __throw_length_error(__N(__s));
        const size_type __len = size() + std::max(size(), __n);
        return (__len < size() || __len > max_size()) ? max_size() : __len;
}

相変わらずlibstdc++のソースコードのインデントはこの世のものとは思えない汚さだ。実装している連中の脳みそはどうなってやがるんだ・・・。

アロケータ絡みでチェックコードが入ってますが要はsize() + std::max(size(), __n)この部分が倍々ゲームを担当しているようです。

これがどこから呼び出されているかをオーバーロードとか無視して雑に調べて図にしました。