выполнение декларирования объектов

Jan 03 2021

Я писал код для своего рода университетского завоевания и кое-что заметил, когда объявлял карту в цикле, как показано ниже:

for (int i = 0; i < n; i++)
{
    map<int, bool> hashMap;
    //...
}

требуется больше времени, чем:

map<int, bool> hashMap;
for (int i = 0; i < n; i++)
{
    hashMap.clear();
    //...
}

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

Ответы

2 dxiv Jan 04 2021 at 10:59

В первой версии кода конструктор и деструктор hashMapвызываются ntimes, а во второй версии они вызываются только один раз.

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

std::mapобычно реализуется с использованием красно-черных деревьев , и для реализаций красно-черного дерева обычно используется контрольный узел для NIL-листьев, см., например, Преимущество контрольного узла в красно-черном дереве? . Этот часовой должен быть назначен каждый раз при построении дерева, а затем освобожден при уничтожении. Напротив, команда clear'a' mapочищает дерево, но повторно использует связанные внутренние объекты.

В качестве реального примера такой реализации _Treeконструктор Microsoft вызывает метко названный _Alloc_sentinel_and_proxy();. Так как они являются mapпроизводными от _Tree, this mapвызывается каждый раз при создании объекта.