LINUX.ORG.RU

выбор структуры данных

 ,


0

1

Какую выбрать структуру данных?

Список целых чисел (на отрезке от нуля до N), элементы добавляются последовательно, процентов на 80 в отсортированном порядке. Элементов в списке немного, обычно до 20, но процедура наполнения списка вызывается часто.

И главное, после наполнения списка извлечь надо только уникальные элементы в отсортированном порядке.

Avl, как я понимаю, не вполне подходят из-за необходимости часто балансировать дерево.

Главное требование - скорость добавления и извлечения уникальных сортированных. Память не критична, время удаления не критично.

Что бы выбрать?


процентов на 80 в отсортированном порядке

вы не поверите, но /dev/random выдаёт процентов на 70 «в отсортированном» порядке :-)

MKuznetsov ★★★★★ ()
Ответ на: комментарий от yoghurt

ну линейно от N так что проще учитывая размеры и характер входа любая примитивная сортировка

тем более есть

uniqUE

qulinxao ★★☆ ()
Последнее исправление: qulinxao (всего исправлений: 1)
Ответ на: комментарий от qulinxao

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

Думал, вдруг есть более быстрый способ :)

jcdr ()
Ответ на: комментарий от yoghurt

std::set<int> и не запаривайся

это медленно получается. целочисленный список с последующей сортировкой раза в 2 быстрее

jcdr ()
Ответ на: комментарий от jcdr

а индекс элемента вектора - значение, хранящиеся в списке. если N не особо большое (как в моем случае), то получается достаточно быстро. Т.к. каждое добавление элемента гаранитрует уникальность значения в таком списке

jcdr ()

На таком объеме вектор лучший вариант.

panter_dsd ★★★★ ()

при таких условиях и массив сойдёт

Harald ★★★★★ ()

20 элементов? На таком количестве данных все равно, что ты будешь использовать.

m0rph ★★★★★ ()

Элементов в списке немного, обычно до 20

vector или unordered_set (чтобы от дубликатов избавиться сразу)

invy ★★★★★ ()
Последнее исправление: invy (всего исправлений: 2)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.