Я пытаюсь понять пример кода в документации emplace_hint():
https://en.cppreference.com/w/cpp/conta ... place_hint
Особенно следующая функция:
Код: Выделить всё
std::size_t map_emplace_hint_closest()
{
std::map map;
auto it = map.begin();
for (int i = 0; i < n_operations; ++i)
it = map.emplace_hint(it, i, 'e');
return map.size();
}
Насколько я понимаю, здесь итератор, предлагаемый emplace_hint(), не совсем "тот, перед которым должен быть вставлен новый элемент", а является итератором для " ранее вставленный элемент, ПОСЛЕ которого будет сделана новая вставка». Но похоже, что итератор все еще «достаточно близок» к правильному, поэтому эта функция работает быстро. Я попробовал запустить код на вышеупомянутом веб-сайте, и при вставленном чуть более 1 миллиона членов (почему в примере такое странное число 1005000?) время выполнения составило около 83 мс, что было даже лучше, чем в функции map_emplace_hint(), где итератор просто устанавливается на map.end() после каждой вставки.
Просто из любопытства я подумал, каким будет время выполнения, если я использую возвращенное значение итератора в map_emplace_hint_closest( ), но увеличит его так, чтобы оно точно соответствовало месту вставки следующего элемента:
Код: Выделить всё
for (int i = 0; i < n_operations; ++i)
{
it = map.emplace_hint(it, i, 'e');
++it;
}
И, что было большим сюрпризом, время выполнения оказалось более 300 мс — аналогично использованию emplace() без каких-либо намеков. В моем понимании операция увеличения итератора не должна быть дорогостоящей (по крайней мере, не сравнимой со вставкой в большую карту вообще без какой-либо подсказки), так в чем же здесь проблема? Моя подсказка в последнем цикле неверна?
Я также попробовал, что произойдет, если я просто увеличу итератор, не используя возвращаемое значение emplace_hint():
Код: Выделить всё
for (int i = 0; i < n_operations; ++i)
{
map.emplace_hint(it, i, 'e');
++it;
}
И это снова сделало функцию быстрой — 86 мс. Таким образом, проблема с длительным временем выполнения, по-видимому, связана с использованием возвращаемого итератора и последующим его увеличением.
Все мои тесты проводились на веб-сайте cppreference с параметрами по умолчанию (GCC13.1 (C) ++23)).
Обратите внимание, что я задаю этот вопрос, чтобы узнать, что не так в моей логике, а НЕ для того, чтобы я хотел запустить именно этот код в своем проекте. Я хотел бы знать общую причину: ПОЧЕМУ исправление итератора, который я должен указывать на точную позицию следующего места, стоит так дорого?
Заранее спасибо.
Подробнее здесь:
https://stackoverflow.com/questions/790 ... e-iterator