sparse vector in C++? [closed]

Question

I have some code, using the class vector, which I want to implement with a vector that implements sparse vectors (i.e. instead of recording the elements in an array of the vector's length, including 0's, it would only include the non-zero tables in a look-up table).

Is there any sparse vector class in C++ that makes use of the same interface that vector does? (that will make refactoring much easier.)

Answer 1

Brendan is right to observe that logically a vector provides a map from index to value. An std::vector accomplishes this mapping with a simple array. But there are other options.

• std::unordered_map has amortized O(1) time operations and seems like a natural alternative.
• std::map has O(logn) operations, but the constants are smaller and there are more years of optimizations behind this. In practice it may be faster depending on your application.
• SparseHash has an STL-compatible hashtable implementation that claims to be better than a standard unordered_map.
• C++ BTree again offers an STL-compatible map, but one that uses btrees instead of binary trees. They claim significantly improved memory (50-80%) and time.
• BitMagic offers an implementation of a sparse bit vector. Think a sparse std::bitset. If this fits your needs it offers really significant improvements over all the other approaches.
• Finally the classical approach to a sparse vector is to use two vectors, one for the index and one for the values. So you have an std::vector<uint> ind; and a std::vector<value_type> val;.

None of these have exactly the same interface as a std::vector, but the differences are pretty small and you could easily write a small wrapper. For example, for the map classes you would want to keep track of the size and overload size() to return that number instead of the number of non-empty elements. Indeed, Boost's mapped_vector that Brendan links to does exactly this: it wraps a map-like class in a vector-like interface.

A drop-in replacement that works in all cases is impossible (because a std::vector is in nearly all cases assumed to degenerate into an array, eg. &vector[0], and often this is used). Also most users who are interested in the sparse cases are also interested in taking advantage of the sparsity, hence need it exposed. For example, your sparse vector's iterator would have to iterate over all elements, including the empties, which is simply wasteful. The whole point of a sparse structure is to skip all that. If your algorithms can't handle that then you leave a lot of potential gains on the table.

Answer 2

Boost has a sparse vector. I don't think one exists in the standard library.

std::unordered_map is probably a better choice though in the long run though, unless you're already using Boost. The main annoyance in refactoring will be that size() means something different in a map vs. sparse array. Range-based for loops should make that easier to deal with though.