472,992 Members | 3,338 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 472,992 software developers and data experts.

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 2378

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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

5
by: Jerry Coffin | last post by:
Jerry Coffin wrote: > > > Q7 Remove duplicates in array > > > > You can't really "remove" an element from an array, so this is poorly > > defined. If it was a C++ vector (for example) std::sort...
21
by: Matteo Settenvini | last post by:
Ok, I'm quite a newbie, so this question may appear silly. I'm using g++ 3.3.x. I had been taught that an array isn't a lot different from a pointer (in fact you can use the pointer arithmetics to...
19
by: chris | last post by:
Hello, I've recently been trying to understand the various structures supplied by c++, and the one I find most confusing is deque. One quick question about this. It seems most implementations...
5
by: Gomaw Beoyr | last post by:
Hello Is there any explanation why Microsoft chose to implement arrays as objects allocated on the heap instead of structs allocated on the stack? For "mathematical stuff", one normally...
18
by: Mike Bartels | last post by:
Hi Everyone! I have two Arrays A and B. Both arrays are byte arrays with 7 bytes each. The contents of array A and B are the same A = {1, 2, 3, 4, 5, 6, 7}; B = {1, 2, 3, 4, 5, 6, 7}; When...
4
by: Olumide | last post by:
Hello - I have two classes A and B as follows: class B{ public: ~B(){ cout << "destroying B" << endl; } }; class A{
2
by: Dr Dav | last post by:
Hello all, I'm a physicist whose rewriting a numerical simulation, previously written in IDL, in C with the goal reducing runtime. As you may imagine, my C programming skills are quite poor but I...
27
by: George2 | last post by:
Hello everyone, Should I delete memory pointed by pointer a if there is bad_alloc when allocating memory in memory pointed by pointer b? I am not sure whether there will be memory leak if I do...
4
by: honey777 | last post by:
Problem: 15 Puzzle This is a common puzzle with a 4x4 playing space with 15 tiles, numbered 1 through 15. One "spot" is always left blank. Here is an example of the puzzle: The goal is to...
0
by: lllomh | last post by:
Define the method first this.state = { buttonBackgroundColor: 'green', isBlinking: false, // A new status is added to identify whether the button is blinking or not } autoStart=()=>{
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 4 Oct 2023 starting at 18:00 UK time (6PM UTC+1) and finishing at about 19:15 (7.15PM) The start time is equivalent to 19:00 (7PM) in Central...
0
by: Aliciasmith | last post by:
In an age dominated by smartphones, having a mobile app for your business is no longer an option; it's a necessity. Whether you're a startup or an established enterprise, finding the right mobile app...
0
tracyyun
by: tracyyun | last post by:
Hello everyone, I have a question and would like some advice on network connectivity. I have one computer connected to my router via WiFi, but I have two other computers that I want to be able to...
1
by: Teri B | last post by:
Hi, I have created a sub-form Roles. In my course form the user selects the roles assigned to the course. 0ne-to-many. One course many roles. Then I created a report based on the Course form and...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 1 Nov 2023 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM) Please note that the UK and Europe revert to winter time on...
3
by: nia12 | last post by:
Hi there, I am very new to Access so apologies if any of this is obvious/not clear. I am creating a data collection tool for health care employees to complete. It consists of a number of...
0
isladogs
by: isladogs | last post by:
The next online meeting of the Access Europe User Group will be on Wednesday 6 Dec 2023 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, Mike...
3
SueHopson
by: SueHopson | last post by:
Hi All, I'm trying to create a single code (run off a button that calls the Private Sub) for our parts list report that will allow the user to filter by either/both PartVendor and PartType. On...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.