Sparse Array Template Class

• Download SparseArrayExample.zip - 6.1 KB

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.

//**********************************************************************
// Program: SparseArrayExample.cpp
//
//  Copyright (C) 2013 William Hallahan
//
//  Permission is hereby granted, free of charge, to any person
//  obtaining a copy of this software and associated documentation
//  files (the "Software"), to deal in the Software without restriction,
//  including without limitation the rights to use, copy, modify, merge,
//  publish, distribute, sublicense, and/or sell copies of the Software,
//  and to permit persons to whom the Software is furnished to do so,
//  subject to the following conditions:
//
//  The above copyright notice and this permission notice shall be
//  included in all copies or substantial portions of the Software.
//
//  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
//  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
//  OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
//  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
//  HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
//  WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
//  FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
//  OTHER DEALINGS IN THE SOFTWARE.
//**********************************************************************

#include <iostream>
#include <cstring>
#ifdef __linux__
#include <unistd.h>
#endif
#include "SparseArray.h"
#include "platform_os.h"

// Start of main program.
int _tmain(int argc, TCHAR* argv[])
{
    // Set the print mode for Unicode builds on Windows(TM).
    SET_STDOUT_MODE;

    // Declare a sparse array.
    SparseArray<unsigned int, unsigned int> x;

    // Calculate the first 20 values of the Fibonacci sequence
    // and store them in the sparse array.
    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];
    }

    // Print the first 20 values of the Fibonacci sequence.
    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

//**********************************************************************
//  File: SparseArray.h
//  Author: Bill Hallahan
//  Date: March 27, 2000
//
//  Abstract:
//
//    This class provides an implementation for a sparse array.
//
//  Copyright (C) 2000-2013 William Hallahan
//
//  Permission is hereby granted, free of charge, to any person
//  obtaining a copy of this software and associated documentation
//  files (the "Software"), to deal in the Software without restriction,
//  including without limitation the rights to use, copy, modify, merge,
//  publish, distribute, sublicense, and/or sell copies of the Software,
//  and to permit persons to whom the Software is furnished to do so,
//  subject to the following conditions:
//
//  The above copyright notice and this permission notice shall be
//  included in all copies or substantial portions of the Software.
//
//  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
//  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
//  OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
//  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
//  HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
//  WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
//  FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
//  OTHER DEALINGS IN THE SOFTWARE.
//**********************************************************************

#ifndef SPARSEARRAY_H
#define SPARSEARRAY_H

#include <map>

//------------------------------------------------------------------
//  Forward declarations.
//------------------------------------------------------------------

template <typename T_KEY, typename T_ITEM>

class SparseArray;

//------------------------------------------------------------------
//  Class definition for class SparseArrayProxy.
//
//  This is a proxy class for class SparseArray below.
//  See the book "More Effective C++" by Scott Meyers,
//  "Item 30: Proxy classes", page 213 for a detailed description
//  of proxy classes. The proxy class ideally is a nested class
//  inside the class that uses it, but many compilers do not
//  handle nested classes inside of templates correctly, so
//  the proxy is implemented as a stand-alone class.
//
//  In short, the proxy class allows determining whether
//  operator[]() for the SparseArray class is on the left side
//  or the right side of an equals sign in an expression.
//------------------------------------------------------------------

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;
};

//------------------------------------------------------------------
//  Class definition for the sparse map.
//
//  Inheritance was used here, however, it might have been
//  cleaner to use containment for the STL map container and
//  to create methods to allow accessing the map from the
//  proxy class.
//------------------------------------------------------------------

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);
};

//----------------------------------------------------------------------
//  Implementation for methods of class SparseArrayProxy.
//
//  Constructor:
//
//    SparseArrayProxy(SparseArray & sparse_array, 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)
{
}

//----------------------------------------------------------------------
//  SparseArrayProxy & operator =(const SparseArrayProxy & right_hand_side);
//----------------------------------------------------------------------

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 the item is the default item then clear the existing item
    //  at this key from the map.
    //------------------------------------------------------------------

    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
    {
        //--------------------------------------------------------------
        //  Add the item to the map at the specified key.
        //--------------------------------------------------------------

        (static_cast<std::map< T_KEY, T_ITEM, std::less<T_KEY> > &>(m_sparse_array))[m_key] = right_hand_side;
    }

    return *this;
}

//----------------------------------------------------------------------
//  SparseArrayProxy & operator =(T_ITEM & item);
//----------------------------------------------------------------------

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;
}

//----------------------------------------------------------------------
//  operator T_ITEM() const;
//----------------------------------------------------------------------

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();
    }
}

//----------------------------------------------------------------------
//  Implementation for methods of class SparseArray.
//
//  const SparseArrayProxy operator [](T_KEY key) const;
//----------------------------------------------------------------------

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);
}

//----------------------------------------------------------------------
//  SparseArrayProxy<T_KEY, T_ITEM> operator [](T_KEY 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]++;    // This will not compile.
++x[i];    // This won't compile either. 

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.