C のvectorの要素アクセス

From HongoWiki
Jump to: navigation, search

このページのメンテナ

  • 桜井壮希 ( sakurai _at_mark_ juno.phys.s.u-tokyo.ac.jp )

Maintainer of this page

  • Soki Sakurai ( sakurai _at_mark_ juno.phys.s.u-tokyo.ac.jp )


C++標準のSTLにはvectorというテンプレートクラスが用意されています。動的配列を扱うもので、配列の要素数が変わりうる場合に使用します。

vectorの要素アクセスには、イテレータを除けば2種類の方法があり、atメソッドを使う方法と[ ]演算子を使う方法とがあります。

両者ともランダムアクセスなので定数時間で済みますが、at()ではインデックスがout_of_rangeかどうかのチェックを行うため、[ ]に比べて倍ぐらい時間がかかります。

なので、try&catchしない場合や、範囲内のインデックスしか指定しないという確信がある場合は、後者を使うようにしましょう。

ちなみに、定数時間で済むのは各要素がメモリ上で必ず連続になっているためです。可変のリストには自己参照構造体などを使う方法がありますが、

それだと一般にシーケンシャルアクセスとなり、要素を取ってくるのに<math>o(N)</math>の時間がかかってしまいます。

stlのvectorでは、まず領域を余剰に確保しておいて、それでも足りなかった場合は新たにその倍?の領域を別の番地に確保し、もとのデータをそこにコピーします。

とすると、先頭要素のポインタを保持していて、後でpush_backしすぎたら、いつの間にか死にポインタになってしまうような。(要検証。誰か暇でしたら)

Personal tools