Здравствуйте, ser_gunya, Вы писали:


SC>>1. std::set вместо вектора
_>сет работает дольше, как и список и очередь (при аналогичном использовании).
А если скормить ему нестандартный аллокатор? например, бустовский?
Можно написать свой сет, который за счет знания конкретного типа и распределения данных будет работать быстрее.

SC>>2. inplace_merge вместо std::sort
_>не пользовался inplace_merge. если я правильно понял, нужно иметь две отсортированые последовательности, т.е поддерживать эти последовательности отсортированными?
нужно сортировать только вставляемый вектор, что модно сделать быстро, поскольку он маленького размера. Большая последовательность получится отсортированной по построению. Будет ли быстрее — фиг знает, надо проверять. Скорее всего нет, но прпробовать стоит.

SC>>3. tbb::parallel_sort вместо std::sort
_>Я так понимаю это интеловская библиотека!?
_>к сожалению есть ограничение — можно использовать только буст и стл
Можно свою написать по мотивам. Идея в том, чтобы распараллелить.

SC>>4. своя реализация некоторой структуры данных вместо вектора(какая именно — зависит от характера данных)
_>тип данных я привел в примере, это std::vector< std::pair<int, int> >.
Тип не так важен. Важно статистическое распределение данных. В литературе описываются случаи, когда перемешивание элементов массива перед сортировкой поднимало общее быстродействие

_>если ли смысл переписывать отператор меньше для std::pair<int, int>?
никакого

SC>>5. свяо реализация сортировки, которая может заодно и unique сделать.
_>unique занимет немного времени, главная проблема это сортировка
Возможно, имеет смысл поменять что-нибудь в том месте, где эти данные используются, то есть вместо сортировки использовать какой-нибудь более простой алгоритм разбиения, а досортировывать по мере необходимости.