テンプレート化されたsparse_vectorクラスを実装しています。これはベクトルのようなものですが、デフォルトの構築値とは異なる要素のみを格納します。
したがって、sparse_vectorは、値がT()ではないすべてのインデックスの遅延ソートされたインデックスと値のペアを格納します。
私は、数値ライブラリ内の既存のスパースベクトルに基づいて実装を行っていますが、非数値型Tも処理します。見てみましboost::numeric::ublas::coordinate_vector
たeigen::SparseVector
。
両方のストア:
size_t* indices_; // a dynamic array
T* values_; // a dynamic array
int size_;
int capacity_;
単純に使ってみませんか
vector<pair<size_t, T>> data_;
私の主な質問は、両方のシステムの長所と短所は何ですか、そしてどちらが最終的に優れているかです。
ペアのベクトルは、size_とcapacity_を管理し、付随するイテレータクラスを単純化します。また、2つではなく1つのメモリブロックがあるため、再割り当ての半分が発生し、参照の局所性が向上する可能性があります。
他のソリューションでは、検索中にキャッシュラインがインデックスデータのみでいっぱいになるため、検索が速くなる可能性があります。Tが8バイトタイプの場合、アライメントの利点もいくつかありますか?
ペアのベクトルがより良い解決策であるように私には思えますが、両方のコンテナーがもう一方の解決策を選択しました。なんで?