kikairoya https://blog.hatena.ne.jp/kikairoya/ kikairoya’s diary https://kikairoya.hatenablog.com/ ソフトウェア C++ STLの一翼を担うdeque(デックと読むらしい)ですが、その性能に比していまいち知名度が低いようです。 そこで、少しdequeについておさらいしましょう。 dequeの構造 まずは、dequeの期待される内部構造から。 といっても、非常に単純で、std::vector *>とほぼ等価と考えてかまいません。固定長の領域(ページと呼ぶ)へのポインタを配列にして管理している構造です。 これにより、vectorと違い、begin() -- end()の範囲がメモリ上で連続していることは期待できません。が、両端への挿入による再確保が発生しても全要素の移動にはならないため、償却定数時間のvector::… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkikairoya.hatenablog.com%2Fentry%2F20100718%2F1279465696" title="そろそろstd::dequeについて語ろうか - kikairoya’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2010-07-18 00:08:16 rich https://kikairoya.hatenablog.com/entry/20100718/1279465696 1.0 100%