Подтвердить что ты не робот

Итерация через объекты с общим базовым классом в условной памяти

Я пытаюсь выяснить, как я могу выполнять итерацию через контейнер (например, std::vector) объектов, которые совместно используют основной родительский класс смежно.

Чтобы продемонстрировать проблему, используйте следующие примеры.

class Base
{
public:
    Base();
    virtual void doStuff() = 0;
};

class DerivedA : public Base
{
private:
    //specific A member variables
public:
    DerivedA();
    virtual void doStuff();
};

class DerivedB : public Base
{
private:
    //specific B member variables
public:
    DerivedB();
    virtual void doStuff();
};

Теперь, используя std::vector для итерации, будет сохраняться объект в смежной памяти, но мы будем испытывать нарезку, поскольку нет места для производных свойств.

Таким образом, мы должны использовать полиморфную технику, используя указатели, такие как

int main ()
{
    std::vector<Base*> container;
    container.push_back(new DerivedA());
    container.push_back(new DerivedB());

    for (std::vector<Base*>::iterator i = container.begin(); i!=container.end(); i++)
    {
        (*(*i)).doStuff();
    }
}

Насколько я знаю, это должно работать нормально, учитывая, что классы реализованы.

Проблема: Теперь вектор содержит указатели в смежной памяти, но это не означает, что адреса, на которые они указывают, являются.

Поэтому, если я хочу, чтобы в любое время удалять и вставлять объекты в вектор "на лету", объекты будут распространяться по всему месту в памяти.

Вопрос: Кажется, что каждый предлагает сделать это std::vector, но почему это не считается проблематичным, что он не повторяется в памяти (при условии, что мы действительно используем указатель)?

Я вынужден сделать это с копией-макароном?

int main ()
{

    std::vector<DerivedA> containerA;
    DerivedA a;
    containerA.push_back(a);

    std::vector<DerivedB> containerB;
    DerivedB b;
    containerB.push_back(b);

    for (std::vector<DerivedA>::iterator i = containerA.begin(); i!=container.end(); i++)
    {
        (*i).doStuff();
    }
    for (std::vector<DerivedB>::iterator i = containerB.begin(); i!=container.end(); i++)
    {
        (*i).doStuff();
    }
}

Я предполагаю, что не может быть реального решения этого, так как хранение объектов различных размеров в линейном порядке в памяти не имеет смысла, но если кто-нибудь может дать мне несколько советов, я был бы признателен.

4b9b3361

Ответ 1

Давай рассмотрим вопросы по порядку.

Q: Как я могу создать непрерывный гетерогенный контейнер?

A: Вы не можете.

Предположим, вы использовали некоторые размещение нового махинации, чтобы расположить ваши объекты в памяти так:

  [B ][DA  ][DB      ][B ][B ][DB      ][DA  ]

Как механизм итерации узнает, как далеко продвинется итерация указатель от одного объекта к другому? Количество байтов от первого элемент ко второму отличается от второго к третьему.

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

Это рассуждение приводит к идее использовать массив указателей, о которых Вы задали следующий вопрос:

В: Почему не считается проблематичным, что он не является непрерывным непрерывно

A: Это не так медленно, как вы думаете.

Кажется, ваша забота заключается в выполнении следующих указателей на разбросанные места памяти. Но стоимость следования этим указателям вряд ли будет доминирующим. Не зацикливайтесь на таких микрооптимизациях, как макет памяти, пока у вас нет веских доказательств того, что они необходимы.

Q: Я вынужден сделать это методом копировальной пасты?

A: Нет!

Здесь проблема, скорее всего, в ремонтопригодности, а не в производительности. Ремонтопригодность гораздо важнее, на мой взгляд, и это хорошо думать о раннем.

Для удобства обслуживания у вас уже есть прекрасное решение: поддерживать вектор Base*.

Если вы действительно хотите использовать несколько векторов, есть еще лучший способ чем копировать и вставлять: используйте функцию шаблона, как это (не проверено):

template <class T>
void doStuffToVector(std::vector<T> &vec)
{
  for (std::vector<T>::iterator i = vec.begin(); i!=vec.end(); ++i) {
    (*i).doStuff();
  }
}

Затем вызовите его для каждого контейнера:

  doStuffToVector(containerA);
  doStuffToVector(containerB);

Если ваша единственная забота - ремонтопригодность, то либо вектор указателей или функции шаблона должно быть достаточно.

Q: Любой совет?

A: Для начала, игнорировать производительность, по крайней мере, до постоянной факторы обеспокоены. Сконцентрируйтесь на правильности и ремонтопригодности.

Затем измерьте производительность. Заметьте, что этот вопрос не начался с указанием текущей и желаемой скорости. У вас еще нет актуальная проблема для решения!

Если после измерения вы сделаете слишком медленный вывод, используйте профилировщик чтобы узнать, где медленные пятна. Они почти никогда не там, где ты думаю, что они будут.

Показательный пример: весь этот вопрос и ответы были сосредоточены на итерации, но никто не поднял вопрос о том, что виртуальная функция звонки на doStuff, скорее всего, станут узким местом! виртуальный вызовы функций дороги, потому что они являются косвенным потоком управления, что вызывает серьезные проблемы для pipeопровод; косвенный доступ к данным намного дешевле, потому что кеш данных обычно очень эффективен для быстрого удовлетворения запросов на доступ к данным.

Q: (Подразумевается) Как бы я оптимизировал это?

A: После тщательного измерения, вы можете обнаружить, что этот код (сама итерация, включая отправку виртуальной функции; не то, что внутри doStuff) узкое место. Это должно означать, что это выполняется минимум на миллиарды итераций.

Сначала рассмотрим алгоритмические улучшения, которые уменьшат количество итераций требуется.

Затем исключите вызов виртуальной функции, например, встраивая явный индикатор типа объекта и его тестирование с помощью if или switch. Это позволит процессору предсказатель ветвления для быть намного более эффективным.

Наконец, да, вы, вероятно, захотите объединить все элементы в один непрерывный массив для улучшения локальности и устранения косвенных данных доступ. Это будет означать устранение иерархии классов, так что все объекты одного типа, либо объединение всех полей в один класс и/или с помощью union. Это повредит вашей программе ремонтопригодность! Это иногда одна из затрат написания высокого код производительности, но на самом деле это необходимо только очень редко.

Ответ 2

Очень простое решение - отсортировать массив указателей по значению адреса. Затем, если вы выполните итерацию вашего вектора, они будут в порядке памяти. Возможно, не смежно, но, тем не менее, в порядке, уменьшающем количество кешей.

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

Ответ 3

  Кажется, что все предлагают сделать это способом std::vector, но почему Разве это не считается проблематичным, что это не повторяется непрерывно в память (при условии, что мы на самом деле используем указатель)?

Я не знаю, кто считает это проблематичным или нет. Как и в других ответах, во многих случаях вам просто все равно. Выполните профилирование, и вы увидите, нужно ли оптимизировать его или нет.

В большинстве случаев люди рекомендуют вам использовать std::vector<std::unique_ptr<...>>.

Однако во многих случаях очень важно хранить ваши объекты в непрерывной памяти. Игры - один из таких случаев. Я пишу много вычислительного кода (библиотеки конечных элементов), где это тоже очень важно. Вы можете прочитать о том, как организовать ваши данные по-другому, чтобы все выстроилось в линию. Например, может быть интересно сохранить все объекты Arm в std::vector, а не сохранять каждый Arm в объекте Hero и обращаться к объектам Arm через объект Hero.

В любом случае, вот простой способ хранить ваши объекты из вашего примера в непрерывном контейнере.

Для base class используйте alignas, чтобы зафиксировать размер объекта. Убедитесь, что он достаточно большой, чтобы в него помещались все производные объекты. В моем примере ниже, DerivedA имеет размер 16, DerivedB имеет размер 24. Указанный размер выравнивания должен быть степенью 2, поэтому мы выбираем 32.

struct alignas(32) Base
{
    virtual void print() const {}
};

struct DerivedA : Base
{
    void print() const final override { std::cout << "num: " << i << std::endl; }
    int i = 1;
};

struct DerivedB : Base
{
    void print() const final override { std::cout << "num: " << i << std::endl; }
    int i = 2;
    double j = 100.0;
};

Теперь мы можем написать экземпляры DerivedA и DerivedB с помощью placement new:

int main ()
{
    std::vector<Base> v(2);
    new (&v[0]) DerivedA();
    new (&v[1]) DerivedB();

    for (const auto& e : v)
        e.print();

    return 0;
}

EDIT

Проблема здесь в том, что вам нужно управлять размерами вручную. Также, как мне недавно указывалось, alignas предназначен для позиционирования объекта в памяти, а не для выделения размера. Возможно, лучшим способом было бы просто использовать std::variant.

int main()
{
    std::vector<std::variant<DerivedA, DerivedB>> vec;
    vec.emplace_back(DerivedA());
    vec.emplace_back(DerivedB());
    for (const auto& e : vec)
        std::visit(VisitPackage(), e);
    return 0;
}

где VisitPackage может выглядеть примерно так:

struct VisitPackage
{
    void operator()(const DerivedA& d) { d.print(); }
    void operator()(const DerivedB& d) { d.print(); }
};

Ниже приведен полный и короткий пример того, как получить то, что вы хотите, используя std::variant.

#include <iostream>
#include <vector>
#include <variant>

struct Base { virtual void print() const = 0; };
struct DerivedA : Base { void print() const final override { std::cout << "DerivedA\n"; } };
struct DerivedB : Base { void print() const final override { std::cout << "DerivedB\n"; } };

struct Print
{
    template <typename T>
    // note that the operator() calls print from DerivedA or DerivedB directly
    void operator()(const T& obj) const { obj.print(); }
};

int main ()
{    
    using var_t = std::variant<DerivedA, DerivedB>;
    std::vector<var_t> vec { DerivedA(), DerivedB() };
    for (auto& e : vec)
        std::visit(Print(), e);

    return 0;
}

Ответ 4

Если нам нужно хранить объекты в массиве, их тип должен быть фиксированным. Тогда у нас есть эти варианты:

  • динамически размещать и хранить указатели - если указанным объектам требуется быть непрерывными в памяти, используйте специальный распределитель
  • использовать полиморфный тип фиксированного размера, например, union, в качестве типа хранения

Для второго варианта код может выглядеть примерно так:

#include <new>

struct A {
    A() {}
    virtual void f() {}
};
struct B : A {
    B() {}
    void f() override {}
};

union U {
    A a;
    B b;
    U() {}
};

int main() {
    U u[2];
        new (&u[0]) A;
        new (&u[1]) B;
    ((A*)&u[0])->f(); // A::f
    ((A*)&u[1])->f(); // B::f
}

Ответ 5

std::vector<T> итераторы предполагают, что объекты в смежной памяти имеют тип T, std::vector<T>::iterator::operator++ считает, что sizeof T является инвариантным, то есть он не обращается к конкретному экземпляру для данных размера.

По существу, вы можете думать о vector и vector::iterator как о тонком фасаде над указателем T* m_data, так что iterator++ на самом деле является просто основной операцией указателя.

Вам, скорее всего, понадобится использовать собственный распределитель и на месте new для подготовки ваших данных, сопровождаемый индексацией, связыванием и т.д. Возможно, подумайте над http://www.boost.org/doc/libs/1_58_0/doc/html/intrusive/slist.html

См. также boost:: stable_vector

Ответ 6

std::vector выделяет объекты в непрерывной памяти, но указатели объектов, которые вы храните в векторе, не являются. Так вы повторяете vector. Следующий код написан в С++ 14. Описанная проблема не разрешима этим решением, поскольку указатели объектов хранятся в непрерывной памяти, но не в реальных объектах.

#include <iostream>
#include <memory>
#include <vector>
#include <algorithm>
using namespace std;

class Base
{
public:
    Base() {}
    virtual void doStuff() = 0;
};

class DerivedA : public Base
{
private:
    //specific A member variables
public:
    DerivedA() : Base() {}
    virtual void doStuff() {
        std::cout << "Derived Class A - Do Stuff" << std::endl;
    }
};

class DerivedB : public Base
{
private:
    //specific B member variables
public:
    DerivedB() : Base() {}
    virtual void doStuff() {
        std::cout << "Derived Class B - Do Stuff" << std::endl;
    }
};
int main() {
    // your code goes here
    std::vector<std::unique_ptr<Base> > container;
    container.push_back(std::make_unique<DerivedA>());
    container.push_back(std::make_unique<DerivedB>());

    std::for_each(container.begin(), container.end(),[](std::unique_ptr<Base> & b) {
        b->doStuff();
    });
    return 0;
}

Live Demo здесь.