std :: список объектов эффективности

Question

Скажем, у вас есть std :: list некоторого класса.Есть два способа сделать этот список: 1)

std::list<MyClass> myClassList;
MyClass myClass;
myClassList.push_front(myClass);

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

2)

std::list<MyClass*> myClassList;
MyClass* myClass = new MyClass();
myClassList.push_front(myClass);

Этот метод не вызовет конструктор копирования для класса.Я не совсем уверен, что происходит в этом случае, но я думаю, что список создаст новый MyClass * и назначит адрес параметра.На самом деле, если вы делаете myClass в стеке, а не в куче, и позволяете ему выйти из области видимости, тогда myClassList.front () недопустим, поэтому это должно быть так., но я считаю, что 2-й метод гораздо эффективнее для определенных классов.

Answer 1

Это всегда вопрос.

Прежде всего, это действительно зависит от того, поддерживает ли ваш компилятор семантику перемещения C ++ 11 или нет, поскольку это кардинально меняет аспекты проблемы.

Для тех, кто застрял в C ++ 03

Есть несколько вариантов:

std::list<MyClass> list;
list.push_front(MyClass());

Даже если семантически имеется копия, оптимизатор может удалить большую частьизбыточные / мертвые магазины.Большинство оптимизаторов требуют, чтобы было доступно определение конструктора по умолчанию и конструктора копирования.

boost::ptr_deque<MyClass> deque;
std::auto_ptr<MyClass> p(new MyClass());
deque.push_front(p);

ptr_vector можно использовать, если вы замените push_front на push_back, иначе это будет немного расточительно.Это позволяет избежать большинства накладных расходов памяти std::list<MyClass*> и имеет дополнительный бонус автоматической обработки памяти.

boost::stable_vector<MyClass> svec;
svec.push_back(MyClass());
//        ~~~~

Существует одна копия (как со списком), но гарантия того, что дальнейшая копия не должна быть сделанавнутри контейнера (как со списком).Он также позволяет выполнять несколько больше операций, чем list (например, произвольный доступ), за счет того, что он медленнее для вставки в середине для больших контейнеров.

Для тех, кто пользуется C ++ 11

std::list<MyClass> list;
list.push_front(MyClass());

не создает никакой копии, вместо этого происходит операция перемещения.

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

std::list<MyClass> list;
list.emplace_front();

создаст новый MyClass непосредственно внутри узла, без копирования, без перемещения.

И, наконец, вы можете пожелать более компактное представление или другие операции над контейнером, в этом случае:

std::vector<std::unique_ptr<MyClass>> vec;
vec.emplace_back(new MyClass());

Предлагает вам произвольный доступ и меньшую нагрузку на память.

Answer 2

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

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

Во втором случае контейнер не становится владельцем элемента, который вы добавляете, вы сами управляете им.И если вам необходимо, вы должны использовать Умный указатель в качестве элемента контейнера, а не необработанный указатель.

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

Answer 3

Если вы действительно беспокоитесь о производительности, но все еще должны использовать связанные списки, рассмотрите возможность использования boost :: intrusive :: list .Основная проблема с использованием std::list заключается в том, что вам нужно выделить новую память из кучи, и это, вероятно, дороже, чем даже создание копии в большинстве случаев.Так как boost::intrusive::list оставляет вам выделение, вы можете хранить ваши объекты в std::vector и распределять их в пакетном режиме.Таким образом, вы также получите лучшую локальность кэша, что является еще одной проблемой производительности.В качестве альтернативы вы можете использовать собственный распределитель с std :: list, чтобы сделать то же самое.Поскольку использование пользовательского распределителя для std::list, вероятно, не так сложно, как использование навязчивого списка boost, я бы пошел с boost, потому что вы получаете много других полезных функций (например, хранение одного и того же объекта в нескольких списках и т. Д.).).

Кстати, не беспокойтесь о структуре копирования, компилятор, вероятно, оптимизирует любое ненужное копирование (ненужное, учитывая способ его использования).

Answer 4

Проблема с первым подходом - низкая производительность, когда MyClass велика, и невозможность иметь один и тот же объект в двух структурах данных (в двух списках, каждый с разной семантикой; в списке и дереве; и т. Д.) , Если эти недостатки вас не беспокоят, используйте первый подход.

Второй подход более эффективен, но им сложнее управлять. Например, вам нужно правильно уничтожить MyClass объекты, если они больше не будут доступны. Это может быть нетривиально при наличии исключений (читайте о C ++ безопасность исключений ). Я бы порекомендовал вам взглянуть на Boost Smart Pointers , который призван упростить управление указателями в C ++. C ++ 11 имеет эти встроенные функции, поэтому вам не нужен Boost, если вы используете современный компилятор. Прочитайте Википедию для краткого введения.