可変長配列に要素を追加する処理の色々 - Qiita

これは何？ go の slice や C++ の std::vector のようなものに要素を追加する場合に世の人々がどうするのかを調べた。 そもそも いわゆる可変長配列というものの代表的な実装は 適当にメモリ確保して、そこに要素を格納する 確保した容量に入らなくなったら、別の場所にメモリを確保して、そこに全部移動してから新要素を追加する というものになっている。 この「別の場所にメモリを確保」の際にどうするのかが悩みどころ。 必要サイズぴったりにメモリ確保すると「1個追加」を1000回行った場合に絶望的に遅くなる。 多めに確保したいところだけど、多すぎるのはやっぱり損。 みんなどうしているのかなと思って調べてみた。 各実装 go の slice https://github.com/golang/go/blob/go1.18.1/src/runtime/slice.go#L193 辺りに