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

Ответ 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 выполняет линейный поиск, потому что он не может считать диапазон отсортированным).

Ответ 2

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

Ответ 3

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

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

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

Ответ 4

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

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

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

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

Ответ 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 обычно реализует слияние, но он знает, что он сортирует список и может перехватывать узлы вместо копирования. Сопоставленный списком метод mergesort может сортировать список в O (n log n) времени только с O (log n) дополнительной памятью, в то время как ваш типичный mergesort (например, 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.

Ответ 6

Отвечая на вопрос "Почему?"

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

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

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