4

我正在实现一个模板化的 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 字节类型，也可能有一些对齐优势？

在我看来，对向量是更好的解决方案，但两个容器都选择了另一个解决方案。为什么？

4

2 回答 2

2

将索引放在单独的列表中会使它们查找起来更快 - 正如您所建议的，它将更有效地使用缓存，特别是在 T 很大的情况下。

如果你想实现自己的，为什么不直接使用std::map（或std::unordered_map）？密钥会更大，但实现时间将接近于零！

于 2010-05-11T06:28:57.210 回答
1

实际上，他们似乎重新发明了轮子（可以这么说）。

我个人会根据您的需要考虑 2 个库：

  • Loki，for Loki::AssocVector-> 在 a 上实现的地图接口vector（这是您想要做的）
  • Boost.Iterator，对于它的iterator_adaptor类。通过 Composition 实现新容器变得非常容易。

作为一个评论，我会注意到你可能希望更通用一点的值不同于 ，T()因为这强加T为 DefaultConstructible。您可以提供一个构造函数，它采用T const&. 在编写通用容器时，最好尽量减少必要的要求（只要不影响性能）。

另外，我要提醒您，使用vectorfor 存储的想法对于少量值非常有用，但您可能希望将底层容器更改为经典容器，map或者unordered_map如果值的数量增加。这可能值得分析/计时。请注意，STL 通过容器适配器（如 ）提供了这种能力stack，尽管它可能会使实现稍微困难一些。

玩得开心。

于 2010-05-11T07:00:10.447 回答