Code puzzle?: Implementing arrays without arrays or heap

Discussion in 'C++' started by k04jg02@gmail.com, Aug 24, 2006.

  1. Guest

    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>::eek: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>::eek: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;
    }
     
    , Aug 24, 2006
    #1
    1. Advertising

  2. Earl Purple Guest

    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>::eek: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>::eek:perator[]( int i )
    {
    if ( i-1 == n )
    {
    return this->mem;
    }
    else
    {
    return Array<T, n-1 >::eek: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.
     
    Earl Purple, Aug 24, 2006
    #2
    1. Advertising

  3. 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
     
    Frederick Gotham, Aug 24, 2006
    #3
  4. Guest

    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, 2006
    #4
  5. Guest

    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>::eek:perator[]( int i )
    > {
    > if ( i-1 == n )
    > {
    > return this->mem;
    > }
    > else
    > {
    > return Array<T, n-1 >::eek: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.
     
    , Aug 24, 2006
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Michal Slocinski

    Heap dump file size vs heap size

    Michal Slocinski, Mar 25, 2008, in forum: Java
    Replies:
    1
    Views:
    772
    GArlington
    Mar 25, 2008
  2. viki
    Replies:
    6
    Views:
    625
    Erik Wikström
    Jun 28, 2008
  3. Giampaolo Rodola'
    Replies:
    4
    Views:
    278
    Josiah Carlson
    Aug 5, 2008
  4. Tassilo Horn
    Replies:
    9
    Views:
    410
    Tassilo Horn
    Mar 27, 2009
  5. Raymond Schanks
    Replies:
    0
    Views:
    592
    Raymond Schanks
    Apr 11, 2010
Loading...

Share This Page