Как писать компаратор в с

Как писать компаратор в с

Большинство встроенных в .NET классов коллекций и массивы поддерживают сортировку. С помощью одного метода, который, как правило, называется Sort() можно сразу отсортировать по возрастанию весь набор данных. Например:

int[] numbers = new int[] < 97, 45, 32, 65, 83, 23, 15 >; Array.Sort(numbers); foreach (int n in numbers) Console.WriteLine(n); // 15 23 32 45 65 83 97

Однако метод Sort по умолчанию работает только для наборов примитивных типов, как int или string. Для сортировки наборов сложных объектов применяется интерфейс IComparable . Он имеет всего один метод:

public interface IComparable

Метод CompareTo предназначен для сравнения текущего объекта с объектом, который передается в качестве параметра object? o . На выходе он возвращает целое число, которое может иметь одно из трех значений:

• Меньше нуля. Значит, текущий объект должен находиться перед объектом, который передается в качестве параметра
• Равен нулю. Значит, оба объекта равны
• Больше нуля. Значит, текущий объект должен находиться после объекта, передаваемого в качестве параметра

Например, имеется класс Person:

class Person : IComparable < public string Name < get;>public int Age < get; set; >public Person(string name, int age) < Name = name; Age = age; >public int CompareTo(object? o) < if(o is Person person) return Name.CompareTo(person.Name); else throw new ArgumentException("Некорректное значение параметра"); >>

Здесь в качестве критерия сравнения выбрано свойство Name объекта Person. Поэтому при сравнении здесь фактически идет сравнение значения свойства Name текущего объекта и свойства Name объекта, переданного через параметр. Если вдруг объект не удастся привести к типу Person, то выбрасывается исключение.

var tom = new Person("Tom", 37); var bob = new Person("Bob", 41); var sam = new Person("Sam", 25); Person[] people = < tom, bob, sam>; Array.Sort(people); foreach (Person person in people) < Console.WriteLine($"- "); >

И в данном случае мы получим следующий консольный вывод:

Bob - 41 Sam - 25 Tom - 37

Интерфейс IComparable имеет обобщенную версию, поэтому мы могли бы сократить и упростить его применение в классе Person:

class Person : IComparable  < public string Name < get;>public int Age < get; set; >public Person(string name, int age) < Name = name; Age = age; >public int CompareTo(Person? person) < if(person is null) throw new ArgumentException("Некорректное значение параметра"); return Name.CompareTo(person.Name); >>

Аналогичным образом мы мошли сравнивать по возрасту:

class Person : IComparable  < public string Name < get;>public int Age < get; set; >public Person(string name, int age) < Name = name; Age = age; >public int CompareTo(Person? person) < if(person is null) throw new ArgumentException("Некорректное значение параметра"); return Age - person.Age; >>

Применение компаратора

Кроме интерфейса IComparable платформа .NET также предоставляет интерфейс IComparer:

public interface IComparer

Метод Compare предназначен для сравнения двух объектов o1 и o2. Он также возвращает три значения, в зависимости от результата сравнения: если первый объект больше второго, то возвращается число больше 0, если меньше — то число меньше нуля; если оба объекта равны, возвращается ноль.

Создадим компаратор объектов Person. Пусть он сравнивает объекты в зависимости от длины строки — значения свойства Name:

class PeopleComparer : IComparer  < public int Compare(Person? p1, Person? p2) < if(p1 is null || p2 is null) throw new ArgumentException("Некорректное значение параметра"); return p1.Name.Length - p2.Name.Length; >> class Person < public string Name < get;>public int Age < get; set; >public Person(string name, int age) < Name = name; Age = age; >>

В данном случае используется обобщенная версия интерфейса IComparer, чтобы не делать излишних преобразований типов. Применение компаратора:

var alice = new Person("Alice", 41); var tom = new Person("Tom", 37); var kate = new Person("Kate", 25); Person[] people = < alice, tom, kate>; Array.Sort(people, new PeopleComparer()); foreach (Person person in people) < Console.WriteLine($"- "); >

Объект компаратора указывается в качестве второго параметра метода Array.Sort() . При этом не важно, реализует ли класс Person интерфейс IComparable или нет. Правила сортировки, установленные компаратором, будут иметь больший приоритет. В начале будут идти объекты Person, у которых имена меньше, а в конце — у которых имена длиннее:

Tom - 37 Kate - 25 Alice - 41

Использование стандартной сортировки

Для сортировки массивов и векторов в STL есть функции sort и stable_sort (последняя реализует устойчивую сортировку, которая не меняет порядок элементов массива, если они равны).

Для сортировки вектора A алгоритм сортировки нужно вызывать так:

Для сортировки массива A из n элементов функцию сортировки нужно вызывать так:

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

Функция-компаратор

Алгоритм сортировки сравнивает элементы при помощи операции «меньше». Можно самостоятельно реализовать операцию «меньше» и использовать её в алгоритме сортировки. Например, давайте упорядочим числа по последней цифре, а если последние цифры равны, то порядок неопределён. В этом случае мы вводим между ними отношение порядка, обозначим его \(\prec\). Например, следующие отношения будут верны, так как последняя цифра левого числа меньше, чем последняя цифра правого числа:

А следующие отношения порядка неверны:

Отношение порядка должно удовлетворять следующим свойствам:

2. Если \(a\prec b\), то \(b\nprec a\).

3. Если \(a \prec b\) и \(b \prec c\), то \(a \prec c\).

Для того, чтобы использовать функцию-компаратор, необходимо объявить функцию, которая получает на вход два сравниваемых значения и возвращает значение типа bool, при этом она возвращает true, если первый аргумент меньше второго аргумента, то есть обязан в упорядоченном массиве идти раньше второго.

Пример реализации такой функции для сортировки значений по последней цифре:

bool cmp(int a, int b)
return a % 10 < b % 10;
>

Эта функция передается в функцию sort третьим параметром:

sort(a.begin(), a.end(), cmp);

Если есть два элемента \(a\) и \(b\), такие, что \(a\nprec b\) и \(b\nprec a\), то с точки зрения сортировки эти элементы «равны». В нашем примере это два числа, оканчивающиеся на одинаковые цифры. Тогда их порядок не определен, если используется функция sort. Если же использовать функцию stable_sort, то эта функция не переставляет равные элементы, то есть сохраняется тот же порядок, который был в массиве до сортировки.

Приведем еще один пример сортировки двух чисел — по возрастанию последней цифры числа, а если последние цифры равны — то по убыванию самих чисел.

Заметим также, что в функцию-компаратор лучше передавать объекты не по значению, а по ссылке, в этом случае они не будут копироваться (что может занимать значительное время при передачи крупных объектов, например, строк, векторов и т.д.). Тогда функцию нужно объявлять так:

Структура pair

В библиотеке STL есть шаблон класса pair .

Класс pair — это два значения, то есть «пара». У объектов этого класса два поля, первое называется first , второе называется second . Например, класс pair можно использовать для хранения точек плоскости (точка — это две координаты) или рациональных дробей (дробь — два числа).

Один экземпляр объектов класса pair определяется так:

Теперь p — это структура с двумя полями, типа int каждое, им можно присваивать значения:

p.first = 1;
p.second = 2;

Можно сразу присвоить значение «паре» целиком, здесь может оказаться полезным функция make_pair , у которой два аргумента, и которая возвращает объект класса pair , поля которого равны двум аргументам. Например:

p = make_pair(1, 2);

Можно создавать массивы и векторы из pair , например:

pair сортируются в лексикографическом порядке, то есть сначала они упорядочиваются по значению поля first , а при равном значении поля first — по значению поля second . Поэтому для решения задачи сортировки, например, чисел по последней цифре можно создать pair , у которой поле first будет равно последней цифре числа, а поле second — самому числу. Рассмотрим два примера реализации считывания и создания такого массива:

int n;
cin >> n;
vector > a(n);
for (int i = 0; i < n; ++i) cin >> a[i].second;
a[i].first = a[i].second % 10;
>

А в следующем примере будем использовать функцию make_pair для создания пары и добавления ее в конец вектора:

int n;
cin >> n;
vector > a;
for (int i = 0; i < n; ++i) int num;
cin >> num;
a.push_back(make_pair(n % 10, n));
>

Элементами пары могут быть объекты разных типов, не только числа.

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

Структура tuple

Допустим, в одной переменной нужно хранить не два, а большее число полей. Например, информация о человеке может содержать поля имя, фамилия, возраст, и необходимо как-то сортировать эти данные.

Возможные варианты решения:

1. Создание собственной структуры данных с указанием нужных полей. Например,

struct person string lastname;
string firstname;
int age;
>

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

2. Использовать pair, один из элементов которого также является pair.

Например, можно объявить переменную так:

pair > person;
person.first = lastname;
person.second.first = firstname;
person.second.second = age;

Это не требует объявления структуры, но достаточно неудобно обращаться к полям структуры через конструкции вида .second.first .

Начиная со стандарта C++11 в STL есть класс tuple (кортеж), который предоставляет возможность создавать аналоги pair из любого количества полей. Например, для представления класса из трех полей типа string , string , int можно объявить класс следующим образом:

Для доступа к полям tuple используется конструкция get следующим образом:

get(p) = lastname;
get(p) = firstname;
get(p) = age;

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

Например, объявим класс person как tuple из трех полей при помощи typedef (для упрощения последующего использования)

Или можно использовать функцию make_tuple , аналогичную make_pair:

typedef tuple person;
int n;
cin >> n;
vector p;
for (int i = 0; i < n; ++i) string lastname, firstname;
int age;
cin >> lastname >> firsstname >> age;
p.push_back(make_tuple(lastname, firstname, age));
>

Tuple сортируются также в лексикографическом порядке — сначала по первому полю, при равенстве первого поля — по второму, затем по третьему и т.д.

Функция sort и компаратор в C++: что это такое

Привет, дорогие читатели! Этот урок посвящен встроенной сортировке C++ и ее учителю — компаратору.

Что такое функция sort

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

Принцип работы построен на алгоритме быстрой сортировки (quicksort), так что за быстроту можно не волноваться.

Также в C++ имеется другая сортировка — qsort, но она работает значительно медленнее текущей.

Чтобы нам оперировать данной функцией понадобится для начала подключить библиотеку — .

#include 

Многие языки не могут похвастаться такой гибкостью. Например, Pascal, там придется самостоятельно писать алгоритм сортировки (который составляет несколько десятков строк !).

Функция sort для вектора

Вот как выглядит конструкция вызова:

sort (начало>, конец>, компаратор>);

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

#include #include // vector #include // sort using namespace std; int main ()  setlocale(0, ""); int n; vector int> vec; cout  <"Введите количество элементов последовательности: "; cin >> n; int a; for (int i = 0; i  n; i++)  cout  + 1  <") "; cin >> a; vec.push_back(a); > cout  <"Вот как выглядит последовательность до: "; for (int i = 0; i  n; i++)  cout  [i]  <" "; > sort (vec.begin(), vec.end()); // сортировка cout   <"После сортировки: "; for (int i = 0; i  n; i++)  cout  [i]  <" "; > sort(vec.begin() + n / 2, vec.end(), comp); cout   <"А вот еще раз: "; for (int i = 0; i  n; i++)  cout  [i]  <" "; > system("pause"); return 0; >

Введите количество элементов последовательности: 10 1) 1 2) 4 3) 2 4) 8 5) 9 6) 5 7) 3 8) 7 9) 10 10) 6 Вот как выглядит последовательность до: 1 4 2 8 9 5 3 7 10 6 А вот как после: 1 2 3 4 5 6 7 8 9 10 А вот еще раз: 1 2 3 4 5 10 9 8 7 6 Process returned 0 (0x0) execution time : 0.010 s Press any key to continue.

имя списка>.sort(компаратор>);