Стандарт указывает (23.4.4.2:5 и т. д.), что построение всех четырех упорядоченных ассоциативных контейнеров (map, multimap, set, multiset) из диапазона [first, last) должно быть линейным в N = last - first, если диапазон уже отсортирован.
Однако для слияния диапазона (например, контейнера того же типа) с существующим контейнером в таблице 102 23.2.4:8 указывается только то, что insertвключение диапазона [i, j) в контейнер должно иметь сложность N log(a.size() + N), где N = distance(i, j). Казалось бы, это указывает на то, что использование вставки с подсказкой:
for (auto it = a.begin(); i != j; ++i)
it = next(a.insert(it, *i));
может быть более эффективным, чем a.insert(i, j), имея сложность строго меньше, чем N log(a.size() + N), в зависимости от доли правильных подсказок (за исключением тривиального случая, когда N == 0); и быть линейным, поскольку каждая подсказка верна, если a изначально пусто.
Является ли это недостатком стандарта или есть какой-то другой язык (или средство), охватывающий этот случай? На практике оптимизируются ли реализации для слияния упорядоченного ассоциативного контейнера с другим?
Благодарим https://stackoverflow.com/a/11362162/567292 за то, что вдохновили на этот вопрос.
