如何實現一個sparse_vector類

Question

我正在實現一個模板化的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_，並簡化伴隨的迭代器類;它也有一個內存塊而不是兩個，所以它會導致一半的重新分配，並且可能具有更好的參考位置。

另一種解決方案可能搜索更快，因爲緩存行在搜索期間只填充索引數據。如果T是8字節類型，那麼可能還有一些對齊優勢？

在我看來，對的向量是更好的解決方案，但兩個容器都選擇了另一個解決方案。爲什麼？

Answer 1

實際上，他們似乎重新改造了車輪（可以這麼說）。

我個人認爲2個庫您的需求：

• 洛基，爲Loki::AssocVector - >過一個vector實現地圖的界面（這是你想要做的事情）
• Boost.Iterator ，其類別爲iterator_adaptor。通過Composition很容易實現一個新的容器。

這樣的話，我想指出，你不妨多一些通用的，重視從T()不同，因爲這強加T是缺省構造。你可以提供一個構造函數，它需要一個T const&。在編寫通用容器時，最好儘可能減少必要的需求（只要它不影響性能）。

另外，我想提醒你，使用儲存vector的想法是值的數量少非常好，但是你可能希望改變底層容器向經典map或unordered_map如果值的數量增長。這可能是值得剖析/計時的。請注意，STL通過容器適配器如stack提供此功能，儘管它可能會使實施稍微困難。

玩得開心。

Answer 2

將索引放在一個單獨的列表中會讓它們更快地查找 - 正如您所建議的那樣，它會更有效地使用緩存，特別是當T很大時。

如果你想實現你自己的，爲什麼不使用std::map（或std::unordered_map）？按鍵會更大，但實施時間將接近於零！