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

Используйте список пропуска. Другой вариант - многоуровневый вектор. Список пропусков выполняет вставку с константой O (log (n)) и сохраняет порядок чисел. Многоуровневый вектор поддерживает вставку в O (sqrt (n)) и снова может печатать элементы по порядку.

РЕДАКТИРОВАТЬ: в комментарии amit я объясню, как найти k-й элемент в списке пропуска:

Для каждого элемента у вас есть башня со ссылками на следующие элементы, и для каждой ссылки вы знаете, через сколько элементов она перепрыгивает. Итак, ища k-й элемент, вы начинаете с заголовка списка и спускаетесь по башне, пока не найдете ссылку, которая перескакивает не более чем через k элементов. Вы переходите к узлу, на который указывает этот узел, и уменьшаете k с количеством элементов, которые вы перепрыгнули. Продолжайте делать это, пока не получите k = 0.

Вы рассматривали возможность использования std::map или std::vector?

Вы можете использовать std::map с рангом вставки в качестве ключа. А vector имеет reserve функцию-член.

Вы можете использовать пары отображения std::map (индекс, время вставки) в значения, где время вставки является целым числом "автоинкремента" (в терминах SQL). Порядок пар должен быть следующим:

(i, t) < (i*, t*)

если только

i < i* or t > t*

В коде:

struct lt {
    bool operator()(std::pair<size_t, size_t> const &x,
                    std::pair<size_t, size_t> const &y)
    {
        return x.first < y.first || x.second > y.second;
    }
};

typedef std::map<std::pair<size_t, size_t>, int, lt> array_like;

void insert(array_like &a, int value, size_t i)
{
    a[std::make_pair(i, a.size())] = value;
}

Относительно вашего комментария:

List.Insert () (который работает слишком медленно, так как должен сдвигать каждый элемент),

Списки не меняют свои значения, они перебирают их, чтобы найти место, которое вы хотите вставить, будьте осторожны с тем, что вы говорите. Это может сбивать с толку новичков вроде меня.

Решение, которое по умолчанию включено в GCC, - это структура данных веревка. Вот документация. Обычно веревки приходят на ум при работе с длинными строками символов. Здесь вместо символов ints, но работает то же самое. Просто используйте int в качестве параметра шаблона. (Также может быть pairs и т. Д.)

Вот описание веревки в Википедии.

По сути, это двоичное дерево, которое поддерживает количество элементов в левом и правом поддеревьях (или эквивалентную информацию, которая называется статистикой порядка), и эти подсчеты обновляются соответствующим образом по мере вращения поддеревьев. когда элементы вставляются и удаляются. Это позволяет выполнять O (lg n) операций.

В С ++ вы можете просто использовать карту векторов, например:

int main() {
  map<int, vector<int> > data;
  data[0].push_back(1);
  data[1].push_back(3);
  data[1].push_back(2);
  data[0].push_back(5);
  map<int, vector<int> >::iterator it;
  for (it = data.begin(); it != data.end(); it++) {
    vector<int> v = it->second;
    for (int i = v.size() - 1; i >= 0; i--) {
      cout << v[i] << ' ';
    }
  }
  cout << '\n';
}

Это печатает:

5 1 2 3 

Так же, как вы хотите, а вставки - O (log n).