Introduction
The SparseArray
template class defined in file SparseArray.h is especially useful when you can have a very large index into an array, but most of the array indexes below that large index will never be written. The
SparseArray
index is really a key and because the SparseArray
is a template class, the key type and the item type stored in the array can be almost any types.
The only requirements for the data types used in the
SparseArray
template are the that
T_KEY
type used to declare the template must provide operator <, which is the less-than operator, and the
T_ITEM
type must provide operator== and a default constructor. All intrinsic, or built-in, types provide the less-than operator, operator==, and a default constructor.
The SparseArray is really an associative container.
I didn't have to implement the container code, the SparseArray inherits from the STL map template class. The SparseArray class provides the
array-like behavior.
This is an efficient implementation of a SparseArray
, however, it is obviously not nearly as time-efficient as using
a regular array. Use this either when the key type is not an integer type, the maximum index in the array is very large and the data is sparse,
or achieving maximum performance doesn't matter.
I tested this on Windows(TM) using Visual Studio 2008 and on Linux using G++.
Background
I wrote the
SparseArray
template class after reading Scott Meyer's excellent book, "More Effective C++". In that book he demonstrates how to use a proxy class to differentiate between the left and right hand side of an expression. I copies the idea and merely applied it to an STL map container.
("Effective C++"
and his book "Effective STL", both also by Scott Meyer, are excellent too. If you write C++, then
whether you use this code or not, I highly recommend reading these
books).
The next two paragraphs will only make sense if you study the SparseArray
template code.
I should probably be chastised, because I did two things Scott Meyer states to NOT do. First, my class inherits from an STL map, and I overrode a non-virtual method,
that is, operator[]. The inherited STL map's operator[] is hidden. While technically bad, in this case, you never want to access that anyway.
The right thing to do is to use containment, that is make a private data member in the
SparseArray
template class that is an STL map, and then to implement the necessary methods that the
SparseArrayProxy
class needs in the SparseArray
template class. Whew! In my defense, I believe (perhaps incorrectly?) that would be less efficient, and I was using this template to implement a mathematical algorithm where both efficiency and scalability mattered.
Because I used inheritance, you get all the methods of an STL map in the
SparseArray
template, although I never have used them. It might be useful to use the STL map's 'size' method to obtain how many items are currently in the map.
See "Points Of Interest" below for other limitations of the SparseArrray
template.
List of Files
- SparseArrayExample.cpp - Program that uses the SparseArray template. This program calculates the first 20 values in the Fibonacci sequence.
- SparseArray.h - Implements the SparseArray template.
- platform_os.h - File to allow compiling on Windows and Linux
- SparseArrayExample.sln - A Visual Studio 2008 solution file
- SparseArrayExample.vcproj - A Visual Studio 2008 project file
- Makefile - For building on Linux
Using the code
The
SparseArrayExample.cpp file shows how to use the SparseArray
template class. In short, you include the
SparseArray.h file in your C++ file and then start using the container. The program calculates the first 20 items of the Fibonacci sequence. Of course, it's not necessary to use a
SparseArray
for this application. I chose this because it is both simple to follow and shows how easy it is to use the template.
#include <iostream>
#include <cstring>
#ifdef __linux__
#include <unistd.h>
#endif
#include "SparseArray.h"
#include "platform_os.h"
int _tmain(int argc, TCHAR* argv[])
{
SET_STDOUT_MODE;
SparseArray<unsigned int, unsigned int> x;
const int max_fibonacci_index = 20;
x[0] = 1;
x[1] = 2;
for (int i = 2; i < max_fibonacci_index; ++i)
{
x[i] = x[i-2] + x[i-1];
}
for (int j = 0; j < max_fibonacci_index; ++j)
{
STD_COUT << j << _T(" ") << x[j] << std::endl;
}
return 0;
}
If the code were to access a key value, or index value in the program above, that was never added to the container, then the value the default constructor supplies to the item in the container is returned. For any built-in numeric type, that value is 0.
Also, if the user inserts a value that equals the default value, then the key and item are deleted in the internal map.
The SparseArray Template Class
#ifndef SPARSEARRAY_H
#define SPARSEARRAY_H
#include <map>
template <typename T_KEY, typename T_ITEM>
class SparseArray;
template <typename T_KEY, typename T_ITEM>
class SparseArrayProxy
{
public:
SparseArrayProxy(SparseArray<T_KEY, T_ITEM> & sparse_array, T_KEY key);
SparseArrayProxy & operator =(const SparseArrayProxy<T_KEY, T_ITEM> & right_hand_side);
SparseArrayProxy & operator =(T_ITEM item);
operator T_ITEM() const;
private:
SparseArray<T_KEY, T_ITEM> & m_sparse_array;
T_KEY m_key;
};
template <typename T_KEY, typename T_ITEM>
class SparseArray : public std::map< T_KEY, T_ITEM, std::less<T_KEY> >
{
public:
const SparseArrayProxy<T_KEY, T_ITEM> operator [](T_KEY key) const;
SparseArrayProxy<T_KEY, T_ITEM> operator [](T_KEY key);
};
template <typename T_KEY, typename T_ITEM>
SparseArrayProxy<T_KEY, T_ITEM>::SparseArrayProxy(SparseArray<T_KEY, T_ITEM> & sparse_array,
T_KEY key)
: m_sparse_array(sparse_array),
m_key(key)
{
}
template <typename T_KEY, typename T_ITEM>
SparseArrayProxy<T_KEY, T_ITEM> &
SparseArrayProxy<T_KEY, T_ITEM>::operator =(const SparseArrayProxy<T_KEY, T_ITEM> & right_hand_side)
{
if (T_ITEM(right_hand_side) == T_ITEM())
{
typename SparseArray<T_KEY, T_ITEM>::iterator it = m_sparse_array.find(m_key);
if (it != m_sparse_array.end())
{
m_sparse_array.erase(it);
}
}
else
{
(static_cast<std::map< T_KEY, T_ITEM, std::less<T_KEY> > &>(m_sparse_array))[m_key] = right_hand_side;
}
return *this;
}
template <typename T_KEY, typename T_ITEM>
SparseArrayProxy<T_KEY, T_ITEM> &
SparseArrayProxy<T_KEY, T_ITEM>::operator =(T_ITEM item)
{
(static_cast<std::map< T_KEY, T_ITEM, std::less<T_KEY> > &>(m_sparse_array))[m_key] = item;
return *this;
}
template <typename T_KEY, typename T_ITEM>
SparseArrayProxy<T_KEY, T_ITEM>::operator T_ITEM() const
{
typename SparseArray<T_KEY, T_ITEM>::iterator it = m_sparse_array.find(m_key);
if (it != m_sparse_array.end())
{
return (*it).second;
}
else
{
return T_ITEM();
}
}
template <typename T_KEY, typename T_ITEM>
const SparseArrayProxy<T_KEY, T_ITEM> SparseArray<T_KEY, T_ITEM>::operator [](T_KEY key) const
{
return SparseArrayProxy<T_KEY, T_ITEM>(const_cast< SparseArray<T_KEY, T_ITEM> & >(*this), key);
}
template <typename T_KEY, typename T_ITEM>
SparseArrayProxy<T_KEY, T_ITEM> SparseArray<T_KEY, T_ITEM>::operator [](T_KEY key)
{
return SparseArrayProxy<T_KEY, T_ITEM>(*this, key);
}
#endif
As mentioned earlier, The T_ITEM
type must implement both operator== and a default constructor. If the class doesn't implement operator== and you cannot change the code for the class, there are two solutions. I prefer the first solution.
You can add a global function that uses operator < to implement operator==, like:
bool operator==(const ClassName & instance_0, const ClassName & instance_1)
{
bool is_not_equal = (instance_0 < instance_1) || (instance_1 < instance_0);
return !is_not_equal
}
Or, if you really want, you can modify the following line of the SparseArrray
template:
if (T_ITEM(right_hand_side) == T_ITEM())
to be:
if ((!(T_ITEM(right_hand_side) < T_ITEM()) && (!(T_ITEM() < T_ITEM(right_hand_side))))
Compiler issues:
Modern C++ changed template definitions to use:
template typename
instead of:
template class
This change was made because types other than class-types can be used in template definitions.
I updated the template to use the more modern definition, which is template typename
.
I had originally used the older
template class
kewords because years ago I ran into an issue with one compiler that hadn't implemented the
typename
keyword correctly in all case. This works fine now.
Points of Interest
While accessing the values using operator[]
works, code such as:
x[i]++; ++x[i];
will not work. Decrementing with -- won't compile either
Those lines of code won't compile because the SparseArray
class and the
SparseArrayProxy
class do not overload operator++()
and
operator++(int)
.
I chose not to implement those operators because the
SparseArray
class can be used as an associative array with other types. For example, the following declaration is valid:
SparseArray<std::string, std::string> m_dictionary;
Since using ++ with std::string
makes no sense, and wouldn't compile, I chose to limit the interface so the class could be more flexible.
History
- Initial post.
- Defined
STD_COUT
in file platform_os.h. Changed template to use the keyword typename
. The code has now been tested on Linux. Updated article text. Thank you to users for feedback regarding errors.
I'm an electrical engineer who has spend most of my career writing software. My background includes Digital Signal Processing, Multimedia programming, Robotics, Text-To-Speech, and Storage products. Most of the code that I've written is in C, C++ and Python. I know Object Oriented Design and I'm a proponent of Design Patterns.
My hobbies include writing software for fun, amateur radio, chess, and performing magic, mostly for charities.