LINUX.ORG.RU

[C++] Посоветуйте контейнер, алгоритм... Хранить числа в отсортированном виде, брать с верхушки наименьшее, изменять его, но чтобы принцип неубывания сохранялся всегда. Пересортировка. std::set???


0

0

Нужно иметь объект, в который можно закидывать любые unsigned числа и с «верхушки» этого объекта брать меньшее из имеющихся в нём. Потом это число нужно изменить и дать объекту найти для этого числа новое место - на верхушке оно теперь или десятое от верхушки. То есть, внутри объекта всё должно сортироваться.

Можно взять std::map, std::set, кидать в них числа, они там будут по определению сортироваться.

Но если какой-то узел дерева в этих контейнерах изменить, он сам никуда не переместится, его придётся удалять и вставлять заново. Эта операция удаления-вставки чё-то меня напрягает, не хочу постоянно дёргать аллокатор, т.е. выделение-освобождение памяти. Чисел будет неубывающее количество, преймущественно всегда одно и тоже с редким ростом их числа. Т.е. хочется манипулировать связями между числами, а их особо не месить туда-сюда...

Спасибченко.

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

Попробовать вместо std::map/set использовать boost::intrusive контейнеры? Там операции удаления/вставки очень быстры by design в т.ч. без необходимости выделять память.

bibi ()

Я бы использовал std::set, если производительность не устроила бы, написал свою реализацию дерева под данный случай.

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

Ему надо брать не произвольный элемент, а минимальный. Поэтому дерево избыточно, нужна куча наподобие std::priority_queue.

PS: Хотя, с другой стороны, реальной разницы в перформансе тут скорее всего не будет, а весь реальный код на С++ и так написан через жопу.

Absurd ★★★ ()

>Можно взять std::map, std::set ... Но если какой-то узел дерева в этих контейнерах изменить

В них вообще-то нельзя изменять ключи.

legolegs ★★★★★ ()

set если много вставлять
если вставлять редко, для чисел удобно Loki::AssocVector (обертка кучи в векторе)

gavv ()

>выделение-освобождение памяти
ну это не проблема, аллокаторов много

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

>boost::intrusive
а есть смысл использовать для совсем мелких объектов? будет выигрыш по сравнению с vector или pod-vector?

gavv ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.