Имеется самый тупой массив типа std::vector, где по индексу можно за O(1) получить элемент. То есть, указатель на начало + индекс = указатель на нужный элемент.
Хочется выдернуть из середины элемент с индексом Y и вставить его в начало.
У элементов с индексами >= Y+1 индексы уменьшаются на 1, т.е. дырки не образуется, а происходит сдвиг всех элементов после выдернутого ближе к началу на 1.
Вставка в начало: вставляемый элемент получает индекс 0, а у всех последующих элементов индекс увеличивается на 1.
Операция «выдернуть из Y и вставить на 0» на самом деле в итоге сохранит индексы у всех элементов начиная с индекса Y+1, а у всех элементов [1...Y-1] индексы увеличатся на 1, а у элемента Y индекс поменяется на 0.
Проще говоря: операция переноса элемента из середины в начало не образует дырок в массиве, переносимый элемент приходит в начало массива, потесняя остальные элементы на 1 в направлении конца.
Ясно, что противоречащие условия. Я не хочу никакого memmove() на 999 элементов, если переношу тысячный элемент в начало. При этом хочется доступа по индексу за O(1) или близко к этому.
А ещё хочется, чтобы элементы в памяти лежали максимально запаковано, с точки зрения хеша, т.е. в идеале это недостижимый std::vector, а на практике хотя-бы какая-то цепочка из блоков, где лежит последовательно по 64 элемента. Что-то memmov-ать в пределах нескольких линий кеша — норм.
