Создание игр » Featured, STL » Std::sort
Std::sort
Std::sort это алгоритм сортировки, один из представителей семейства алгоритмов stl. Как понятно из его названия, std::sort занимается сортировкой данных. Кстати, std::sort часто (или почти всегда?) опережает по скорости стандартную функцию sort(). Вообще, в STL очень много полезных алгоритмов и sort – один из наиболее часто используемых. Давайте рассмотрим на примере std::sort() использование алгоритмов STL и разберём, где именно и как именно надо использовать алгоритмы, а так же как мы можем модифицировать их поведение с помощью функторов.
Алгоритм std::sort
Как и большинство алгоритмов STL, sort определён в двух формах:
template <class RandomAccessIterator> void sort ( RandomAccessIterator first, RandomAccessIterator last ); template <class RandomAccessIterator, class Compare> void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp ); |
Первая форма алгоритма использует дефолтный функтор сравнения, а вторая позволяет задать его самостоятельно. Выполним простую сортировку массива:
// sort algorithm example #include <iostream> #include <algorithm> #include <vector> using namespace std; int main () { int myints[] = {32,71,12,45,26,80,53,33}; vector<int> myvector (myints, myints+8); // теперь в контейнере: 32 71 12 45 26 80 53 33 vector<int>::iterator it; // используем сравнение по-умолчанию sort (myvector.begin(), myvector.begin()+4); // теперь в контейнере: (12 32 45 71)26 80 53 33 // вот сюда будем добавлять остальные варианты сортировки // печатаем содежимое cout << "myvector contains:"; for (it=myvector.begin(); it!=myvector.end(); ++it) cout << " " << *it; cout << endl; return 0; }} |
std::sort через функцию
Сортировка с использованием нашей собственной функции сравнения элементов в контейнере:
// это функция сравнения для использования внутри std::sort bool sort_function (int i,int j) { return (i<j); } // добавляем в конец main() // иcпользуем нашу функцию сравнения sort (myvector.begin()+4, myvector.end(), sort_function); // теперь в контейнере: 12 32 45 71(26 33 53 80) |
std::sort + функтор
А вот использование функтора:
// это наш функтор сортировки struct sort_class { bool operator() (int i, int j) { return (i<j);} } sort_object; // это добавляем в конец main() // используем функутор сортировки sort (myvector.begin(), myvector.end(), sort_object); // теперь в контейнере: (12 26 32 33 45 53 71 80) |
std::sort и сортировка объектов
Как же с помощью алгоритма sort можно отсортировать контейнер с объектами? Да, собственно, практически так же – меняется мало что. Давайте предположим, что у нас есть класс и контейнер с объектами этого класса:
class MyObject { float m_fPosX; float m_fPosY; float m_fMass; } std::vector<MyObject> vecObjects; |
Вот так мы можем отсортировать объекты в этом массиве по их расположению вдоль оси Х:
struct sort_class_x { bool operator() (MyObject i, MyObject j) { return (i.m_fPosX<j.m_fPosX);} } sort_objectX; sort (myvector.begin(), myvector.end(), sort_objectX); |
Сортировка того же самого набора объектов, но уже по массе:
struct sort_class_mass { bool operator() (MyObject i, MyObject j) { return (i.m_fMass<j.m_fMass);} } sort_objectMass; sort (myvector.begin(), myvector.end(), sort_objectMass); |
И, конечно же, ничего не мешает Вам написать более сложные функции сортировки. Например, сделать функтор, который будет сортировать объекты по массе, а объекты с равной массой будут сортироваться по Х-координате:
struct sort_class_mass_pos { bool operator() (MyObject i, MyObject j) { if (i.m_fMass==j.m_fMass) return (i.m_fPosX<j.m_fPosX); return (i.m_fMass<j.m_fMass); } } sort_objectMassPos; sort (myvector.begin(), myvector.end(), sort_objectMassPos); |
Как-то так. Если есть вопросы – задавайте.
Во. Классная штука. Спасибо за урок.
в структуре
struct sort_class_mass_pos
вас не смущает вот эта строка?
if (i.m_fMass==j.m_fMass)
Кстати, std::sort часто (или почти всегда?) опережает по скорости стандартную функцию sort()
whaaat?
[…] http://dev.mindillusion.ru/std-sort/ […]
А зачем вообще нужен функтор, с затратами на конструктор/деструктор/хранение, если можно задать функцию?
Функтор совсем не обязательно должен иметь тяжеловсные конструктор и деструктор (а если они будут пустые – то и затраты будут вообще нулевые). А главное его приемущество состоит в том, что он зачастую может работать быстрее. Что происходит, например, когда мы вызывает qsort? Плюсы для каждых двух сравниваемых заничений помещают их в стек и вызывают указанную нами функцию сортировки (что достаточно медленно). Когда же мы используем функтор – часто (не всегда, но как правило) компилятор понимает чего мы от него хотим (а хотим мы максимально зианлайнить всё) и оптимизирует соответсвующим образом. Как итог – обычно получаем заметный буст (прирост скорости т.е.).
При этом обычно стоит так же (в статье это не указано, но это так) делать функцию сравнения константной, а сами сравниваемые переменные, если это не POD-типы, а какие-то отсносительно сложные данные, передавать как константные ссылки – это поможет компилятору лучше сообразить что от него требуется.
Вы можете сами сравнить производительность – например, напишите сортировку относительного большого массива (несколько миллионов интов, например) обычным qsort и второй вариант через std::sort и засеките время работы в том и другом случае – разница будет весьма существенной.