2D Dynamic Arrays

Pages: 12
Disch (13742)
When you start feeling better, would you mind explaining why is that such a bad idea? :D


It's obfuscated and inhibits your options for implementation because some of the internals are somewhat exposed.

Although most of my illness came from my hatred of multidimentional arrays, which this approach exacerbates.

It is also highly probable that he wants to test known algorithms found on the internet. And what will the 2D array syntax of these algorithms be? This one -> "array[i][j]". No?


What algorithms are you talking about?

The only thing I can think of would be matrix multiplication/etc, in which case this is a false assumption because matrices are almost always objectified and are hardly ever accessed with [x][y] syntax (at least in the code I've seen). And those aren't even really algorithms anyway.

Matrixes aren't even really dynamic 2D arrays anyway (they're generally not resizable).


When the OP decides that he doesn't want to make any more changes and he feels ready to build the release version of his game engine, he can just get rid of that stuff and implement his 2D array in the fastest and most unsafe way he can imagine.


So when he doesn't want to make any more changes, he can go back and change everything? Seems kind of silly to me. Why not just do it a practical way from the get-go?

But if he does that from the beginning, it will most certainly slow down the development of his project considerably.


That's what the precompiler is for. Bound checking and other "slow but safe" stuff is put behind #ifdefs.

Flip a switch and they're gone.

The whole foo.at(y).at(x) that was suggested is even worse.
m4ster r0shi (2201)
Disch wrote:
some of the internals are somewhat exposed

How is that? Row is a private class whose only public member is the [] operator. I mean you can't do something like this:

DynamicArray2D::Row & row=array[i];

because Row is a private class.

Neither can you do something like this:

array[i].resize(1234);

because row_data is a private member of the Row class.

Disch wrote:
What algorithms are you talking about?

Well, to be honest, I don't know. I've never tried game programming so far... But I'm not only referring to graphics algorithms. I was talking in general, anything that can fit in a game engine that manipulates dynamic 2D arrays. Of course, since matrices are not dynamic arrays, it doesn't have anything to do with them.

EDIT: Or, you could also do it for matrices just for the bounds checking feature.

Disch wrote:
That's what the precompiler is for. Bound checking and other "slow but safe" stuff is put behind #ifdefs.

Flip a switch and they're gone.

Disch, that means that you have to place #ifdef s aaaaaall around your code (because you can't modify the behavior of the [] operator of a vector without making a wrapper for it). In the way I suggest, you only have to do that in one place.

Disch wrote:
Why not just do it a practical way from the get-go?

And what would that be?
Last edited on
Disch (13742)
How is that? Row is a private class whose only public member is the [] operator.


I suppose I chose my words poorly there. Touche

I was talking in general, anything that can fit in a game engine that manipulates dynamic 2D arrays.


Dynamic 2D arrays aren't really in many algorithms. They're typically just used for large chunks of data lookup (like a world map being a 2D array of tiles or the like).

Disch, that means that you have to place #ifdef s aaaaaall around your code (because you can't modify the behavior of the [] operator of a vector without making a wrapper for it)


No, it just means you have to make a wrapper for it -- which is what he's doing.

In the way I suggest, you only have to do that in one place.


Actually, you'd have to do it twice, because you have two seperate [] operators that need to bounds check.

Four times if you want to be const correct.

And what would that be?


Exactly what he was doing originally: Overloading the () operator to have 2 params.
m4ster r0shi (2201)
Mmmm... So, you don't disagree that my method is a good way to have both the [][] syntax and bounds checking, but you say that having the [][] syntax is not really necessary. Ok, I can't really argue on that last one because (as I stated before) I'm not familiar with game programming, so I'll have to trust you.
Last edited on
Disch (13742)
Mmmm... So, you don't disagree that my method is a good way to have both the [][] syntax


Your method is probably the best way to get the [][] syntax.

My argument is that the [][] syntax gains you nothing and the hoops you have to jump through to accomplish it aren't worth it. The () operator works just fine.
m4ster r0shi (2201)
Disch wrote:
Your method is probably the best way to get the [][] syntax.

`(^o^)'

Disch wrote:
My argument is that the [][] syntax gains you nothing and the hoops you have to jump through to accomplish it aren't worth it. The () operator works just fine.

Ok.
m4ster r0shi (2201)
Though, on second thought, this looks quite good to me:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
 
template <class T>
class DynamicArray2D
{
private:

    int numberOfRows;
    int numberOfColumns;

#ifdef DEBUG

    class Row
    {
        friend class DynamicArray2D;

        vector<T> row_data;

    public:

        T & operator[](int i)
        {
            if (row_data.size()<=i) throw(911);
            return row_data[i];
        }
    };

    vector<Row> data;

#else //RELEASE

    vector<vector<T> >data;

#endif

public:

    DynamicArray2D() : numberOfRows(0), numberOfColumns(0) {}

    void resize(int row, int column)
    {
        numberOfRows = row;
        numberOfColumns = column;

        data.resize(row);

        for (int i = 0; i < row; ++i)
        {
            
#ifdef DEBUG

            data[i].row_data.resize(column);

#else //RELEASE

            data[i].resize(column);

#endif

        }
    }

#ifdef DEBUG

    Row & operator[](int i)
    {
        if (numberOfRows<=i) throw(911);
        return data[i];
    }

#else //RELEASE

    vector<T> & operator[](int i)
    {
        return data[i];
    }

#endif

};

Some notes:

->Both the debug and the release version of the code use the [][] syntax.

This is good for two reasons:
(1) The debug and the release version use the same syntax.
(2) That syntax is the common 2D array syntax.

->The debug version offers bounds checking.

->The release version is probably as fast as it can be, bearing in mind that the compiler inlines the involved function calls.

Of course, in the release version the inner vector is exposed, but this really isn't a problem as you would switch from debug to release just before your final compilation.

Disch, what do you think?
Disch (13742)
m4ster r0shi wrote:

This is good for two reasons:
[snip]
(2) That syntax is the common 2D array syntax.


That's kind of my thing -- I dont' see that as a good thing. Personally I find [y][x] syntax to generally be harder to follow. But besides that....

Downsides include:
1) double indirection (ie slower) (multidimentional via 2 vectors = 2x the indirection)
2) more memory consumed than necessary (ie bulkier) (again due to 2 vectors)
3) inconsistent types returned from [] operator.

(also, throwing '911' is kind of silly -- it'd be better to throw a range error: http://cplusplus.com/reference/std/stdexcept/range_error/ -- but whatever. I figured you're doing that just because he did in his original example?)

#1 and 2 can be avoided with this approach if you do the [y*width+x] lookup, but doing that via double brackets and a Row class is even more clutter and unnecessarily complicated code. On the other hand, 2x vectors does make natural resizing quite a bit easier (not that it's impossible the other way -- but it's certainly more work)

#3 isn't as big of a deal since Row is private -- but that pretty much means the only way you can use this class is with the double brackets (using single brakets isn't an option).

So what's the point of double brakets? Isn't the benefit of using them the option that you can only use one if you want?

You're also cluttering the entire class with #ifdefs since the class is defined totally differently for both builds. It'd probably be better to just write two different classes and #ifdef the whole thing rather than futily trying to #ifdef only bits and pieces. But of course that means double maintanance, somewhat duplicate code.

It's just ugly on so many levels. And for what?

I'm tempted to write my own class for contrast, but it's so late.

EDIT: "doing it right" with placement new and shifting everything around when you resize would actually be a considerable amount of work. You wouldn't really be able to use vector for that.

I could even implement [y][x] (without bounds checking) as well as (x,y) -- but I don't think that'd be a good idea as [y][x] would have more overhead and lacks bounds checking, and leads to bad habits.
Last edited on
m4ster r0shi (2201)
Disch wrote:
Downsides include:
1) double indirection (ie slower) (multidimentional via 2 vectors = 2x the indirection)
2) more memory consumed than necessary (ie bulkier) (again due to 2 vectors)
3) inconsistent types returned from [] operator.

1) + 2) I don't know about that. I mean, of course you're right that access time is slower (let's put the memory consumption issue aside, since speed is the main thing here) but mind that 2 vectors offer faster resizing (if you use one vector you'd have to add some more code to take care of the issue you noticed with resizing - you'd have to copy some elements to the right places). Now, is this enough to choose 2 vectors over 1? I believe it is. You see, this is a class for resizable arrays, and if an array is resized more frequently than it is accessed then it's worth making the resizing part faster. After all, if you plan not to resize it for a long time, you can just copy it to a normal 2D array and access the data from there. No?

3) I don't think this is a problem.

Disch wrote:
also, throwing '911' is kind of silly

Haha, of course that wasn't meant to stay like this. I did it to save some typing.

Disch wrote:
You're also cluttering the entire class with #ifdefs since the class is defined totally differently for both builds. [...] But of course that means double maintenance, somewhat duplicate code.

What kind of maintenance would a [] operator need?

Disch wrote:
I'm tempted to write my own class for contrast, but it's so late.

I can wait. After all, I will live forever... :)

EDIT: Ah, I see you noticed that resizing using 1 vector is no trivial task... ;)
Last edited on
Disch (13742)
m4ster r0shi wrote:
but mind that 2 vectors offer faster resizing (if you use one vector you'd have to add some more code to take care of the issue you noticed with resizing


Only for resizing the width. Other than that resize times would be comparable.

Now, is this enough to choose 2 vectors over 1? I believe it is. You see, this is a class for resizable arrays, and if an array is resized more frequently than it is accessed then it's worth making the resizing part faster.


I disagree.

Arrays will never be resized more frequently than they're accessed. If they are, you're doing something horribly wrong.

Resizing is actually extremely infrequent compared to access.

After all, if you plan not to resize it for a long time, you can just copy it to a normal 2D array and access the data from there. No?


That's nonsense. If you copy to another array then what is the point of using the dynamic array at all?

3) I don't think this is a problem.


1
2
3
4
5
6
7
8
9
10
11
12
 
void somefunction(vector<int>& foo)
{
  // do some stuff with foo
}

void somethingelse()
{
  Array2D<int> bar(10,10);

  somefunction( bar[3] );  // works sometimes, doesn't work other times
     // inconsistent
}


What kind of maintenance would a [] operator need?


Since you have two classes (one for debug and one release), any time you make a change to the class, you must remember to change both classes.

EDIT: Ah, I see you noticed that resizing using 1 vector is no trivial task... ;)


You could simplify it if you just reassigned stuff. But then it would have slightly different behavior from vector (which moves stuff around with placement new).

Just reassigning would be trivial though, would work just fine for 99% of applications, and is something the OP would be capable of doing on his own I'm sure.

But yeah, "doing it right" definately is not trivial. I'll concede that.
m4ster r0shi (2201)
Disch wrote:
Resizing is actually extremely infrequent compared to access.

If that's the case, then why bother to wrap a vector<T> or a vector<vector<T> > to begin with? You can just wrap a T pointer (and play with new/delete for resizing). It's faster and you can add safety nets if you want as you wrap it.
Disch (13742)
That's exactly what my class would be.

I'm not a fan of vector<vector<T> >, and vector<T> wouldn't really work for a 2D array if you want to "do it right" with placement new.
Topic archived. No new replies allowed.
Pages: 12