最近導入された Shift-To-Middle Array データ構造は、有望なコンセプトにもかかわらず、多くの開発者から重大な欠陥を指摘され、大きな議論を巻き起こしています。従来の std::deque、std::vector、連結リストなどのデータ構造の代替として設計されたこの新しい実装は、連続したメモリストレージを維持しながら、両端での挿入と削除を最適化することを目指しています。
無限成長問題の特定
最も重要な批判は、基本的な設計上の欠陥に集中しています：このデータ構造は、一般的なキュー操作で使用すると無限に成長します。ある開発者が議論の中で指摘したように、先頭にプッシュして末尾から削除するという標準的なキューパターンを繰り返すと、配列内の要素数が少なく一定であっても、配列は継続的にリサイズされます。
「この実装では、配列内の最大要素数が少なくても、先頭にプッシュして末尾から削除を繰り返すと無限に成長します。」
この動作は、この一般的なユースケースを不必要なメモリ割り当てやデータコピーなしに効率的に処理するリングバッファの実装とは対照的です。この成長問題は、高性能キューという主要な用途の一つにおいて、このデータ構造の実用性を根本的に損なっています。
Shift-To-Middle Array の主な特徴
- 両端での挿入と削除が償却 O(1)
- 高速なランダムアクセス（O(1)）
- 連結リストよりも優れたキャッシュ局所性
- SIMD および並列最適化をサポート
- 連続したメモリ格納（ std::deque の断片化されたブロックとは異なる）
主な批判点
- キュー的な操作（先頭への挿入、末尾からの削除）で無限に成長する
- 自明でない型（デストラクタ、ムーブコンストラクタ）に関する問題
- リングバッファ実装と比較して不必要なコピーが発生
- 効率的なランダム削除操作の欠如
- 標準アルゴリズムとの互換性のためのイテレータサポートの欠如
非自明な型に関する実装上の懸念
複数の開発者が、現在の C++ 実装は非自明な型で問題に直面するだろうと指摘しています。実装が生のメモリ上で操作しているように見えるため、デストラクタや移動コンストラクタ（std::unique_ptr のような）を持つオブジェクトは問題を引き起こす可能性があります。あるコメンテーターは、少なくとも使用を自明にコピー可能な型に制限するための静的アサーションを追加することを提案し、現在の実装の限界を強調しました。
既存のソリューションとの比較
コミュニティの議論では、代替実装に関する興味深い洞察が明らかになりました。一部の人々は、Apple の CoreFoundation CFArray や Boost の devector など、同様のアプローチがすでに存在することを指摘しました。また、この新しい構造が VecDeque（リングバッファ実装）のような確立されたソリューションに対して意味のある利点を提供するかどうかを疑問視する声もありました。
複数の開発者が自分自身の同様のデータ構造の実装を共有し、コンセプト自体には価値があるが、エッジケースとパフォーマンス特性を慎重に考慮する必要があることを示唆しました。
パフォーマンスのトレードオフ
Shift-To-Middle Array は連結リストよりも優れたキャッシュ局所性と両端での効率的な操作を約束していますが、議論ではいくつかの重要なパフォーマンストレードオフが強調されました。リサイズ中に要素を中央にシフトするという構造のアプローチには、単純なリングバッファが回避できるコピーが含まれています。
一部の開発者は、ラップアラウンドを処理するための分岐やモジュロ演算が必要なため、リングバッファのインデックス付けはわずかにコストがかかる可能性があると示唆しましたが、他の人々はそのような小さな違いは命令パイプライン処理により消えることが多いと指摘しました。一般的なユースケースを比較する包括的なベンチマークがなければ、どのアプローチが実際により良いパフォーマンスを発揮するかを判断するのは難しいです。
代替アプローチ
議論のスレッドでは、同様の問題を解決するためのいくつかの代替アプローチが明らかになりました。ある開発者は、両端に空きスペースを維持し、ポインタと3つの長さを格納する両端ベクトルについて説明しました（Vec の通常の24バイトと比較して合計32バイト）。別の開発者は、連続したビューを持つリングバッファを作成するためのメモリマッピングトリックについて言及しましたが、このアプローチにはページサイズとシステムコールのオーバーヘッドに関連する独自の制限があります。
Shift-To-Middle Array はデータ構造の世界に興味深い追加をもたらしますが、その現在の実装は一般的なユースケースには不十分です。多くの特殊なデータ構造と同様に、最適な選択は特定のアプリケーション要件、アクセスパターン、およびパフォーマンス特性に大きく依存します。この構造を検討している開発者は、特にキューのような操作における懸念される成長動作について、その利点が特定された制限を上回るかどうかを慎重に評価する必要があります。