Объединение множества контейнеров с помощью алгоритмов STL

Question

У меня есть много списков, векторов, наборов ... (что вы когда-нибудь предпочитаете) указателей, называемых RealAlgebraicNumberPtr для определенного класса.Они отсортированы.

Я хочу объединить их и, конечно же, хочу сделать это быстро и эффективно.

Какой самый лучший выбор?std::merge?Или, может быть, std::set?Я могу предоставить и <и == заказ. </p>

Любые идеи?

Answer 1

Как уже упоминалось, std::merge в порядке.

Только для std :: list, вы можете воспользоваться оптимизацией, которую реализует std::list::merge функция-член : она склеивает узлы спискаиз источника в цель.Таким образом, список источников станет пустым, но это позволит избежать (пере) выделения ресурсов

Re: std::set

, на самом деле вы можете std :: merge в std :: setчтобы получить уникальные значения за один раз.При универсальном слиянии повторяющиеся значения не фильтруются, но результат сортируется , поэтому вы можете применить std::unique к результату.Если вы ожидаете много дубликатов, вы можете быстрее использовать std::set

Answer 2

std::merge настолько эффективен, насколько это возможно.Какой базовый контейнер вы используете, зависит от ваших требований.std::vector имеет наименьшие накладные расходы памяти из всех стандартных контейнеров, поэтому, если ваши данные большие, вы должны придерживаться этого.

Если вы используете std::vector, вы должны resize целевой вектор передобъединение во избежание перераспределения (вы должны быть в состоянии рассчитать необходимый размер заранее) вместо использования std::back_inserter.