Как связать с номером другое число без использования массива

Question

Допустим, мы прочитали эти значения:

3
1241
124515
5322353
341
43262267234
1241
1241
3213131

И у меня есть такой массив (с элементами выше):

a[0]=1241
a[1]=124515
a[2]=43262267234
a[3]=3
...

Дело в том, что элементы 'порядок в массиве не является постоянным (я должен изменить его где-нибудь в моей программе).

Как узнать, в какой позиции один элемент появляется в прочитанном документе.

Обратите внимание, чтоЯ не могу сделать:

vector <int> a[1000000000000];
a[number].push_back(all_positions);

Поскольку a будет слишком большим (есть ограничение памяти).(допустим, у меня есть только 3000 элементов, но их значения находятся в диапазоне от 0 до 2 ^ 32)

Итак, в приведенном выше примере я хотел бы знать, что все позиции 1241 появляются без повторения итерации.через все прочитанные элементы.

Другими словами, как я могу связать с числом "1241" позиции "1,6,7", чтобы я мог просто получить к ним доступ в O (1) (где на самом деле 1это число позиций, в которых появляется элемент)

Если нет O (1), я хочу знать, какое из них оптимальное ... Я не знаю, ясно ли я пояснил.Если нет, просто скажите это, и я обновлю свой вопрос:)

Answer 1

Вам нужно использовать какой-то динамический массив, например, вектор (std::vector) или другие подобные контейнеры (std::list, возможно, это зависит от ваших потребностей).

Такие структуры данных безопаснее и проще в использовании, чем массив в стиле C, поскольку они заботятся об управлении памятью.

Если вам также нужно искать элемент в O (1), вам следует рассмотреть возможность использования некоторых структур, которые будут связывать как индекс с элементом, так и элемент с индексом. Я не думаю, что STL предоставляет какие-либо, но Boost должен иметь что-то подобное.

Если O (log n) - это стоимость, которую вы можете себе позволить, также рассмотрите std::map

Answer 2

Вам нужна ассоциативная коллекция, но вы можете захотеть связать ее с несколькими значениями.

Вы можете использовать std::multimap< int, int >

или

вы можете использовать std::map< int, std::set< int > >

Я обнаружил, что на практике последнее легче удалить, если вам нужно удалить только один элемент. Он уникален для комбинаций ключ-значение, но не только для ключа или значения.

Если вам нужна более высокая производительность, вы можете использовать hash_map вместо map. Для внутренней коллекции вы не получите большой производительности при использовании хэша, так как у вас будет очень мало дубликатов, и лучше использовать std :: set.

Существует множество реализаций hash_map, и это в новом стандарте. Если у вас нет нового стандарта, идите на повышение.

Answer 3

Вместо вашего массива используйте

std::map<int, vector<int> > a;

Answer 4

Вы можете использовать карту для этого. Как:

std::map<int, std::vector<int>> MyMap;

Таким образом, каждый раз, когда вы сталкиваетесь со значением при чтении файла, вы добавляете его положение на карту. Скажем, X - это значение, которое вы прочитали, а Y - это позиция, тогда вы просто делаете

MyMap[X].push_back( Y );

Answer 5

Вам не нужен разреженный массив из 1000000000000 элементов; используйте std::map для сопоставления позиций со значениями.

Если вы хотите двунаправленный поиск (то есть иногда вы хотите, «каковы индексы для этого значения?», А иногда «каково значение этого индекса?»), Тогда вы можете использовать boost::bimap .

Все усложняется, поскольку у вас есть значения, появляющиеся более одного раза. Вы можете пожертвовать двунаправленным поиском и использовать std::multimap.

Answer 6

Вы можете использовать то, что обычно называют мультикартой .То есть он хранит ключ и несколько значений.Это время поиска O (log).

Если вы работаете с Visual Studios, они предоставляют свои hash_multimap , иначе я могу предложить использовать Boost :: unordered_map со списком в качестве значения?

Answer 7

Для поиска O (1) вы можете хешировать число, чтобы найти его запись (ключ) в хэш-карте (boost :: unordered_map, dictionary, stdex :: hash_map и т. Д.)

Значение может быть вектором индексов, где встречается число, или 3000-битным массивом (375 байтов), в котором установлено число бит для каждого соответствующего индекса, где встречается число (ключ).

boost::unordered_map<unsigned long, std::vector<unsigned long>> myMap;
for(unsigned long i = 0; i < sizeof(a)/sizeof(*a); ++i)
{
   myMap[a[i]].push_back(i);
}

Answer 8

Помимо решения std::map, предлагаемого другими здесь (O (log n)), есть подход хэш-карты (реализованный как boost::unordered_map или std::unordered_map в C ++ 0x, поддерживаемый современными компиляторами).

Это даст вам O (1) поиск в среднем , что часто быстрее, чем основанное на дереве std::map. Попробуйте сами.

Answer 9

Вы можете использовать std :: multimap для хранения как ключа (например, 1241), так и нескольких значений (например, 1, 6 и 7).

insert имеет логарифмическую сложность, но вы можете ускорить ее, если дадите подсказке методу вставки, куда он может вставить элемент.

Answer 10

Кажется, вам нужен std::map<int,int>.Вы можете сохранить отображение, такое как 1241->0 124515->1 и т. Д. Затем выполните поиск на этой карте, чтобы получить индекс массива.