Is it possible to swap arrays of structs (in linear time)?

Question

I have a small program computing the forces of planets on each other. My program has two arrays of structs, one that holds the positions and velocities before iterations, and the other holds what their positions and velocities will be after the iterations.

At the end of each iteration, I'd like to move the values from the second array into the first and the second array can become garbage (but needs to point to some valid memory location I can write to later). I thought I could simply switch the arrays since an array is a pointer, but the compiler won't let me.

Consider this example:

typedef struct { int a; } Foo;

int main()
{
   Foo bar[8], baz[8];

   Foo *temp = baz;
   baz = bar;   //ISO C++ forbids the assignment of arrays
   bar = temp;  //incompatible types in assignment of Foo* to Foo[8]
}

This is what I'd like to do. It would certainly be faster than a for loop from 1 to N.

Answer 1

You should consider using std::vector which can be swapped in constant time:

std::vector<Foo> bar(8), baz(8);

std::swap(bar, baz);

Or if you don't want to do that and instead want to manually manage your memory, you can use new[] to get a pointer to an array on the free store and swap the pointers when you want to swap the arrays.

If you must have your arrays on the stack, the only way to do this without actually swapping each element would be to create the arrays on the stack and instead of using the arrays, use pointers to the arrays:

Foo bar[8], baz[8], *pbar = bar, *pbaz = baz;

// ...
// this code only using pbar and pbaz
// ...

// swap the pointers
std::swap(pbar, pbaz);

// ...
// use pbar and pbaz some more
// ...

Answer 2

Here's where you went wrong:

since an array is a pointer

This is not true. Arrays decay to a pointer, but they are not the same thing.

However you can easily do what you want here by actually getting pointers from those arrays.

   Foo bar[8], baz[8];

   // load bar up with valid data
   Foo *data = bar;
   Foo *garbage = baz;

   // compute next step

   std::swap(data,garbage);

Also consider using std::array rather than raw arrays (it has properties more consistent with other types in C++ and is less 'special' than raw arrays). Then when you use pointers to these arrays the size of the array won't be discarded the way it is for pointers to raw arrays.

   std::array<Foo,8> bar, baz;

   std::array<Foo,8> *data = &bar;
   std::array<Foo,8> *garbage = &baz;

   // compute next step

   std::swap(data,garbage);

If you need dynamically sized arrays use std::vector, and then you can just swap the vectors directly rather than swapping pointers to the vectors, because swapping vectors will be implemented to swap the pointers inside the vectors.

   std::vector<Foo> data, garbage;

   // compute next step

   std::swap(data,garbage);

Answer 3

The problem is that you're using a stack-allocated array.

When you say Foo bar[8];, you're creating space for eight Foo structs in the current stack frame. So the reason you can't assign it to something else is that it'd have to move outside the frame somehow, escaping the memory management and scoping it's supposed to have.

You want a dynamically-allocated array - Foo* bar = new Foo[8];. When you're done with it, delete[] bar;. The difference here is that now the pointer is on the stack, but the actual contents are on the heap - so you can change the location the pointer references without having to worry about moving the actual pointer itself.

Another option is to use a class with a copy-constructor and operator=, like std::vector, std::list, or std::deque.

Incidentally, the procedure of copying the array contents is linear time. A pointer assignment is constant time (O(1)) because it doesn't matter how large your array gets - it's always one operation to move the pointer.

Answer 4

You could use memcpy:

int main()
{
   Foo bar[8], baz[8], temp[8];

   memcpy(temp, baz, sizeof(Foo) * 8);
   memcpy(baz, bar, sizeof(Foo) * 8);
   memcpy(bar, temp, sizeof(Foo) * 8);
}

Answer 5

You can declare your arrays as temps, and also declare pointers - which you will use for the rest of the function.

Those ponters can be easily swapped.

int main()
{
   Foo temp1[8], temp2[8];
   Foo *bar = temp1, *baz = temp2;

   Foo *temp = baz;
   baz = bar;  //no problems now 
   bar = temp;  
}

Answer 6

   Foo bar[8], baz[8];

Then

   Foo* arr1 = bar, arr2 = bax;

Forget about baz & bar, work only with arr1 and arr2.

Swap:

  int* temp = arr1;
  arr1 = arr2;
  arr2 = temp;