Code puzzle?: Implementing arrays without arrays or heap

[k04jg02]

I was thinking that it would be cool if a programming language could
implement an array type in its standard library rather than depending
on arrays being a builtin type. I wondered if C++ could do this.
Obviously, writing a class that just used a C array under the hood
would be cheating. As would simply allocating a big chunk of memory on
the heap -- for it to be a true equivalent of a C array it should be
allocate memory on the stack.

I came up with the following compileable solution but I'm not sure it
will always work. I don't know if the standard somehow mandates that
the 'mem' members will be contiguous. I figured out a way to make it
work on some nonoptimizing compilers (see comment below) but I'm
curious if anyone has a way to make it even more safe. Or an
alternative way altogether.

#include <cstdlib>
#include <iostream>

using namespace std;

template<class T, int n>
class Array : public Array<T, n-1>
{
public:
T& operator[](int i);

protected:
T mem;
};

//// Works on gcc 3.4 but probably
//// breaks on nonoptimizing compilers
//template<class T, int n>
//T& Array<T, n>:perator[](int i)
//{
// return (T&)(*((int*)(this) + i));
//}

// This definition is better because it
// will work on compilers that don't
// optimize away Array<T, 0> occupying
// a leading byte.
// See:
// http://www.research.att.com/~bs/bs_faq2.html#sizeof-empty
template<class T, int n>
T& Array<T, n>:perator[](int i)
{
// Should be able to just use line below
// but some compilers are stupid
// return *(&(Array<T, 1>::mem) + i);

int& x = Array<T, 1>::mem;
return *(&x + i);
}

template<class T>
class Array<T, 0> {};

int main(int argc, char *argv[])
{
Array<int, 5> x;

cout << sizeof(Array<int, 5>) << endl; // 20 as expected

x[0] = 9;
x[1] = 8;
x[2] = 4;
x[3] = 2;
x[4] = 5;

// Prints correctly
cout << x[0] << x[1] << x[2] << x[3] << x[4] << endl;

return 0;
}

 

[Earl Purple]

#include <cstdlib>
#include <iostream>

using namespace std;

template<class T, int n>
class Array : public Array<T, n-1>
{
public:
T& operator[](int i);

protected:
T mem;
};

You could also use an aggregation relationship here. Now if you pass
this array about as a reference to a smaller array there will be no
problem, but there is the danger of it not having a virtual destructor.

//// Works on gcc 3.4 but probably
//// breaks on nonoptimizing compilers
//template<class T, int n>
//T& Array<T, n>:perator[](int i)
//{
// return (T&)(*((int*)(this) + i));
//}

Undefined behaviour though, you are relying on how the compiler outlays
your class. I was more expecting you to do this:

template < typename T, int n >
T& Array<T,n>:perator[]( int i )
{
if ( i-1 == n )
{
return this->mem;
}
else
{
return Array<T, n-1 >:perator[]( i );
}
}

template<class T>
class Array<T, 0> {};

This class in my implementation will need operator[] to throw a bounds
exception, so it would do bounds-checking.

It would also make operator[] an O(N) operation, as well as filling up
the call stack, so I wouldn't recommend programming arrays this way.

int main(int argc, char *argv[])
{
Array<int, 5> x;

cout << sizeof(Array<int, 5>) << endl; // 20 as expected

x[0] = 9;
x[1] = 8;
x[2] = 4;
x[3] = 2;
x[4] = 5;

// Prints correctly
cout << x[0] << x[1] << x[2] << x[3] << x[4] << endl;

return 0;
}

You're lucky then.

 

[Frederick Gotham]

posted:

template<class T, int n>
class Array : public Array<T, n-1>

Very nice!

// Should be able to just use line below
// but some compilers are stupid
// return *(&(Array<T, 1>::mem) + i);

What compiler wouldn't "understand" that?

If "mem" weren't protected, then your template class would be a POD. You
could then be certain that mem is located right at the beginning of the
object in memory.

The thing to watch out for is padding at the end of the object (i.e. after
"mem").

Very nice code -- I particularly like the recursive inheritance!

 

[k04jg02]

What compiler wouldn't "understand" that?

gcc 3.4 on windows :/

If "mem" weren't protected, then your template class would be a POD. You
could then be certain that mem is located right at the beginning of the
object in memory.

Wait, so long as the member is public, then it's guarunteed to be laid
out in memory that way? I'm guessing for backwards compatibility with C
structs?

The thing to watch out for is padding at the end of the object (i.e. after
"mem").

Right, but hopefully you'd only have to worry about that if you went
past the end of the array (which is just as likely to give you odd
behavior with a normal array).

Very nice code -- I particularly like the recursive inheritance!

Thanks

 

[k04jg02]

Undefined behaviour though, you are relying on how the compiler outlays
your class. I was more expecting you to do this:

template < typename T, int n >
T& Array<T,n>:perator[]( int i )
{
if ( i-1 == n )
{
return this->mem;
}
else
{
return Array<T, n-1 >:perator[]( i );
}
}

That would work but would be pretty big performance hit over normal
arrays. You're adding a branch to every element access and making them
recursive (although tail recursive so not too terrible). The check also
defeats the point of specializing Array for <T, 0>. You might as well
include that as a case to check for to.