468,253 Members | 1,286 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,253 developers. It's quick & easy.

Code puzzle?: Implementing arrays without arrays or heap

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>::operator[](int i)
//{
// return (T&)(*((int*)(this) + i));
//}

// This definition is better because it
// will work on compilers that don't
// optimize away Array<T, 0occupying
// a leading byte.
// See:
// http://www.research.att.com/~bs/bs_f...l#sizeof-empty
template<class T, int n>
T& Array<T, n>::operator[](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, 5x;

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

Aug 24 '06 #1
4 2065

k0*****@gmail.com wrote:
#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>::operator[](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>::operator[]( int i )
{
if ( i-1 == n )
{
return this->mem;
}
else
{
return Array<T, n-1 >::operator[]( 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, 5x;

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.

Aug 24 '06 #2
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!

--

Frederick Gotham
Aug 24 '06 #3
Frederick Gotham wrote:
// 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?
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 :)

Aug 24 '06 #4
Earl Purple wrote:
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>::operator[]( int i )
{
if ( i-1 == n )
{
return this->mem;
}
else
{
return Array<T, n-1 >::operator[]( 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.

Aug 24 '06 #5

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

5 posts views Thread by Jerry Coffin | last post: by
21 posts views Thread by Matteo Settenvini | last post: by
4 posts views Thread by Olumide | last post: by
2 posts views Thread by Dr Dav | last post: by
27 posts views Thread by George2 | last post: by
4 posts views Thread by honey777 | last post: by
reply views Thread by kermitthefrogpy | last post: by
reply views Thread by zattat | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.