sparse vector in C++?
c++, stl
Solution
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.
Problem
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.)