Простой аллокатор

[Igors]

Добрый день

Пример - скопировать массив/контейнер без дубликатов но так чтобы порядок оставшихся сохранился. Напрашивается так

Код

C++ (Qt)
template <class TVec, class TElem>
void CopyWithoutDup( const TVec & src, TVec & dst )
{
 dst.clear();
 std::set <TElem> theSet;
 for (size_t i = 0; i < src.size(); ++i) {
  const TElem & elem = src[i];
  if (theSet.find(elem) != theSet.end()) continue;
  theSet.insert(elem);
  dst.push_back(elem);
 }
}
 

Все вполне хорошо, ну может сделать set указателей и использовать lower_bound - но не суть. Но есть одна небольшая неприятность - это притормаживает т.к. каждый insert вызывает malloc. Понятно что "официальная доктрина" - делайте custom allocator, но это не вызывает энтузиазма. Только что все было легко и просто, а тут разбирайся с классом и все такое.

Часто вполне устраивает простейший аллокатор который распределил бы память один раз на максимально возможное число элементов в set (или др. ассоциативном контейнере), это число мне известно. Есть ли такой готовый? И, по ходу дела, как с этим в Qt контейнерах ?

Спасибо

Edit: виноват, забыл упомянуть что порядок должен быть сохранен. Исправил

[Пантер]

А если sort и unique_copy?

[brankovic]

Лучше всего использовать сортировку, но если не получается:

В бусте есть pool allocator, похоже на ваш случай, но сам я не пользовался.

Ещё по-быстрому можно попробовать tcmalloc, много маленьких одинаковых аллокаций сильно ускоряет (это фактически pool, не намного медленее будет).

Ещё в бусте есть intrusive set. Заполняете в вектор, потом собираете intrusive_set из них, ноды остаются в векторе, удалять можно их вместе с вектором. Но тогда структура при расширении вектора может поломаться, и в TElem придётся добавить 3 указателя для хранения структуры дерева.

[Igors]

А если sort и unique_copy?

Просто так unique_copy скопирует дубликаты если они идут не подряд. А если сначала sort - то изменится порядок следования (забыл указать, исправляю)

Лучше всего использовать сортировку, но если не получается:

Можно и с неизменным порядком через сортировку, но получается длинновато

[Akon]

Использовать вместо set vector, с предварительным reserve(). vector будет сортированным, поиск lower_bound

[brankovic]

изменится порядок следования
...
Можно и с неизменным порядком через сортировку...

std::stable_sort?

[Igors]

std::stable_sort?

Я имел ввиду руками: отсортировать сначала массив указателей и.т.д. Несложно, но длинновато. А stable_sort - не вижу как поможет, насколько помню, он сохраняет изначальный порядок лишь для одинаковых ключей.

Ладно, глянем в буст. Если помните как тот аллокатор там называется - скажите. Спасибо

[brankovic]

http://www.boost.org/doc/libs/1_47_0/libs/pool/doc/interfaces.html