C++ STL: воссоздание или повторное использование контейнера после очистки?
При программировании мы сталкиваемся с различными ситуациями, когда от нас требуется использовать промежуточные контейнеры STL, как показано в следующем примере:
while(true)
{
set < int > tempSet;
for (int i = 0; i < n; i ++)
{
if (m.size() == min && m.size() <= max)
{
tempSet.insert(i);
}
}
//Some condition testing code
}
Или же
set < int > tempSet;
while(true)
{
for (int i = 0; i < n; i ++)
{
if (m.size() == min && m.size() <= max)
{
tempSet.insert(i);
}
}
tempSet.clear();
//Some condition testing code
}
Какой подход лучше с точки зрения сложности времени и пространства, учитывая текущее состояние компиляторов C++?
Ответы 10
Второй вариант может быть немного лучше по времени, но разница будет крайне минимальной - код все равно должен пройти и освободить каждый из элементов в наборе, независимо от того, воссоздает он его или очищает.
(По пространству они будут идентичны.)
Как правило, загрузка данных в контейнер связана с расходами на выделение памяти. Гораздо лучше избежать многократной оплаты этой стоимости за счет повторного использования контейнера. Если вы действительно знаете, сколько элементов, или можете догадаться, вам следует заранее выделить место в контейнере.
Это особенно заметно, если вы вставляете объекты в контейнер, потому что вы можете в конечном итоге заплатить много дополнительных затрат на строительство / разрушение, поскольку контейнер понимает, что он слишком мал, перераспределяет память, а копирование создает новые объекты в новую память на основе на существующих объектах.
Всегда предварительно выделяйте и используйте повторно. Это экономит время и память.
Да я вижу, что. Вам, вероятно, придется сделать что-то глупое с распределителем, чтобы получить приличное предварительное выделение.
Я провел тест. max_size огромен. В данном случае это не проблема.
Если речь идет о set/map/list, то никакой разницы не будет. Если речь идет о vector/hash_set/hash_map/string, то второй будет либо быстрее, либо с такой же скоростью. Конечно, эта разница в скорости будет заметна только в том случае, если вы выполняете очень большое количество операций (10 000 int, помещенных в vector 10 000 раз, были примерно в два раза быстрее - 3 секунды и некоторые изменения против 7 секунд).
Если вы делаете что-то вроде сохранения struct/class в своей структуре данных вместо указателя на один, эта разница будет еще больше, потому что при каждом изменении размера вы должны копировать все элементы.
Опять же, почти в каждом случае это не имеет значения - и в тех случаях, когда это имеет значение, это проявится, если вы оптимизируете и заботитесь о каждой части производительности.
Этот вопрос касается множеств, а не векторов. Также для векторов я спорю о том, как заметить разницу в скорости: векторы должны расти экспоненциально (обычно в два раза каждый раз), поэтому количество распределений амортизируется.
Вопрос не касается ни того, ни другого. Если вы потратите время на то, чтобы действительно запустить некоторые тесты скорости для случая, когда это действительно важно, вы заметите большой скачок производительности. Болит не распределение, а memcpy после перераспределения.
@ ChrisJester-Young: Да, количество распределений амортизировано, но лучше log(n), чем Mlog(n).
Я говорю, что первый более защищен от ошибок. Вам не нужно будет помнить о его очистке (это просто выйдет за рамки и будет сделано). :-)
С точки зрения производительности особой разницы нет, но, тем не менее, вы должны измерить оба случая и убедиться в этом сами.
Следуйте за комментарием, защищающим от ошибок, к OP: представьте, что произойдет при добавлении оператора continue где-нибудь в цикле while.
Разница очень небольшая, хотя ваш второй позволяет избежать многократного вызова конструктора и деструктора. С другой стороны, ваш первый на одну строку короче и гарантирует, что контейнер не будет виден за пределами цикла.
Первая версия верна. Это проще почти во всех смыслах. Легче писать, легче читать, легче понимать, легче поддерживать и т. д.
Вторая версия май будет быстрее, но опять же, может и нет. Вам нужно будет показать, что у него есть значительное преимущество, прежде чем использовать его. В большинстве нетривиальных случаев я бы предположил, что между ними не будет ощутимой разницы в производительности.
Иногда во встроенном программировании полезно не класть вещи в стек; в таком случае вторая версия будет правильной.
По умолчанию использовать первую версию; используйте второй только в том случае, если вы можете указать для этого вескую причину (если причина - производительность, тогда у вас должны быть доказательства того, что выгода значительна).
Я согласен: не делайте переменные видимыми там, где они не нужны, кроме случаев, когда есть веская причина.
Между ними будет очень небольшая разница в производительности. Вы должны принимать решение, основываясь на удобочитаемости и надежности кода.
Я думаю, что первый пример более читабелен и безопаснее - что происходит через шесть месяцев, когда вы добавляете условие в цикл, возможно, с Продолжать где-то там - во втором примере он обойдет clear (), и у вас будет Жук.
Вы кладете свой набор в стек, поэтому стоимость размещения практически равна нулю!
Стоимость выделения для самого заданного объекта близка к нулю, но элементы в нем по-прежнему выделяются из кучи.
@Head Geek: построение / разрушение объектов в наборе одинаково в любом примере - единственная разница - это построение / разрушение самого объекта набора. Итак, точка ypnos верна.
@Mike B: Извини, но я не понимаю твоей точки зрения. Когда я его читал, ypnos говорит о стоимости выделения - времени, необходимом для выделения памяти для объекта, - поэтому я все еще возражаю против этого.
Я говорю о стоимости размещения установленного объекта. Вставка элементов и, следовательно, их (де) выделение памяти в обоих примерах одинаковы! Использование clear () эффективно делает то же самое, что и вызов деконструктора (бесплатные элементы) и конструктора (инициализация метапеременных) установленного объекта.
Я думаю, вы можете заранее выделить определенное количество элементов для контейнеров STL, таким образом имея постоянную стоимость выделения памяти, если вы знаете, сколько элементов будет в контейнере.
std :: set не имеет такой функциональности. Возможно, вы думаете о std :: vector :: reserve?
Набор обычно представляет собой красно-черное дерево. Каждый узел выделяется отдельно, поэтому повторное использование набора не дает. Вот почему оба подхода имеют почти одинаковую производительность. Вызов tempSet.clear () должен занять примерно то же время, что и уничтожение объекта. Первый подход лучше, потому что он имеет ту же производительность и соответствует более безопасному стилю программирования.
Вы можете найти общее обсуждение других контейнеров здесь: Повторное использование контейнера o создание нового
Не думаю, что в наборе можно заранее выделить место.