C ++ STL: восстановление или повторное использование контейнера после очистки?

Question

При программировании мы сталкиваемся с различными ситуациями, когда нам необходимо использовать промежуточные контейнеры 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 ++?

Answer 1

Первая версия верна. Это проще почти во всех отношениях. Легче писать, легче читать, легче понимать, легче поддерживать и т. Д ....

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

Иногда во встроенном программировании полезно избегать размещения вещей в стеке; в этом случае вторая версия будет правильной.

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

Answer 2

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

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

Answer 3

Если это вопрос set/map/list, это не будет иметь никакого значения. Если речь идет о vector/hash_set/hash_map/string, вторая будет либо быстрее, либо с той же скоростью. Конечно, эта разница в скорости будет заметна только в том случае, если вы выполняете очень большое количество операций (10 000 дюймов, введенных в vector 10000 раз, были примерно в два раза быстрее - 3 секунды и некоторые изменения по сравнению с 7 секундами.).

Если вы делаете что-то вроде сохранения struct/class в вашей структуре данных вместо указателя на единицу, эта разница будет еще больше, потому что при каждом изменении размера вы должны копировать все элементы.

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

Answer 4

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

(В пространстве они будут идентичны.)

Answer 5

Вы кладете свой набор в стек, поэтому стоимость выделения практически равна нулю!

Answer 6

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

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

Answer 7

Набор обычно реализован в виде красного чёрного дерева. Каждый узел выделяется отдельно, поэтому набор не получает выгоды от повторного использования. Вот почему оба подхода имеют практически одинаковую производительность. Вызов «tempSet.clear ()» должен занять примерно то же время, что и уничтожение объекта. Первый подход лучше, потому что он имеет ту же производительность и придерживается более безопасного стиля программирования.

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

Answer 8

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

Answer 9

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

Answer 10

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

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

Всегда предварительно распределяйте и используйте повторно. Это экономит время и память.