Compile time sparse vectors in C
Jaakko Järvi · 1997
Templates are a powerful feature of C++. In this article a template library for a special class of sparse vectors is outlined. For these vectors, the sparseness structure of the vectors can be arbitrary but must be known at compile time. In this case it suffices to store only the nonzero elements of the vectors, no indexing information about the sparseness pattern is required. The indexing information is contained in the type of the sparse vector as non-type template parameters. It is shown how common vector operators can be overloaded for the given vectors. With these operators it is possible to write abstract vector expressions between arbitrary sparse vectors. When compiled the operators yield code which performs only the necessary elementary operations between nonzero elements without any runtime penalty for the indexing of zero and nonzero elements. All indexing is performed at compile time resulting in very fast execution speed. The vector classes are best suited for short vectors up to few dozens of elements. Automatic