Какой алгоритм лучше всего подходит для несмежного массива с индексированием?

Question

Мне нужна помощь в написании алгоритма на C / C ++ (хотя подойдет любой пример языка). Целью является контейнер / массив, который позволяет вставлять по любому индексу. Однако, если вставить элемент в индекс, который не близок к существующему индексу, то есть приведет к большому пустому пространству сегментов. Тогда массив будет минимизировать пустые сегменты.

Допустим, у вас есть набор элементов, которые необходимо вставить в следующие индексы:

14
54
56
57
12
8
6
5678

Непрерывный массив будет производить структуру данных. Как то так:

0
1
2
3
4
5
6 val
7
8 val
9
10
11
12 val
...

Тем не менее, я ищу решение, которое создает новый массив, когда индекс не находится в пределах x сегментов своего ближайшего соседа.

Примерно так:

Array1
6 val
7 
8 val
10
11
12 val
13
14 val

Array2
54 val
56 val
57 val

Array 3
5678 val

Затем используйте какую-то карту индекса, чтобы найти массив, в котором находится индекс во время поиска. Мой вопрос заключается в том, какой алгоритм я должен смотреть, чтобы сгруппировать индексы во время вставки? (сохраняя при этом хороший компромисс между временем и пространством)

---

Edit: Спасибо за ответы до сих пор. Данные, которые я собираюсь просмотреть, будут содержать один или два очень больших диапазона индексов без пропусков, затем один или два очень больших пропуска, а затем, возможно, пару «колеблющихся» отдельных значений. Также данные должны быть отсортированы, поэтому хеш-таблицы отсутствуют.

Answer 1

Может быть, то, что вы хотите, это разреженный вектор?Попробуйте реализацию Boost .

Answer 2

Вы хотите использовать разреженные массивы или что-то вроде хэша, в зависимости от обстоятельств. В общем:

1. Если вы собираетесь в конечном итоге получить длинные участки заполненных сегментов, разделенных большими пробелами, то вам лучше использовать разреженный массив, поскольку в этой ситуации они хорошо оптимизируют использование памяти.
2. Если вы собираетесь просто получить разбросанные записи в огромном море пустых дыр, вам лучше использовать хеш.

Answer 3

Почему бы просто не использовать хеш-таблицу / словарь? Если вам действительно нужно что-то конкретное, первое, что приходит мне в голову, - это дерево B. Но, возможно, есть и гораздо лучшие решения, чем это.

Answer 4

Я считаю, что вы ищете хэш-карту или, в более общем случае, карту. Вы можете использовать предоставленный STL класс карты.

Это звучит как то, что вы ищете:

http://www.cplusplus.com/reference/stl/map/