読者です 読者をやめる 読者になる 読者になる

脳汁portal

アメリカ在住(だった)新米エンジニアがその日学んだIT知識を書き綴るブログ

データコレクションの形式(vector/linked list/tree list/dequeue)と各々メモリの使い方

(データ)コレクション は、オブジェクトの集合を扱うための仕組みです。
メモリ上におけるデータ配置に注目しながら代表的な四つを説明します。

データ形式

vector

  • A(iteratable)であり、B(random accessible)でもある。
  • メモリは連続領域を確保しなければならなく、全ての要素の容量は同じ
    • だから規定容量× i で任意のポイントまでアクセスできる(random accessible)

http://ufcpp.net/media/ufcpp2000/stl/fig/array.png

dequeue

  • A(iteratable)
  • vectorの派生版
  • メモリの最初と末尾がくっついてる。要素をdeleteして再格納する際に容量よく使用できる

http://ufcpp.net/media/ufcpp2000/stl/fig/ringbuffer.png

linked list

  • A(iteratable)
  • 要素と次のポインタ情報を持っている
    • メモリは連続領域を確保しなくてもよいが、その分一つ一つ要素の値をチェックしていかなければいけないので遅い

http://i.stack.imgur.com/7hp0o.gif

tree list (set)

  • 樹形図のようなやつ
  • 何番目の要素を探すということや次の要素を探すというようなことは出来ない
  • ルートを示すポインタと子を示すポインターを持つ
  • valueの値がどこにあるかを調べることが得意

http://akita-nct.jp/yamamoto/lecture/2005/2E/26th/html/img2.png

アクセス性

[A]iteratable

  • 一方向でしかアクセスできず、10番目の要素にアクセスするには,1=>2=>3=>.....9=>10とたどっていかなければいけない

[B]random accesable

  • 任意の要素にアクセス出来る いきなり10番目の要素にアクセスできる