Std:: map insert() местоположение подсказки: разница между С++ 98 и С++ 11

Вкл запись cplusplus 'на карте:: insert() Я прочитал о местоположении, которое можно было бы добавить как подсказку для функции, которая "функция оптимизирует свое время вставки" если position указывает на элемент, который будет предшествует вставленному элементу "для С++ 98, тогда как для С++ 11 происходит оптимизация, если position указывает на элемент, который будет выполните вставленный элемент (или до конца, если он будет последним)".

Означает ли это, что производительность фрагментов кода из следующей формы (которые изобилуют устаревшим кодом, над которым я работаю и смоделировали после Scott Meyer "Эффективный STL", пункт 24) были затронуты при переключении на компилятор, совместимый с С++ 11

auto pLoc = someMap.lower_bound(someKey);
if(pLoc != someMap.end() && !(someMap.key_comp()(someKey, pLoc->first)))
    return pLoc->second;
else
    auto newValue = expensiveCalculation();
    someMap.insert(pLoc, make_pair(someKey, newValue));  // using the lower bound as hint
    return newValue;

Каким будет лучший способ улучшить этот шаблон для использования с С++ 11?

Ответ 1

Спецификация С++ 98 является дефектом стандарта. См. Обсуждение LWG-выпуск 233 и N1780.

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

Итак, другими словами, ваш текущий код уже работает корректно в соответствии с спецификацией С++ 11, и на самом деле это было бы неправильно в случае дефектной спецификации С++ 98.

Ответ 2

Да, это повлияет на сложность. Предоставление правильного намека сделает insert() амортизированной постоянной сложностью, в то время как предоставление и неправильный намек заставят карту искать позицию с самого начала, что дает логарифмическую сложность. В принципе, хороший намек делает вставку в постоянное время, независимо от того, насколько велика ваша карта; с плохой подсказкой, добавление будет медленнее на больших картах.

Решение, по-видимому, для поиска подсказки с upper_bound вместо lower_bound.

Ответ 3

Я думаю, что правильная вставка подсказки в стиле С++ 11 может быть следующей:

iterator it = table.upper_bound(key);   //upper_bound returns an iterator pointing to the first element that is greater than key
if (it == table.begin() || (--it)->first < key) {
    // key not found path
    table.insert(it, make_pair(key, value));
}
else {
    // key found path
    it->second = value;
}