Эффективная структура данных для вставки

Я ищу структуру данных (подобную массиву), которая позволяет быстро (быстрее, чем O(N)) произвольно вставлять значения в структура. Структура данных должна иметь возможность распечатать свои элементы в том виде, в котором они были вставлены. Это похоже на что-то вроде List.Insert() (который слишком медленный, так как должен смещать каждый элемент), за исключением того, что мне не нужен произвольный доступ или удаление. Вставка всегда будет в пределах размера «массива». Все значения уникальны. Никаких других операций не требуется.

Например, если Insert(x, i) вставляет значение x в индекс i (0-индексирование). Затем:

• Insert(1, 0) дает {1}
• Insert(3, 1) дает {1,3}
• Insert(2, 1) дает {1,2,3}
• Insert(5, 0) дает {5,1,2,3}

И он должен иметь возможность распечатать {5,1,2,3} в конце.

Я использую C++.