Во-первых, с точки зрения производительности, это не будет иметь никакого значения, если вы используете range.first или range.second.Давайте посмотрим на возвращаемое значение equal_range:
std::equal_range - возвращаемое значение
std::pair, содержащеепара итераторов, определяющих требуемый диапазон, первый указывает на первый элемент, который не меньше значения, а второй указывает на первый элемент, который больше значения.Если нет элементов, не меньших значения, последний возвращается как первый элемент.Точно так же, если нет элементов больше значения, последний возвращается как второй элемент
Это означает, что при получении значения key оба значения range.first и range.secod равны represent positions where ключ may be correctly inserted right before. So performance wise it should not matter if you use range.first or range.last`.Сложность должна быть «амортизируемой константой», поскольку новый элемент вставляется непосредственно перед подсказкой.
Во-вторых, когда диапазон «пустой», range.first и range.second оба равны один за другим.и, следовательно, производительность и результат идентичны, фактически так же, как если бы вы использовали emplace без каких-либо подсказок.
См. следующую программу, демонстрирующую это:
int main()
{
std::multimap<std::string, std::string> m;
// some clutter:
m.emplace(std::make_pair(std::string("k"), std::string("1")));
m.emplace(std::make_pair(std::string("k"), std::string("2")));
m.emplace(std::make_pair(std::string("z"), std::string("1")));
m.emplace(std::make_pair(std::string("z"), std::string("2")));
// relevant portion of demo data: order a-c-b may be preserved
m.emplace(std::make_pair(std::string("x"), std::string("a")));
m.emplace(std::make_pair(std::string("x"), std::string("c")));
m.emplace(std::make_pair(std::string("x"), std::string("b")));
auto r = m.equal_range("x");
// will insert "x.zzzz" before "x.a":
m.emplace_hint(r.first, std::make_pair(std::string("x"), std::string("zzzz")));
// will insert "x.0" right after "x.b":
m.emplace_hint(r.second, std::make_pair(std::string("x"), std::string("0")));
auto rEmpty = m.equal_range("e");
// "empty" range, normal lookup:
m.emplace_hint(rEmpty.first, std::make_pair(std::string("e"), std::string("b")));
m.emplace_hint(rEmpty.second, std::make_pair(std::string("e"), std::string("a")));
auto rWrong = m.equal_range("k");
m.emplace_hint(rWrong.first, std::make_pair(std::string("z"), std::string("a")));
for (const auto &p : m) {
std::cout << p.first << " => " << p.second << '\n';
}
}
Вывод:
e => b
e => a
k => 1
k => 2
x => zzzz
x => a
x => c
x => b
x => 0
z => a
z => 1
z => 2
Короче говоря: если у вас есть действительное range для key предварительно рассчитанного, используйте его при вставке key.В любом случае это поможет.
РЕДАКТИРОВАТЬ:
Были дискуссии вокруг того, может ли "недействительный" подсказка привести к вставке в позицию, которая затем не отражает "порядок вставки" длязначения с тем же ключом.Это может быть заключено из общего многопользовательского оператора «Порядок пар ключ-значение, ключи которого сравниваются, эквивалентен порядку вставки и не изменяется. (Начиная с C ++ 11)».
Я не сделалнайти поддержку той или иной точке зрения в любом нормативном документе.Я только что нашел следующее утверждение в документации по cplusplus multimap / emplace_hint:
emplate <class... Args>
iterator emplace_hint (const_iterator position, Args&&... args);
position Подсказка для позиции, в которую можно вставить элемент.Функция оптимизирует время вставки, если позиция указывает на элемент, который будет следовать за вставленным элементом (или до конца, если он будет последним).Обратите внимание, что это не заставляет новый элемент находиться в этой позиции в контейнере мультикарты (элементы в мультикарте всегда следуют определенному порядку).const_iterator - это тип члена, определенный как двунаправленный тип итератора, который указывает на элементы.
Я знаю, что это не нормативная ссылка, но по крайней мере мой компилятор Apple LLVM 8.0 придерживается этого определения (см.демонстрация выше): если кто-то вставляет элемент с «неправильной» подсказкой, то есть с указателем даже до позиции, в которую должна быть вставлена пара, алгоритм распознает это и выбирает правильную позицию (см. вставку «z» => «a»)где подсказка указывает на элемент "x").Если мы используем диапазон для клавиши «x» и используем range.first, то позиция перед первым x интерпретируется как действительная позиция.
Итак: я думаю, что m.emplace_hint(r.first,... ведет себя так, что алгоритм немедленно выбирает допустимую позицию, и что to a position close to hint отменяет общее утверждение «Порядок пар ключ-значение, ключи которых сравниваются, равенпорядок вставки и не меняется. (начиная с C ++ 11) ".