vectorとlistのメモリ効率
元々は、LinkedListとArrayListのメモリ効率のお話。
ArrayListとLinkedListのメモリ効率 - ori’s diary
404 Not Found
メモリ効率というと通常、「メモリ空間をどれだけ占有するか？」というイメージで捉えられると考えられるため、
ArrayListが効率が良い筈。
（LinkedListはprevや、nextを持ち、要素を指すための新たなクラスをnewしているため）
で、
問題は、odzさんが
ArrayList より LinkedList のほうがメモリ効率が良いなんてことは多分ない。
ArrayList と LinkedList - odz buffer
STL の vector と list なら list のほうが効率が良いこともあるかもしれないけど。
なぜかはちょっと考えてみると良い。
なんておっしゃっていること。
いやあ、意味深じゃありませんか。
個人的に考えられるのはSTLのvectorの実装はcapacity（予めreserveしておく領域）を増やす際に、
「メモリの再配置を出来るだけさせないように」単純に「倍」にするというアルゴリズムがあり得る。（見たことがある）
要するにcapacityが256のコンテナに257番目の要素を追加したとき、capacityは512になるわけだ。
加えて、多くの場合、STLの実装はcapacityを縮小しない。
一度、capacityが512になったvectorのsizeが1になろうともそのcapacityは変わらない。
（ちなみにJavaはそういうアルゴリズムではない）
故に、場合によってはvectorよりもlistの方がメモリ効率がよくなる可能性がある……ということかしら。
まぁ、でもキャッシュなどの問題を考え、
メモリ占有サイズに留まらないメモリアクセス効率や、
最初にreserveしておくであろう戦略を考えると
多くの場合STLでもvectorが最適になっちゃうんでしょうけれどもね。
