C++中的稀疏向量？

Question

我有一些代码，使用类向量，我想用实现稀疏向量的向量来实现它(也就是说，它将只包含在查找表中的非零表，而不是记录在向量长度的数组中的元素，包括0)。

C++中是否有使用向量所做的相同接口的稀疏向量类？(这将使重构更加容易。)

Answer 1

Brendan正确地观察到，从逻辑上说，向量提供了一个从索引到值的映射。一个std::vector用一个简单的数组来完成这个映射。但还有其他选择。

• std::unordered_map对O(1)时间操作进行了摊销，这似乎是一种自然的选择。
• std::map有O(logn)操作，但常量较小，并且在此基础上有更多年的优化。实际上，它可能会更快，取决于您的应用程序。
• SparseHash有一个与STL兼容的hashtable实现，声称它比标准的unordered_map更好。
• C++ BTree再次提供了一个与STL兼容的map，但它使用btree而不是二叉树。他们宣称改进内存(50-80%)和时间是重要的。
• BitMagic提供了稀疏位向量的实现。想一想稀疏的std::bitset。如果这符合您的需要，那么与所有其他方法相比，它确实提供了显著的改进。
• 最后，对于稀疏向量的经典方法是使用两个向量，一个用于索引，另一个用于值。所以你有一个std::vector<uint> ind;和一个std::vector<value_type> val;。

它们都没有与std::vector完全相同的接口，但是差别很小，您可以轻松地编写一个小包装器。例如，对于映射类，您需要跟踪大小和重载size()，以返回该数字，而不是非空元素的数量。事实上，Brendan链接到的Boost的向量正是这样做的:它将类似于映射的类封装在类似向量的接口中。

在所有情况下，插入替换都是不可能的(因为std::vector几乎在所有情况下都被假定为退化为数组，例如。&vector[0]，而且经常使用这种方法)。而且，大多数对稀疏情况感兴趣的用户也对利用稀疏性感兴趣，因此需要公开它。例如，稀疏向量的迭代器必须遍历所有元素，包括空元素，这是非常浪费的。稀疏结构的全部要点是跳过所有这些。如果您的算法不能处理这一点，那么您将留下许多潜在的收益在桌面上。

Answer 2

Boost有一个稀疏向量。我觉得标准图书馆里不存在。

不过，从长远来看，std::unordered_map可能是一个更好的选择，除非您已经在使用Boost。重构的主要麻烦在于，size()在映射和稀疏数组中的含义不同。但是，基于范围的for循环应该使处理起来更容易。