Зачем нужен std::unique?

Question

[Василий Мельников]

Вопрос не, в том что он делает, а для чего и почему так реализован?
Грубо говоря, если есть набор данных, то чтобы оставить только уникальные элементы, придется сначала отсортировать, а потом уже использовать unique. Иначе поведение не определено.
Как-то так если ничего не напутал:

std::vector<int> a = {1, 3, 4, 454, 5454, 4, 3, 2, 2, 1, 1, 2, 3, 5, 2, 1, -32};
std::sort(begin(a), end(a));
a.erase(std::unique(begin(a), end(a)), end(a));

Есть подозрение, что сделано так, потому как сортировка у каждого может быть своя уже отсортировано и прочее бла бла бла. Но всё равно странно.
Скажем так когда-то давно когда впервые воспользовался этим методом, был неприятно удивлен, т.к. естественно ман не прочитал. А тут как раз недавно набрел на срач по этому поводу...

Какие у кого мысли?
Может он вообще для другого нужен?

Comments

[Толстый Лорри]

Стабильное удаление повторов в любом контейнере любого размера без сортировки и копирования - задача нетривиальная. Сортировка любого контейнера - тоже. Поэтому решение в духе стандартной библиотеки - оставить только максимально абстрактные алгоритмы.
Мне кажется, что функцию стоило назвать как-то вроде std::dedup, чтобы не было путаницы и неоправданных ожиданий.

[Roman]

Используется например во всяких GIS для построений и сохранения инфы.
https://www.boost.org/doc/libs/1_69_0/libs/geometr...

[Василий Мельников]

Roman, Но заметь, в бусте контейнер не обязан быть отсортирован. И в приведенном примере, сортировка даже вредна, т.к. порядок элементов важен.
В этом то и заключается вопрос, получается, что стандартную библиотеку добавлен крайне узкоспециализированный алгоритм, с жесткими контрактами.

[Roman]

Василий Мельников, Ответ на этот вопрос нужно искать у/в истоках STL
Можно поискать труды https://en.wikipedia.org/wiki/Alexander_Stepanov

[Василий Мельников]

Roman, можно поискать. У него на сайте даже мейл есть. Насколько прилично к человеку с такими глупыми вопросами приставать?

[Roman]

Василий Мельников, за спрос денег не берут)

[Roman]

https://www.teamsandtechnology.com/dh/writing/arch...

This illustrates an important STL principle:

Use the right container

The flexibility of the STL can catch out the unwary programmer: just because most of the algorithm implementations work with all containers, this is not to say that they are interchangeable. The storage, retrieval and performance characteristics of all STL components are precisely defined - indeed, the library is unique in offering this level of detail in its specification and documentation. Be aware of these characteristics, and use the most appropriate combination of STL container and algorithms for the task at hand

И тут немного collaboration.cmc.ec.gc.ca/science/rpn/biblio/ddj/...

Answer 1

[Александр Таратин]

https://ru.cppreference.com/w/cpp/algorithm/unique - расписано яснее некуда.
Для хранения множества уникальных элементов просто используйте std::set или std::unordered_set

Comments

[Василий Мельников]

Там, что логично, не описано зачем. Хорошо описано как устроено, контракты, даже примеры реализации и использования.

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

[Максим Мосейчук]

Василий Мельников, сначала делать сортировку не нужно, нужно в таком случае использовать set.

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

[Василий Мельников]

fshp, Да, знаю, я это всё и даже именно так и делаю. Просто стало интересно, раз такая функция есть значит она востребована. Наверное. Потому как кажется, что уж больно узкоспециализированная штука.
Да и надо поэксперементировать, есть подозрение, что в каких-то случаях sort+unique будет быстрее set. Всё-таки set хорошо работает когда в него сразу данные накапливать. А если пришёл вектор и куда-нибудь надо отдать вектор дальше, то такие трансформации через set становятся накладными.

[Василий Мельников]

Я измерил скорость работы для удаления дублирующихся элементов с помощью set и связки sort+unique
Для массива интов разница в 1.5-2 раза в пользу второго варианта. Притом с увеличением длины выборки разница даже увеличивается. Понятно, что это исследование сферического коня в вакууме. Но всё-таки. Может кому-то любопытно.

[laphroaig]

Василий Мельников, есть множество примеров когда сортированный вектор или дека гораздо эффективней ассоциативных массивов. В этих случаях и применяется