Solved

Best Structure...?

Posted on 2003-11-19
16
329 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
Comment
Question by:trican
  • 7
  • 3
  • 3
  • +2
16 Comments
 
LVL 1

Expert Comment

by:jploeg
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

by:trican
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

by:bcladd
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

by:jj819430
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

by:trican
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

by:itsmeandnobodyelse
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

by:trican
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

by:bcladd
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
What Security Threats Are You Missing?

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

 
LVL 1

Expert Comment

by:jploeg
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

by:trican
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

by:
bcladd earned 100 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

by:trican
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

by:itsmeandnobodyelse
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

by:jploeg
jploeg earned 50 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

by:trican
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

by:trican
ID: 9807111
thanks guys
0

Featured Post

Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

Suggested Solutions

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

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

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

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now