Sort, std

Std::sort це алгоритм сортування, один із представників сімейства алгоритмів stl. Як відомо з його назви, std::sort займається сортуванням даних. До речі, std::sort часто (чи майже завжди?) випереджає за швидкістю стандартну функцію sort(). Взагалі, у STL дуже багато корисних алгоритмів і sort – один із найчастіше використовуваних. Давайте розглянемо з прикладу std::sort() використання алгоритмів STL і розберемо, де як і як треба використовувати алгоритми, і як ми можемо модифікувати їх поведінка з допомогою функторов.

Алгоритм std::sort

Як і більшість алгоритмів STL, sort визначено у двох формах:

Перша форма алгоритму використовує дефолтний функцій порівняння, а друга дозволяє задати його самостійно. Виконаємо просте сортування масиву:

std::sort через функцію

Сортування за допомогою нашої власної функції порівняння елементів у контейнері:

std::sort + функтор

А ось використання функтора:

std::sort та сортування об'єктів

Як за допомогою алгоритму sort можна відсортувати контейнер з об'єктами? Так, власне, практично так само змінюється мало що. Давайте припустимо, що у нас є клас та контейнер з об'єктами цього класу:

Ось так ми можемо відсортувати об'єкти в цьому масиві за їх розташуванням вздовж осі Х:

Сортування того ж набору об'єктів, але вже за масою:

І, звичайно ж, нічого не заважає Вам написати складніші функції сортування. Наприклад, зробити функтор, який сортуватиме об'єкти за масою, а об'єкти з рівною масою сортуватимуться за Х-координатом:

Якось так. Якщо є питання – ставте.

У. Класна штука. Дякую за урок.

у структурі struct sort_class_mass_pos

вас не бентежить ось цей рядок? if (i.m_fMass==j.m_fMass)

До речі, std::sort часто (або майже завжди?) випереджає за швидкістю стандартну функцію sort()

А навіщо взагалі потрібний функтор, із витратами на конструктор/деструктор/зберігання, якщо можна задати функцію?

Функтор зовсім не обов'язково повинен мати важкі конструктор та деструктор (а якщо вони будуть порожні – то й витрати будуть взагалі нульові). А головне його перевага полягає в тому, що він часто може працювати швидше. Що відбувається, наприклад, коли ми викликає qsort? Плюси для кожних двох порівнюваних занищень поміщають їх у стек і викликають вказану нами функцію сортування (що досить повільно). Коли ж ми використовуємо функтор - часто (не завжди, але як правило) компілятор розуміє чого ми від нього хочемо (а хочемо максимально зіанлайнити все) і оптимізує відповідним чином. Як результат – зазвичай отримуємо помітний буст (приріст швидкості тобто).

При цьому зазвичай варто так само (у статті це не вказано, але це так) робити функцію порівняння константної, а самі порівнювані змінні, якщо це не POD-типи, а якісь відносно складні дані, передавати як константні посилання – це допоможе компілятору краще збагнути що від нього потрібно.

Ви можете самі порівняти продуктивність - наприклад, напишіть сортування відносного великого масиву (кілька мільйонів інтів, наприклад) звичайним qsort і другий варіант через std::sort і засікайте час роботи в тому й іншому випадку - різниця буде дуже суттєвою.

---