CArray: A simple but highly efficient improvement

• Download demo project - 17 Kb

Introduction

If you use CArray, and the const keyword, your programs might be running 50% too slow! Interested? Well read on...

Background

I love Object-Oriented programming. And after 15 years of writing C programs, I'd be quite happy to code in C++ forever.

Two of the things I love most are: templates and the const keyword.

If you're like me, you use const everywhere. It encapsulates encapsulation. Well kind of... Anyway, if I can pass a const reference or const pointer, I will. Why? Because it means that my calling routine knows that its data is safe. It reduces complexity.

Templates speak for themselves. Well actually, they don't...and the syntax sucks (I have to race to a text book every time I want to create a template - that either means the syntax sucks or I'm stupid or maybe I just drink too much red wine...).

Anyway, Microsoft has written several useful template classes, including CArray. It's a pity they did such a poor job, particularly with the documentation.

What's wrong with CArray?

I've been burned by CArray several times. My code works fine, but then I discover a whole lot of unnecessary copying going on.

CArray is fine for arrays of ints and doubles, but give it a class with more than a few bytes of data, and your program's efficiency gets clobbered.

Here's the kind of thing I like to do:

 //
 // Declare a useful class.
 //
class MyClass
{
protected:
    // data here (maybe lots)
public:
    // etc. etc. etc. etc
};

typedef CArray<MyClass,MyClass&> MyClassArray;

Then, I'll use this array as follows:

MyFunction(const MyClassArray& array)
{
    for (int ii = 0 ; ii < array.GetSize() ; ii++)
        DoSomething(array[ii]);
}
DoSomething(const MyClass& my_object)
{
    // do stuff here
}

Pretty simple, right? But with CArray, the call to DoSomething(array[ii]) creates a temporary copy of the array element (in this case, MyClass) before calling DoSomething! Then the temporary copy is destroyed before the next loop iteration.

If my array element is an int, that's fine by me. But if it's a class with 1K of data, then CArray is silently stabbing me in the back.

Of course, to be fair, CArray isn't "silent". Its operator[] const and GetAt methods are documented to return a copy.

But WHY?

I can't think of any good reason (unless CArray is only designed for arrays of ints etc.) why these methods return a copy. They should return a const reference.

After getting burned for the Nth time, I've done something about it.

The Solution

I've made a simple derivation of the template class CArray, called OCArray (OC stands for Open Concepts - one of my companies). Or, if you like, it can mean "Optimised-CArray".

/*
 * Template Class: OCArray
 * Author: Russell Robinson
 * Purpose:
 *    To provide a generic array class like CArray without the problems.
 *    OCArray takes one parameter - TYPE.  Unlike CArray, OCArray always
 *    returns references and expects references as parameters.
 */
template <class TYPE> class OCArray : public CArray<TYPE,TYPE&>
{
public:
    /*
     * Method: OCArray::operator[] const
     * Parameters: i_index the array index to access
     * Returns: const TYPE& reference to the element at the index
     * Author: Russell Robinson
     * Purpose:
     *    To return an element of the array for const access.
     */
    inline const TYPE&    operator[](int i_index) const
    {
        ASSERT(0 <= i_index && i_index < GetSize());
        return (GetData()[i_index]);
    };

    /*
     * Method: OCArray::GetAt
     * Parameters: i_index the array index to access
     * Returns: const TYPE& reference to the element at the index
     * Author: Russell Robinson
     * Purpose:
     *    To return an element of the array for const access.
     */
    inline const TYPE&    GetAt(int i_index) const
    {
        ASSERT(0 <= i_index && i_index < GetSize());
        return (GetData()[i_index]);
    };

    /*
     * Method: OCArray::operator[]
     * Parameters: i_index the array index to access
     * Returns: TYPE& reference to the element at the index
     * Author: Russell Robinson
     * Purpose:
     *    To return an element of the array for possible modification.
     *    This method is needed because the compiler
     *    loses the base class's method.
     */
    inline TYPE& operator[](int i_index)
    {
        ASSERT(0 <= i_index && i_index < GetSize());
        return (GetData()[i_index]);
    };
};

Just use OCArray instead of CArray. It only takes one parameter, because the argument type is implied as being a reference. This also helps remind you that you're not using CArray.

The result is that there is no copying when you access the array through a const reference or pointer.

The time saving is around 50% in an optimized program, and can be 75% in a debug version!

The above is all you need, but I've provided a demonstration project so that you can see the difference.

Now we can think about what we'll do with all those spare CPU cycles......