Let's reimplement (not reinvent) the wheel

いやいや, std::vector も std::list も簡単なよーに見えて,「例外安全」という4文字を考え出した途端に吐き気を催すことうけあい.マジお勧め.
何がしんどいって実装もしんどいけれどテストもしんどい.ある一定回数コピーしたら例外が飛んでくるような時限爆弾的クラス作って……う〜,どっか〜ん.
とりあえず今すぐパッと思いつくポイント.

うちの std::vector のばあい

  • insert やヴぁい(basic guarantee で良いので多少はマシ).initialized な部分と uninitialized な部分の区別かなーりやヴぁい.あと,たまには std::copy_backward のことも思い出してやってください
  • std::vector< int > v( 10, 0 ); v[6] = 1; v.insert( v.begin() + 5, v[6] ); // 落とし穴2つ
  • っていうか allocator を引数に取る uninitialized_copy/uninitialized_fill ぐらい標準で用意しててほしいにゃー
  • push_back を amortized O(1) にするために,旧バッファサイズの定数倍を新バッファのサイズにする戦略
  • その「定数倍」の定数(伸長係数)について, Andrew Koenig のお勧めは 2 じゃなくて 1.5 (ただし10年近く前の記事に書いてたことなので今も通用するのかは不明)

うちの std::list のばあい

  • std::list< int > l( 10, 0 ); // そこで Boost.TypeTraits ですよ
  • std::list の実装に sentry (番兵)使う場合は実装に一難あるかも
  • っていうか番兵ないと困るんじゃね?例えばイテレータとかイテレータとかイテレータとか
  • (例外安全な) std::list の実装のキーポイントは splice.多分ね,多分
  • merge は安定
  • そしてマージソート
  • ちなみに番兵は free store 上に確保する方法と std::list クラスのメンバとして保持する方法が考えられるけれど,後者は swap の実装がアホみたいにめんどーになる.ただし Move Semantics を考慮すると,たとえ swap が面倒でも後者を採用する意義(valid resourceless state の存在を保証すること)があるよ〜な?