Более эффективный обмен объектами с большим количеством контейнеров данных внутри объектов

Question

Тип общего объекта подкачки, который я хотел бы сделать:

• Метод в классе объектов для замены или класс / функция-обертка, которые могут бытьвызван для обмена

• Я не хочу заставлять пользователя свопа использовать указатели / объявлять объект в куче

• Если мы представим, что всего вложенных контейнеров объекта много, я хочу избежать необходимости менять их все

Есть ли способ получить доступ к указателю, который программа использует длядва объекта одного типа, которые существуют в стеке и просто меняют эти два указателя?

Пример попытки:

#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;
}

Проблема здесь в том, что this и &foo_object возвращаютЗначения r, поэтому &this и &&foo_object не имеют смысла.

Если мы рассмотрим известное решение подкачки:

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_);
}

Это линейный O (N) по отношению кобщее количество вложенных контейнеров (N).

Я понимаю, что подкачка с постоянным временем концептуальновозможно, если бы мы могли получить доступ к указателям непосредственно на два объекта. Есть ли способ сделать это с C ++, который все еще поддерживает хороший стиль ООП?

Answer 1

То, что вы просите, не может быть сделано. Если у нас есть требование, чтобы структуры данных были размещены в стеке, то замена будет всегда приблизительно линейной по размеру структуры.

Если я объявлю Foo x, где Foo является классом или структурой со многими членами, тогда некоторое пространство в стеке должно быть выделено для хранения его содержимого. Теперь x и любая ссылка (любого рода) на x должны в конечном итоге указывать на это выделенное пространство стека. Следовательно, чтобы «поменять» x с другим Foo (скажем, y), нам нужно преобразовать содержимое этого пространства так, чтобы оно выглядело как y (а также преобразовать пространство, выделенное для y, чтобы выглядетькак x). Единственный способ сделать это - скопировать все данные из y в пространство x, операция, которая неизбежно становится более дорогой с увеличением размера Foo. C ++ не позволяет вам «повторно указывать» переменные и ссылки - это именно то, для чего нужны указатели!

Итак, как мы можем обойти это?

Вы упомянули, что вы этого не делаетехотите, чтобы пользователи вашего класса занимались распределением кучи или «использовали указатели». Интересно, это именно потому, что вы хотите, чтобы память выделялась в стеке, или вы просто хотите, чтобы использование Foo позволяло объявлять Foo x внутри функций (т.е. не нужно заниматься каким-либо более сложным распределением)? ? Если это последнее, то вы можете просто превратить Foo в обертку вокруг выделенной кучи внутренней структуры:

// 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);
    }
}

Итак, это делает перестановку (и вообще семантику перемещения) операцией постоянного времени,и мы все еще можем просто объявить Foo x в нашем коде. Очевидным недостатком здесь является то, что каждая другая операция на Foo будет включать (скрытое внутреннее) перенаправление указателя, поэтому является более дорогой. По всей вероятности, операции, отличные от подкачки, будут вызываться гораздо чаще, чем подкачка, так что вполне возможно, что это компромисс, который вы не хотите брать.

Реальный вопрос: почему это так? Вам важно, чтобы обмен был постоянным и прозрачным? Я бы сказал, что самым элегантным решением на сегодняшний день является простое документирование вашего класса Foo, отметив, что он большой, и порекомендовав, чтобы в ситуациях, когда его много поменяли местами, он выделил кучу, и указатели поменялись местами. вместо. Вы можете сделать это более явным, если у нет метода обмена или дружественной функции на самом Foo. Я понимаю, что это нарушает ваше предпочтение не требовать от пользователей явного распределения в куче, но в конечном итоге это наиболее гибкое решение: каждое использование класса может решить для себя, какой шаблон распределения лучше всего, учитывая его требования.

Answer 2

Если я правильно понимаю вопрос, вы хотите сделать что-то вроде:

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

Это не поддерживается языком напрямую (на самом деле это невозможно на самом деле) - вы будетенеобходимо добавить дополнительный уровень косвенности тем или иным образом , если вы хотите такой обмен. Когда вы кладете что-то в стек - это на самом деле прямо там, т.е. нет дополнительной переменной, указывающей на объект стека (если только вы ее не создадите) - чтобы продемонстрировать, что рассмотрим:

struct Foo {
   int a;
   int b;
};

void test1 {
  Foo foo{};
}

по стеку концептуально эквивалентно:

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

Довольно легко увидеть, что нет способа просто «поменять местами указатели».

(а указатель this объекта Foo просто указывает на базовый адрес объекта - в этом очень простом случае это должен быть тот же адрес, что и адрес int a;)

Answer 3

Добавьте конструктор перемещения и присвойте перемещение вашему классу - если по какой-то причине компилятор не может автоматически сгенерировать их - и std::swap будет автоматически использовать их.

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
};