Есть ли потомки std :: vector, которые могут сливаться и сортироваться?

Question

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

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?

Answer 1

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

E.g. сортировать вектор вы бы назвали

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

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

Чтобы слить и удалить дубликаты, вы можете использовать std::set_union, что, вероятно, будет вашим лучшим выбором. Here is working code example.

Here - учебник по итераторам, хотя для этой конкретной задачи вам понадобится только самоочевидные 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 не потребует этот трюк, но это будет в значительной степени скопировать весь вектор, так что имеет смысл, только если вы хотели, чтобы скопировать его в любом случае.