データコレクションの形式(vector/linked list/tree list/dequeue)と各々メモリの使い方
(データ)コレクション は、オブジェクトの集合を扱うための仕組みです。
メモリ上におけるデータ配置に注目しながら代表的な四つを説明します。
データ形式
vector
- A(iteratable)であり、B(random accessible)でもある。
- メモリは連続領域を確保しなければならなく、全ての要素の容量は同じ
- だから規定容量× i で任意のポイントまでアクセスできる(random accessible)
linked list
- A(iteratable)
- 要素と次のポインタ情報を持っている
- メモリは連続領域を確保しなくてもよいが、その分一つ一つ要素の値をチェックしていかなければいけないので遅い
tree list (set)
- 樹形図のようなやつ
- 何番目の要素を探すということや次の要素を探すというようなことは出来ない
- ルートを示すポインタと子を示すポインターを持つ
- valueの値がどこにあるかを調べることが得意
アクセス性
[A]iteratable
- 一方向でしかアクセスできず、10番目の要素にアクセスするには,1=>2=>3=>.....9=>10とたどっていかなければいけない
[B]random accesable
- 任意の要素にアクセス出来る いきなり10番目の要素にアクセスできる
