Стандарт указывает (23.4.4.2:5 и т. д.), что построение всех четырех упорядоченных ассоциативных контейнеров ( map , multimap , set , multiset ) из диапазона [first, last) должно быть линейным в N = last - first , если диапазон уже отсортирован....