Блог

Я работаю с std ::vectors для графической программы. Эти векторы содержат позиции на экране, и они сортируются. Теперь я хотел бы объединить их вместе и сохранить фактическую сортировку, удалив возможные дубликаты, что-то вроде этого:

 vector1 : [2, 6, 10]
vector2 : [1, 5, 6, 10]
result  : [1, 2, 5, 6, 10]
  

Для хорошего понимания: я уже запрограммировал себе функцию для выполнения фактического слияния на основе базовых функций std :: vector at() insert() , таких как , , size() , но моя функция, похоже, является разрывом в производительности (я полагаю, O (n ²)).

Я ищу другие классы std (std:: vector потомки, если это возможно, для простоты программирования), которые содержат merge() и sort(kind="unique") в качестве базовых методов.

Кто-нибудь знает, существуют ли такие классы в STL?

STL имеет эту концепцию разделения контейнеров и алгоритмов, поэтому, хотя std::vector на самом деле у него нет членов для сортировки или объединения, STL предоставляет все необходимые алгоритмы с помощью шаблонов функций, не являющихся членами, которые обрабатывают итераторы.

Например. для сортировки вектора, который вы бы назвали

 std::sort(vector1.begin(),vector1.end());
  

Проверьте заголовок алгоритма для получения дополнительной ссылки, а именно std::sort и std::merge .

Для объединения и удаления дубликатов вы можете использовать std::set_union , что, вероятно, ваш лучший выбор. Вот пример рабочего кода.

Вот руководство по итераторам, хотя для этой конкретной задачи вам понадобится только понятный vector::begin() и vector::end() .

Для удаления дубликатов из одного контейнера вы обычно используете std::unique() или std::unique_copy() , как упоминал @unwind .

Есть одно предостережение с std::unique() и другими алгоритмами «удаления», такими как std::remove() , которое вытекает из того «разделения контейнеров и алгоритмов», о котором я упоминал: алгоритм не имеет средств для фактического удаления элементов из контейнера — ему был предоставлен итератор или диапазон, но он понятия не имеет о фактическом типеи реализация контейнера.

Поэтому вместо этого обычный подход заключается в том, чтобы просто переместить элементы, предназначенные для удаления, в конец диапазона, а затем вернуть итератор к первому из этих элементов. Затем вы можете вызвать другую функцию для фактического удаления (обратите внимание, что на этот раз это будет контейнерный метод).

Вот как это делается с std::unique() :

 vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
  

std::unique_copy этот трюк не потребуется, но он в значительной степени скопирует весь вектор, поэтому это имеет смысл, только если вы все равно намеревались его скопировать.