C++中的稀疏向量？

Question

我有一些代码,使用类向量,我想用一个实现稀疏向量的向量来实现(即不是在向量的长度数组中记录元素,包括0,它只包含非零表一个查询表).

C++中是否有任何稀疏矢量类使用与矢量相同的接口？(这将使重构变得更加容易.)

Answer 1

Brendan正确地观察到,逻辑上矢量提供了从索引到值的映射.An std::vector使用简单数组完成此映射.但还有其他选择.

• std::unordered_map 已摊销O(1)时间操作,似乎是一个自然的替代品.
• std::map具有O(logn)操作,但常量较小,并且在此背后有更多年的优化.实际上,根据您的应用程序,它可能会更快.
• SparseHash具有与STL兼容的哈希表实现,声称优于标准unordered_map.
• C++ BTree再次提供了STL兼容map,但是使用btree而不是二叉树.他们声称显着改善了记忆(50-80%)和时间.
• BitMagic提供稀疏位向量的实现.想想稀疏std::bitset.如果这符合您的需求,它会提供比所有其他方法更大的改进.
• 最后,稀疏向量的经典方法是使用两个向量,一个用于索引,一个用于值.所以你有一个std::vector<uint> ind;和一个std::vector<value_type> val;.

这些都没有与a 完全相同的界面std::vector,但差异非常小,你可以轻松编写一个小包装器.例如,对于地图类,您需要跟踪大小和重载size()以返回该数字而不是非空元素的数量.实际上,Brendan链接到的Boost的mapped_vector就是这样做的:它在类似矢量的界面中包装了一个类似地图的类.

甲简易替换,在所有情况下的工作原理是不可能的(因为std::vector是在几乎所有情况下假定退化成一个阵列,例如.&vector[0],和通常这是使用).大多数对稀疏案例感兴趣的用户也对利用稀疏性感兴趣,因此需要暴露.例如,稀疏向量的迭代器必须迭代所有元素,包括空,这简直是浪费.稀疏结构的重点是跳过所有这些.如果你的算法无法处理,那么你就会在桌面上留下很多潜在的收益.