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

vectorとlistのメモリ効率

元々は、LinkedListとArrayListのメモリ効率のお話。
ArrayListとLinkedListのメモリ効率 - ori’s diary
404 Not Found
メモリ効率というと通常、「メモリ空間をどれだけ占有するか?」というイメージで捉えられると考えられるため、
ArrayListが効率が良い筈。
(LinkedListはprevや、nextを持ち、要素を指すための新たなクラスをnewしているため)


で、
問題は、odzさんが

ArrayList より LinkedList のほうがメモリ効率が良いなんてことは多分ない。
STLvector と list なら list のほうが効率が良いこともあるかもしれないけど。
なぜかはちょっと考えてみると良い。

ArrayList と LinkedList - odz buffer

なんておっしゃっていること。
いやあ、意味深じゃありませんか。


個人的に考えられるのはSTLvectorの実装はcapacity(予めreserveしておく領域)を増やす際に、
「メモリの再配置を出来るだけさせないように」単純に「倍」にするというアルゴリズムがあり得る。(見たことがある)
要するにcapacityが256のコンテナに257番目の要素を追加したとき、capacityは512になるわけだ。
加えて、多くの場合、STLの実装はcapacityを縮小しない。
一度、capacityが512になったvectorのsizeが1になろうともそのcapacityは変わらない。
(ちなみにJavaはそういうアルゴリズムではない)


故に、場合によってはvectorよりもlistの方がメモリ効率がよくなる可能性がある……ということかしら。


まぁ、でもキャッシュなどの問題を考え、
メモリ占有サイズに留まらないメモリアクセス効率や、
最初にreserveしておくであろう戦略を考えると
多くの場合STLでもvectorが最適になっちゃうんでしょうけれどもね。