Вставка в unordered_map/set

Нет, конечно, не гарантировано. Напишите "плохую" функцию хеширования (например, всегда возвращающую одно и то же значение) - и запросто получите линейное время вставки, ибо все вставляемые элементы пойдут в одну корзину.

Идеальное линейное время вставки вы получите только в том случае, если внешняя функция хеширования (вкупе с преобразованиями хэш-значения внутри unordered_map) каким то чудом образовали идеальную функцию хэширования. Но на это рассчитывать в общем случае не приходится.