Използване на стандартното сортиране
сортиране и stable_sort функции
За сортиране на масиви и вектори 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) върне a % 10 b; >
Обърнете внимание също, че впо-добре е обектите да се предават на функцията за сравнение не по стойност, а по препратка, в който случай те няма да бъдат копирани (което може да отнеме много време при предаване на големи обекти, например низове, вектори и т.н.). Тогава функцията трябва да се декларира по следния начин:
двойна структура
STL библиотеката има двойка шаблони за класове.
Класът двойка е две стойности, т.е. "двойка". Обектите от този клас имат две полета, първото се нарича първо, второто се нарича второ. Например класът двойка може да се използва за съхраняване на точки в равнина (една точка е две координати) или рационални дроби (една дроб е две числа).
Един екземпляр на двойка обекти се дефинира по следния начин:
Сега p е структура с две полета, всяко от тип int, на които могат да бъдат присвоени стойности:
p.first = 1; p.second = 2;
Можете незабавно да присвоите стойност на "двойката" като цяло, тук може да бъде полезна функцията make_pair, която има два аргумента и която връща обект от класа pair, чиито полета са равни на два аргумента. Например:
p = make_pair(1, 2);
Можете да създавате масиви и вектори от pair, например:
двойка се сортират в лексикографски ред, т.е. първо се подреждат по стойността на първо поле и ако стойността на първото поле е равна, се подреждат по стойността на второто поле. Следователно, за да разрешите проблема със сортирането, например, на числата по последната цифра, можете да създадете двойка, в която първото поле ще бъде равно на последната цифра на числото, а второто поле ще бъде самото число. Помислете за два примера как да четете и създавате такъв масив:
> a(n); за (int i = 0; i> a[i].second; a[i].first = a[i].second % 10; >
И в следващия пример ще използваме функцията make_pair, за да създадем двойка и да я добавим в края на вектора:
> a; за (int i = 0;аз > брой; a.push_back(make_pair(n % 10, n)); >
Елементите на една двойка могат да бъдат обекти от различен тип, а не само числа.
Друга типична употреба на двойка при сортиране е сортирането на данни при запазване на информацията за реда. Например, да кажем, че е дадена последователност от низове, те трябва да бъдат сортирани по азбучен ред, но за всеки низ запомнете номера му във входните данни. В този случай трябва да използвате pair , в което първото поле е низ, а второто поле е число, в което ще се съхранява числото:
> a(n); за (int i = 0; i> a[i].first; a[i].second = i; >
кортежна структура
Да кажем, че в една променлива трябва да съхранявате не две, а повече полета. Например информацията за дадено лице може да съдържа полетата име, фамилия, възраст и е необходимо по някакъв начин да сортирате тези данни.
Възможни решения:
1. Създаване на собствена структура от данни със задължителните полета. Например,
структура лице низ фамилия; низ собствено име; int age; >
В този случай ще трябва да декларирате самата структура, след което да приложите операцията за сравнение, която може да отнеме доста код.
2. Използвайте двойка, един от елементите на която също е двойка.
Например, можете да декларирате променлива по следния начин:
двойка > person; person.first = фамилия; person.second.first = име; person.second.second = възраст;
Започвайки със стандарта C ++ 11, STL има клас кортеж (кортеж), който предоставя възможност за създаване на двойки аналози от произволен брой полета. Например, за да представите клас от три полета от тип string, string, int, можете да декларирате класа, както следва:
За достъп до полетата на кортеж използвайте конструкцията get, както следва:
get(p) = фамилия; get(p) = първо име; get (p) = възраст;
Параметърът, предаван на функцията get в ъглови скоби, е номерът на полето, индексирането започва от нула. Тази стойност трябва да е константа, т.е. да е дефинирана по време на компилирането на програмата; не можете да използвате променлива като тази стойност.
Например, нека декларираме класа person като кортеж от три полета, използвайки typedef (за да опростим по-късната употреба)
p(n); за (int i = 0; i> get (p[i]) >> get (p[i]) >> get (p[i]); >
Или можете да използвате функцията make_tuple, която е подобна на make_pair:
p; за (int i = 0; i > фамилия >> име >> възраст; p.push_back(make_tuple(фамилия, собствено име, възраст)); >
Кортежите се сортират и по лексикографски ред - първо по първото поле, ако първото поле е равно - по второто, след това по третото и т.н.