Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
Solved

# Best Structure...?

Posted on 2003-11-19
Medium Priority
334 Views
Last Modified: 2010-04-02
Hi,

I have a 2D structure, say an array of 352 by 288 elements and lets say the array is called CURRENT. Once i've finished processing this array I read in new values into the CURRENT array. But i want to hold onto the old values of "current" array, perphaps in an array called PREVIOUS.

I want to know the most efficient way of doing this....
1. Obviously I could just loop through filling PREVIOUS=CURRENT, and then read in the new values of CURRENT. But this seems rather computational intensive.
2. Use two arrays and flip between both for CURRENT processing. Keeping track of which array represents which might be awkward however.
3. use *some* STL - I've no knowledge however about this though and the platform i wish to write for doesnt have great support for STL anyway.
4. ????

Any thoughts?
0
Question by:trican
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• Learn & ask questions
• 7
• 3
• 3
• +2
16 Comments

LVL 1

Expert Comment

ID: 9778524
trican,

i would use 2 arrays and two pointers to these arrays (lets call them pCurrent and pPrevious). Do all processing using these pointers. Just before you want to load new values flip the pointers: if pCurrent points to Array1 then have it point to Array 2, let pPrevious point to the other array.
0

LVL 1

Author Comment

ID: 9778651
My gut feeling is that this is probably the best way too, I'm just a little afraid it might get a tad confusing. I need to do alot processing on both  arrays of data (in case you havent guessed, its image data). But then I guess the flip the pointers is a completely separate task only changed when i read in new pixel data.

{
// do processing
// pCurrent pointing at array1
// pPrevious pointing at array2

}

// read in new values
// array2 = new values
// array1 = now becomes old values
// pCurrent points at array2
// pPrevious points at array1

Actually I'm not too hot on the syntax of pointers within C++. Some guidance would be appreciated.
Thanks
0

LVL 11

Expert Comment

ID: 9778949
typedef int ImageArray[100][200];
typedef int ** ImageArrayPtr;

ImageArray A, B;
ImageArrayPtr pCurrent, pPrevious;

for (int i = 0; i < 100; ++i)
for (int j = 0; j < 200; ++j)
pCurrent[i][j] = i * j;

// process data here

ImageArrayPtr temp = pCurrent;
pCurrent = pPrevious;
pPrevious = temp;

Hope that helps, -bcl
0

LVL 7

Expert Comment

ID: 9779309
Yeah I would just do what bcladd has done and assign a pointer to it. That way you never really shift the data around. All you are going to be doing is shifting the pointer reference. It will be much more efficient. The only question I have is do you want to be able to hold on to previous arrays permanently? if so I would make previous a linked list. That way you can just keep throwing the previous one on to it.
0

LVL 1

Author Comment

ID: 9780065
Firstly, I dont need to hold onto anymore than the current and previous arrays of data.

Secondly, I'm having a few problems still.
I dont fully get what bcladd means by:
typedef int ** ImageArrayPtr;

its a pointer to a pointer ...right? whats the type of first pointer?

You define: ImageArray A, B;  ..... but dont use them or point the pointers at them.

Cheers

0

LVL 39

Expert Comment

ID: 9781014
>1. Obviously I could just loop through filling PREVIOUS=CURRENT, and then read in the
> new values of CURRENT. But this seems rather computational intensive.

If you just want to make a fast copy you may use memcpy:

...
int CURRENT[M][N]  = { 0 };
int PREVIOUS[M][N] = { 0 };

// fill CURRENT somehow

readCurrentImage(CURRENT, ...);

// save array to PREViOUS

memcpy(PREVIOUS, CURRENT, M*N*sizeof(int));
...

BTW,

typedef int ** ImageArrayPtr;

defines a pointer to int pointer array, what is incorrect in your case. If you pass your 2D matrix to a function you have a simple int*, that must be addressed as a 1D array.

Hope, that helps

Alex

0

LVL 1

Author Comment

ID: 9781385
Thanks, but I dont really want to do a fast copy, I want to avoid this overhead.

I want to proceed with the pointer structure, but I cant seem to get it to work the way i want it to. At an absolute basic level I 'm having compilation problems trying to assign the pointer to a 2D array.

I've tried:
const int mV = 288;
const int mH = 352;
int A[mV][mH];
int *pPrev = &A[0][0];
......

the fourth line gives me problems. I dont want to address it as a 1D array, i want to preserve the 2D nature. Obviously something basic i'm doing wrong.

0

LVL 11

Expert Comment

ID: 9781599
int ** pPrev = &A[0][0];

or, better

int ** pPrev  = A;

Remember that in a standard array each application of [] dereferences (removes) one layer of pointer. So an array of integers can pe assigned to a pointer to integers. An array of arrays of int requires a pointer to a pointer to int.

You're right, I never assigned A/B to my pointers in my earlier post. It doesn't matter which you assign to which to start with, so long as you do it before my first for loop. My apologies. It was my intention in my code that all access to the arrays would be through the pointers; A and B would never be used after pCurrent=A and pPrev = B

Hope this helps, -bcl
0

LVL 1

Expert Comment

ID: 9781619
const int mV = 288;
const int mH = 352;
int A[mV][mH];
int *pPrev = (int*)&A;

// fill with random values
for (int i=0;i<mV;i++)
{
for (int j=0;j<mH;j++)
{
A[i][j] = rand() % 69;
}
}

// list using pointer:
for ( i=0;i<mV;i++)
{
for (int j=0;j<mH;j++)
{
printf("%i,%i: %i\n",i,j, *(pPrev + (i * mH ) + j));
}
}
0

LVL 1

Author Comment

ID: 9781944
bcladd

const int mV = 288;
const int mH = 352;
int A[mV][mH], B[mV];
int ** pPrev  = A;

.....
ERROR Implicit cast of pointer to non-equal pointer (for this line:int ** pPrev  = A;)

Otherwise, I think I (finally!) understand how ur code is working

Thanks jploeg - the referencing is little awkward - but thats only my personal opinion for my application, I prefer bcladd appraoch if i could get it to work.
0

LVL 11

Accepted Solution

bcladd earned 400 total points
ID: 9782058
Just as you're understanding what the program is doing I realize that it won't work. The problem is that to use two indices the compiler MUST know how long each of the rows is (assuming a two dimensional array is stored in row major form). Thus the compiler is RIGHT to say it can't cast A to int**. The following program has actually been compiled and tested and produces the results I would expect. Look at the typedefs in particular and ask any questions you still have.

#include <iostream>
#include <iomanip>
using namespace std;

const int ImageWidth = 20;
const int ImageHeight = 10;

typedef int ImageArray[ImageHeight][ImageWidth];
typedef int ImageRow[ImageWidth];
typedef ImageRow * ImageArrayPtr;

int main()
{

ImageArray A, B;

ImageArrayPtr pCurrent, pPrevious;

pCurrent = A;
pPrevious = B;

for (int i = 0; i < ImageHeight; ++i)
for (int j = 0; j < ImageWidth; ++j)
pCurrent[i][j] = i * j;

for (int i = 0; i < ImageHeight; ++i) {
for (int j = 0; j < ImageWidth; ++j)
cout << setw(4) << pCurrent[i][j] << " ";
cout << endl;
}

ImageArrayPtr temp = pCurrent;
pCurrent = pPrevious;
pPrevious = temp;

for (int i = 0; i < ImageHeight; ++i)
for (int j = 0; j < ImageWidth; ++j)
pCurrent[i][j] = -i * j;

for (int i = 0; i < ImageHeight; ++i) {
for (int j = 0; j < ImageWidth; ++j)
cout << setw(4) << pCurrent[i][j] << " ";
cout << endl;
}

for (int i = 0; i < ImageHeight; ++i) {
for (int j = 0; j < ImageWidth; ++j)
cout << setw(4) << pPrevious[i][j] << " ";
cout << endl;
}
}

0

LVL 1

Author Comment

ID: 9785807
Yeah, works a treat!

"....The problem is that to use two indices the compiler MUST know how long each of the rows is (assuming a two dimensional array is stored in row major form). ...."

hmmm dont quite understand this - in ur first code "typedef int ** ImageArrayPtr;" ok i can see how the dimensions aren't defined... But there seems (well to me :-( ) still only one dimension defined in

typedef int ImageRow[ImageWidth];
typedef ImageRow * ImageArrayPtr;

So ImageArrayPtr points to a 1D array of ImageRow values (int's), so could u explain why the following works ok...

ImageArray A, B;
ImageArrayPtr pCurrent, pPrevious;
pCurrent = A;
pPrevious = B;

Or specifically how you can assign pCurrent (a pointer to 1D array) to A (a 2 D array) ..... sorry i'm a bit confused.

And one other small question.... Is it absolutely neccessary to define your own types????

Btw i've increased the points - really appreciate the help!
thanks
0

LVL 39

Expert Comment

ID: 9786652
> Or specifically how you can assign pCurrent (a pointer to 1D array) to A (a 2 D array)

typedef int Row[10];
typedef Row Matrix[10];

// you may pass by reference or by pointer
void ff(Matrix& m, Matrix* pm)
{
// you may define another alias
Matrix& mm = m;

// or use the pointer
int x = (*pm)[5][3];

// or define a pointer to the rows of m
Row*   pRows   = m;

// that you may use the same way as m

if ( pRows[2][3] == m[2][3]))
{
// always true

}

// the only difference is

int size_pRows = sizeof(pRows); // == 4      == sizeof(Row*)  size of a pointer!

int size_m        = sizeof(m);        // == 400  == sizeof(Matrix)

}

The only typedef you need is Row (or ImageRow), if you just want to access an item by [x][y].
The Matrix type is needed if you want to pass the size information of your 2D array to a function.
The RowPtr or ImageArrayPtr type is only for convenience.

Regards, Alex
0

LVL 1

Assisted Solution

jploeg earned 200 total points
ID: 9786723
the reason why you have to define the "row" type is because that's the only way to know where the second, third etc. row begins. The reason that you can assing pointer to a single row to a 2D array is because you're basically assigning a pointer to a row to an (1D) array of rows , just like you can assign an a pointer to an int to an array of int's. That's all OK, as long as it's clear how big the 'thing' you're pointing to is, so that it's clear where each element in the array starts (and where it ends).

0

LVL 1

Author Comment

ID: 9786983
aha I think I got it now.

I'm just going to play around with it just to make sure. I'll then assign points

100+ bcladd
50 jploeg
0

LVL 1

Author Comment

ID: 9807111
thanks guys
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a â€¦
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the bâ€¦
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Botâ€¦
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.
###### Suggested Courses
Course of the Month7 days, 7 hours left to enroll

#### 715 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.