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

heap ?

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

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

ну т.е. std::priority_queue

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

плюсую этот вариант

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

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

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

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

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

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

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

Вектор + Сортировка.

std::{make,pop,push}_head