More efficient object swapping with lots of data containers inside the objects

Question

Type of general-case object swap that I'd like to be able to do:

• Method in the object class for swapping, or a wrapper class/function that can be called to do the swapping

• I don't want to force the user of the swap to use pointers / declare the object on the heap

• If we imagine the object's total nested containers are many, I want to avoid having to swap all of them

Is there a way to gain access to the pointer that the program is using for two of the same-type objects that exist on the stack and just swap those two pointers?

Example attempt:

#include <iostream>


class Foo
{
    // lots of data that isn't encapsulated in a small number of containers
    // (eg. some nested data that totals n int's and [separately] m vectors of int's)
    // where n and m are large enough not to want our program to manage all of them in a swap

public:

    void Swap (Foo & other)
    {
        foo * our_ptr = this;
        foo * other_ptr = &other;

        foo ** our_ptr_location = &this;
        foo ** other_ptr_location = &&other;

        *our_ptr_location = other_ptr;
        *other_ptr_location = our_ptr;
    }
};

void FooSwap (Foo & a, Foo & b)
{
    Foo * a_ptr = &a;
    Foo * b_ptr = &b;

    Foo ** a_location_ptr = &&a;
    Foo ** b_location_ptr = &&b;

    *a_location_ptr = b_ptr;
    *b_location_ptr = a_ptr;
};

int main ()
{
    Foo a, b;

    // edit data for a and b;

    // using a method
    a.Swap(b);

    // using a global function / wrapper
    FooSwap(a,b);   

    return 0;
}

The problem here is that this and &foo_object return rvalues, so &this and &&foo_object aren't meaningful.

If we consider the well-known swap solution:

void Foo::Swap (Foo & other)
{
    simple_data_1_ = other.simple_data_1_;
    // ...
    simple_data_n_ = other.simple_data_n_;

    container_of_data_1_.Swap(other.container_of_data_1_);
    // ...
    container_of_data_m_.Swap(other.container_of_data_m_);
}

This is linear O(N) with respect to the total number of nested containers (N).

I understand that constant-time swap is conceptually possible if we could access the pointers directly to the two objects. Is there a way to do this with c++ which still maintains good OOP style?

Answer 1

What you're asking for can't be done. If we have a requirement that data structures be allocated on the stack, then swapping will always be roughly linear in the size of the structure.

If I declare Foo x, where Foo is class or struct with many members, then some space on the stack must be allocated to store its contents. Now, x and any reference (of any kind) to x must ultimately point to that allocated stack space. Hence, to 'swap' x with another Foo (say y), we need to transform the contents of that space so it looks like y (and also transform the space allocated for y to look like x). The only way to do that is to copy all of the data from y into x's space, an operation which inevitably gets more expensive as the size of Foo increases. C++ does not allow you to "re-point" variables and references - that's precisely what pointers are for!

So, how can we work round this?

You mentioned that you don't want users of your class to have to do heap allocation or "use pointers". I wonder, is this specifically because you want memory allocated on the stack, or is it just that you want uses of Foo to be able to declare Foo x inside functions (i.e. not having to be concerned with any more complex allocation)? If it's the latter, then you could just turn Foo into a wrapper around a heap-allocated internal structure:

// Forward declaration. FooData will contain all of the many substructures and members
class FooData;

class Foo
{
    FooData* data;

public:

    Foo() : data(new FooData) {}

    ~Foo()
    {
        delete data;
    }

    void do_stuff()
    {
        std::cout << data->element_k;
        // or whatever...
    }

    void swap(Foo &other)
    {
        // Now, no matter how big FooData is, we only ever need to swap one pointer
        std::swap(data, other.data);
    }
}

So, this makes swapping (and move semantics generally) a constant-time operation, and we can still just declare Foo x in our code. The obvious drawback here is that every other operation on Foo will involve (hidden internal) pointer indirection, so is more expensive. In all likelihood, operations other than swapping will be called much more commonly than swapping itself, so this is quite possibly a trade-off you don't want to take.

The real question is: why is it so important to you that swapping is constant-time and transparent? I would argue that by far the most elegant solution is simply to document your Foo class, noting that it is large, and recommending that in situations where it will be swapped a lot, then it should be heap-allocated, and swap pointers instead. You can make this more explicit by not having a swap method or friend function on Foo itself. I understand that this violates your preference not to require users to explicitly allocate on the heap, but it is ultimately the most flexible solution: each usage of the class can decide for itself what the best allocation pattern is, given its requirements.

Answer 2

If I understand the question correctly you want to do something like:

Foo foo1{};
Foo foo2{};
swap(foo1, foo2);//just swap 'pointers'

That is not supported by the language directly (in fact its not possible really) - you will have to add an extra level of indirection in one way or the other if you want that kind of swap. When you put something on the stack - it's actually laid out there directly, ie. there is no extra variable pointing to the stack object (unless you make one) - to demonstrate that consider:

struct Foo {
   int a;
   int b;
};

void test1 {
  Foo foo{};
}

stack-wise is conceptually equivalent to:

void test1 {
  int a{};
  int b{};
}

It is pretty easy to see that there's no way to just 'swap pointers'.

(and the this pointer of the Foo object is just pointing to base address of the object - in this very simple case it should be the same address as the int a; address)

Answer 3

Add move constructor and move assignment to your class - if for some reason compiler is unable to automatically generate them - and std::swap will automatically use them.

class Foo
{
public:
    Foo() = default;
    Foo(const Foo&) = default; // copy ctor
    Foo(Foo&&) = default; // move ctor

    Foo& operator=(const Foo&) = default; // copy assignment
    Foo& operator=(Foo&&) = default; // move assignment
};