Почему vector не имеет метода sort () в качестве функции-члена vector, а list -?

Question

Существует метод sort () для списков в STL. Что абсурдно, потому что я был бы более склонен сортировать массив / вектор. Почему sort () не предусмотрен для вектора? Есть ли какая-то философия, лежащая в основе создания векторного контейнера или его использования, такого рода сортировка для него не предусмотрена?

Answer 1

Как уже было сказано, стандартная библиотека предоставляет шаблон функции без членов, который может сортировать любой диапазон по паре итераторов произвольного доступа.

Было бы совершенно избыточно иметь функцию-член для сортировки вектора.Следующие значения будут иметь то же значение:

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

Один из первых принципов STL состоит в том, что алгоритмы не связаны с контейнерами.То, как данные хранятся и как ими манипулируют, должно быть как можно слабее связанным.

Итераторы используются в качестве интерфейса между контейнерами (которые хранят данные) и алгоритмами (которые работают с данными).Таким образом, вы можете написать алгоритм один раз, и он может работать с контейнерами различных типов, и если вы пишете новый контейнер, существующие универсальные алгоритмы могут использоваться для манипулирования его содержимым.

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

Как правило, в двух случаях контейнер должен реализовывать алгоритм:

• Если универсальный алгоритм не может работать с контейнером, но существует другой, зависящий от контейнера алгоритм, который может обеспечить те же функции, что и в случае с std::list::sort.

• Если контейнер может обеспечить конкретную реализацию алгоритма, которая более эффективна, чем универсальный алгоритм, как в случае с std::map::find, который позволяет найти элемент на карте в логарифмическом времени (универсальный алгоритм std::find выполняетлинейный поиск, потому что он не может предположить, что диапазон отсортирован).

Answer 2

Сортировка, специфичная для вектора, не даст никакого преимущества перед std::sort из <algorithm>. Тем не менее, std::list предоставляет свой собственный sort, потому что он может использовать специальные знания о том, как list реализован для сортировки элементов путем манипулирования ссылками вместо копирования объектов.

Answer 3

Вы можете легко сортировать vector с помощью:

sort(v.begin(), v.end());

---

ОБНОВЛЕНИЕ: (ответ на комментарий): Ну, они, безусловно, предоставили это по умолчанию . Разница в том, что это не функция-член для vector. std::sort - это обобщенный алгоритм, который должен работать для всего, что , которое предоставляет итераторы. Тем не менее, он действительно ожидает, что итератор произвольного доступа будет эффективно сортировать. std::list, будучи связанным списком, не может эффективно обеспечить произвольный доступ к его элементам. Вот почему он предоставляет собственный специализированный алгоритм сортировки.

Answer 4

std::sort() в <algorithm> выполняет сортировку на контейнерах с итераторами произвольного доступа, таких как std::vector.

Также существует std::stable_sort().

edit - почему std::list имеет свою собственную функцию sort() по сравнению с std::vector?

std::list отличается от std::vector и std::deque (и произвольный доступ (итеративный) в том, как это реализовано, поэтому он содержит собственный алгоритм sort, который специализирован для его реализации.

Answer 5

Уже есть интересные элементы ответа, но на самом деле по этому вопросу можно сказать еще кое-что: хотя ответ на вопрос «почему std::vector не имеет sort функции-члена?»действительно, «потому что стандартная библиотека предоставляет функции-члены только тогда, когда они предлагают больше, чем универсальные алгоритмы», реальный интересный вопрос - «почему у std::list есть sort функция-член?», и некоторые вещи не были объясненыпока: да , std::sort работает только с итераторами с произвольным доступом, а std::list предоставляет только двунаправленные итераторы, но , даже если std::sort работает с двунаправленными итераторами, std::list::sort все равно будет предлагать больше.И вот почему:

• Прежде всего, std::list::sort стабильно, а std::sort нет.Конечно, есть еще std::stable_sort, но он также не работает с двунаправленными итераторами.

• std::list::sort обычно реализует сортировку слиянием, но он знает, что сортирует список иможет связывать узлы вместо того, чтобы копировать вещи.Сортировка с учетом списка может сортировать список за O (n log n) только с O (log n) дополнительной памятью, в то время как типичная сортировка слиянием (например, std::stable_sort) использует O (n) дополнительной памяти или имеет O (n log² n) сложность.

• std::list::sort не делает недействительными итераторы.Если итератор указывает на определенный объект в списке, он все равно будет указывать на тот же объект после сортировки, даже если его позиция в списке не такая же, как до сортировки.

• И последнее, но не менее важное: std::list::sort не перемещает и не меняет объекты вокруг, поскольку он только связывает узлы.Это означает, что он может быть более производительным, когда вам нужно сортировать объекты, которые дорого перемещать / менять, но также может сортировать список объектов, которые даже нельзя перемещать, что совершенно невозможно для std::sort!

В принципе, даже если std::sort и std::stable_sort работали с двунаправленными или прямыми итераторами (и было бы вполне возможно, мы знаем алгоритмы сортировки, которые работают с ними), они все равно не могли бы 'Мы не можем предложить все, что может предложить std::list::sort, и они также не могли повторно связать узлы, поскольку стандартные библиотечные алгоритмы не позволяют изменять контейнер, только указанные значения (изменение связей узлов считается изменяющим контейнер).С другой стороны, выделенный метод std::vector::sort не может предложить ничего интересного, поэтому стандартная библиотека его не предоставляет.

Обратите внимание, что все, что было сказано о std::list::sort, такжеверно для std::forward_list::sort.

Answer 6

Ответ на вопрос «Почему?»

Алгоритм сортировки для std :: vector такой же, как и для сортировки собственного массива, и такой же (вероятно), как и для сортировки пользовательского векторного класса.

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

Это позволяет вам написать контейнер, который может иметь определенные характеристики, ичтобы получить алгоритмы бесплатно.Пользовательская реализация предоставляется только в тех случаях, когда существует некоторая особая характеристика данных, означающая, что стандартный алгоритм не подходит, как в случае с std :: list.