Стандартна библиотека, част I

Standard Template Library

Както вече споменахме на няколко места, на състезания няма да се налага сами да пишете повечето стандартни структури данни, а както и някои от по-разпространените алгоритми. В тази тема ще покажем някои от по-често ползваните от тях.

Какво е STL?

Да започнем с това какво представлява STL. Вече говорихме какво е темплейт - просто начин да се абстрахираме от типа данни, с които работи дадена структура данни или алгоритъм. STL, или на английски "Standard Template Library" представлява библиотека от алгоритми и функции, реализирана на базата на темплейти за да може да работи с произволни типове данни.

Какво съдържа

Основни структури данни: динамичен масив (vector), опашка (queue и deque), свързан списък (list), стек (stack), асоциативен масив (map и multimap), множество (set и multiset), приоритетна опашка (priority_queue или heap), и (не точно в STL, но все пак) стринг (string).
Основни алгоритми: сортиране (sort()), обръщане (reverse()), размяна (swap()), минимум (min()), максимум (max()), премахване на дубликати (unique()), произволно разбъркване (random_shuffle()), следваща пермутация (next_permutation()), намиране на n-ти елемент (nth_element()).

Какво липсва

За съжаление има и много неща, които би ни се искало да бъдат включени в нея, но липсват. Примери за такива са дълги числа (long numbers); геометрия; регулярни изрази и алгоритми за намиране на подстринг в стринг (pattern matching); намиране на най-малко общо кратно (LCM) или най-голям общ делител (GCD); бързо вдигане на степен; умножение и като цяло работа с матрици; намиране на брой битове в число...
и, всъщност, всякакви други алгоритми. Като цяло има толкова функции, които би било страхотно ако присъстваха, но по някаква причина ги няма. Тъжнотийка.

Namespace

По-рано коментирахме това, та сега само ще напомним: за да ползвате всички неща в STL, е нужно да включите пространството "std". Това става с реда using namespace std; след #include-ите в началото на програмата.

Контейнери

За "структури данни" в STL се ползва името контейнери. Това име идва поради специфичността на структурите данни, които са имплементирани в STL - това са само такива структури данни, които съдържат елементи (подредени по някакъв начин) и дават достъп до тях. Те рядко, ако изобщо, предоставят методи, които да връщат някаква по-специфична информация, както например тяхна сума, работа върху подинтервали или други подобни, както например беше при префиксния масив.

Тук ще разгледаме най-често ползваните от тях - всички от гореизброените, без list, multimap и multiset. Като цяло интерфейсът им е доста сходен (голяма част от методите се повтарят), в следствие на което нещото, което реално трябва да запомните е разликите между структурите данни. Обемът на тази тема не трябва да ви плаши, тъй като почти всичко са интуитивни неща, като много от тях, както казахме, се повтарят.

pair

#include <utility>
Съхранява двойка обекти от произволен тип. Това става чрез два темплейта, K и T, вместо стандартния един (само T). Така примерно можете да имате двойки от тип pair<string, int>, които съхраняват името на човек и неговите години. Често се ползва, когато искате да върнете две стойности, вместо само една, или искате да сортирате двойки елементи (примерно точки в 2D). Ако забелязвате, това е по-бърза за писане алтернатива на това, да създадете структура с две стойности.

Малко скрито остава това, че за нея са предефинирани и операторите <, == и т.н. Те са направени да работят по следния начин: първо се сравняват първите елементи от двете двойки, а ако те са еднакви се сравняват вторите.

Типът се задава по следния начин: pair <K, T>. За да създадете двойка, може да ползвате функцията make_pair(K val1, T val2), която връща pair<K, T> тип, със стойности val1 и val2. Можете да достъпите първия елемент чрез .first, a втория - чрез .second. Забележете, че това е директен достъп до данните - first и second не са методи - и затова няма скоби() след тях!

Тъй като е темплейтен тип, то няма проблем едната от стойностите да е друг pair. Например, ако искате бързо да направите структура, която съдържа координатите на двумерна точка с целочислени координати и някаква double стойност (примерно тегло на въпросната точка), можете да направите:

vector

#include <vector>
STL-ска имплементация на динамичен масив. Значително по-добра от тази, която ние написахме, така че ползвайте нея, когато ви трябва.

Дребен съвет от нас: не ползвайте вектори за щяло и нещяло. Kогато можете да ползвате обикновен масив - ползвайте обикновен масив. Понякога програма, която ползва вектори, може да е няколко пъти по-бавна от аналогична програма със стандартни масиви. Често без STL бихме ползвали повече памет, но какво от това? Ако програмата се събира в ограниченията по памет, то няма проблем.

• [int idx] - връща елемента на позиция idx, все едно ползвате обикновен масив. Сложност O(1)
• .at(int idx) - друг начин за вземане на елемента на позиция idx. Сложност O(1)
• .front() - връща първия елемент от вектора. Сложност O(1)
• .back() - връща последния елемент от вектора. Сложност O(1)
• .push_back(T val) - добавя нов елемент със стойност val в края на вектора. Сложност O(1)
• .pop_back() - премахва последния елемент на вектора. Сложност O(1)
• .insert(iterator pos, T val) - добавя елемента val на позиция pos, измествайки елементите от pos нататък надясно. Сложност O(N)
• .resize(int len) - увеличава или намалява размера на вектора до len. Сложност O(len)
• .resize(int len, T val) - увеличава или намалява размера на вектора до len, като ако го увеличава, новите елементи са със стойност val. Сложност O(len)
• .clear() - изтрива всички елементи от вектора. Сложност O(N)
• .erase(iterator pos) - изтрива елемента на позицията, сочена от pos, измествайки елементите от pos нататък наляво. Сложност O(N)
• .erase(iterator begin, iterator end) - изтрива всички елементи в интервала [begin, end), измествайки елементите от end нататък наляво. Сложност O(N)
• .size() - връща колко елемента има в масива. Сложност O(1)
• .empty() - връща true или false в зависимост дали .size() == 0. Сложност O(1)
• .begin() - връща итератор към началото на елементите. Сложност O(1)
• .end() - връща итератор към края на елементите. Сложност O(1)
• .rbegin() - връща обратен итератор към началото на елементите. Сложност O(1)
• .rend() - връща обратен итератор към края на елементите. Сложност O(1)

string

#include <string>
Това е по-интересна употреба на vector, където типът е предварително зададен (char). С нея могат да се представят стрингове. Логично. Но като цяло има няколко особени предимства пред нормалния char*. Първо, размерът му може да бъде взет с константна сложност чрез метода .size(). Второ, не се нуждае от терминираща нула. Трето, позволява лесно разширяване или смаляване (както при вектор). Четвърто, копирането му е много по-лесно. Пето, предефинирани са няколко допълнителни оператора - например operator <, operator +, operator +=. С тях може да се сравняват и съединяват стрингове сравнително по-лесно, отколкото при char*.

Недостатъците са, че отново, както и при векторите, е малко по-бавен от нормален масив от char-ове. Има допълнителен метод .c_str(), който връща const указател към стринга, за да може да бъде печатан като обикновен C-style стринг. Това става по следния начин:
Методите, които предоставя, са:

• [int idx] - връща символа на позиция idx, все едно ползвате обикновен масив. Сложност O(1)
• .at(int idx) - връща символа на позиция idx. Сложност O(1)
• .find(char symbol) - връща първата позиция (индексирано от нула), на която се среща символът symbol. Ако символът не се среща в стринга, вместо това бива върната константата string::npos, която е число, по-голямо или равно на дължината на стринга или -1.


• .find(string str) - връща първата позиция (индексирано от нула), на която се среща стрингът str. Ако аргументът не се среща в стринга, вместо това бива върната константата string::npos, която е число, по-голямо или равно на дължината на стринга или -1.


• .substr(int start) - връща друг стринг, започващ от start-ия елемент на стринга. Сложност O(N - start)
• .substr(int start, int len) - връща друг стринг, започващ от start-ия елемент на стринга с дължина len. Сложност O(len)


• .c_str() - връща константен указател към C-string (терминиран с 0 char масив), със същото съдържание като стринга. Сложност O(N) (понякога и по-бързо)
• .push_back(char val) - добавя нов символ в края на стринга. Сложност O(1)
• .append(string str) - закача str накрая на стринга. Сложност O(M), където M е дължината на str
• operator +=(string str) - същото като .append(). Сложност O(M), където M е дължината на str
• .insert(iterator pos, string str) - добавя стринга str на позиция pos, измествайки символите от pos нататък надясно. Сложност O(N)
• .resize(int len) - увеличава или намалява размера на стринга до len. Сложност O(len)
• .resize(int len, char val) - увеличава или намалява размера на стринга до len, като ако го увеличава, новите елементи са със стойност val. Сложност O(len)
• .clear() - изтрива всички символи от стринга. Сложност O(N)
• .erase(iterator pos) - изтрива символа на позицията, сочена от pos, измествайки следващите символи наляво. Сложност O(N)
• .erase(iterator begin, iterator end) - изтрива подстринга в интервала [begin, end), измествайки символите от end нататък наляво. Сложност O(N)
• .size() - връща колко елемента има в масива. Сложност O(1)
• .length() - същото като .size(). Сложност O(1)
• .empty() - връща true или false в зависимост дали .size() == 0. Сложност O(1)
• .begin() - връща итератор към началото на стринга. Сложност O(1)
• .end() - връща итератор към края на стринга. Сложност O(1)

deque

#include <queue>
Декът (deque) е опашка, в която можем да добавяме и премахваме елементи както в началото, така и в края. Обикновено за да става това достатъчно бързо е реализирана или чрез лист, или чрез циклична опашка (тоест в динамичен масив).

• [int idx] - връща елемента на позиция idx. Сложност O(1)
• .at(int idx) - друг начин, за вземане на елемента на позиция idx. Сложност O(1)
• .front() - връща елемента в началото на опашката. Сложност O(1)
• .back() - връща елемента в края на опашката. Сложност O(1)
• .push_front(T val) - добавя нов елемент със стойност val в началото на опашката. Сложност O(1)
• .push_back(T val) - добавя нов елемент със стойност val в края на опашката. Сложност O(1)
• .pop_front() - премахва елемент от началото на опашката. Сложност O(1)
• .pop_back() - премахва елемент от края на опашката. Сложност O(1)
• .resize(int len) - увеличава или намалява размера на опашката до len. Ако се налага да се премахват елементи, това става от края на опашката. Сложност O(len)
• .resize(int len, T val) - увеличава или намалява размера на опашката до len, като ако го увеличава, новите елементи са със стойност val. Сложност O(len)
• .clear() - изтрива всички елементи от опашката. Сложност O(N)
• .size() - връща колко елемента има в опашката. Сложност O(1)
• .empty() - връща true или false в зависимост дали опашката е празна. Сложност O(1)
• .begin() - връща итератор към началото на елементите. Сложност O(1)
• .end() - връща итератор към края на елементите. Сложност O(1)

stack

#include <stack>
Поддържа стандартните операции за стек. Стандартната имплементация е реализирана на базата на deque.

• .top() - връща елемента на върха на стека без да го премахва. Сложност O(1)
• .push(T val) - добавя нов елемент със стойност val на върха на стека. Сложност O(1)
• .pop() - премахва елемента, намиращ се на върха на стека. Сложност O(1)
• .size() - връща колко елемента има в стека. Сложност O(1)
• .empty() - връща true или false в зависимост дали стекът е празен или не. Сложност O(1)

queue

#include <queue>
Поддържа стандартните операции за опашка. Стандартната имплементация е реализиран на базата на deque.

• .front() - връща елемента в началото на опашката без да го премахва. Сложност O(1)
• .back() - връща елемента в края на опашката без да го премахва. Сложност O(1)
• .push(T val) - добавя нов елемент със стойност val в края на опашката. Сложност O(1)
• .pop() - премахва елемента, намиращ се в началото на опашката. Сложност O(1)
• .size() - връща колко елемента има в опашката. Сложност O(1)
• .empty() - връща true или false в зависимост дали опашката е празна или не. Сложност O(1)

priority_queue

#include <queue>
Много полезна структура данни, която ще разгледаме подробно в темата приоритетна опашка. В нея можете да добавяте елементи със сложност O(log(N)) и да взимате максималния елемент с O(1). Също така можете да премахвате максималния елемент със сложност O(log(N)). Често можете да я срещнете и като heap в английската литература.

• .top() - връща максималният елемент от приоритетната опашка без да го премахва. Сложност O(1)
• .push(T val) - добавя нов елемент със стойност val в приоритетната опашка. Сложност O(log(N))
• .pop() - премахва максималния елемент от приоритетната опашка. Сложност O(log(N))
• .size() - връща колко елемента има в приоритетната опашка. Сложност O(1)
• .empty() - връща true или false в зависимост дали приоритетната опашка е празна или не. Сложност O(1)

За да работи с дефинирани от вас структури или класове, те трябва да имат предефиниран operator <. Вижте края на темата за повече информация.

set

#include <set>
Подобно на класа, който ние написахме, тази STL-ска имплементация на set също пази множество от елементи. Той, обаче, ползва различна структура на елементите (балансирано двоично дърво), в следствие на което постига по-добри сложности за добавяне, изтриване на елемент, като запазва същата за търсене. За сметка на това не ни дава достъп до k-тия по големина елемент. Все пак тази структура данни си остава много удобна в редица задачи (а е относително сложна, ако искате да имплементирате сами). Всъщност това (заедно с map, който е базиран на същото дърво) е може би най-сложното нещо, имплементирано в STL.

• .find(T val) - връща итератор към елемента със стойност val, или итератора .end(), ако елементът не се намира в множеството. Сложност O(log(N))
• .count(T val) - намира колко на брой елемента със стойност val има в множеството. Тъй като това е множество, а не мултимножество, този брой е винаги или 0, или 1. Сложност O(log(N))
• .lower_bound(T val) - връща итератор към първия елемент от множеството, който е по-голям или равен на val. Сложност O(log(N))
• .upper_bound(T val) - връща итератор към първия елемент от множеството, който е по-голям от val. Сложност O(log(N))
• .insert(T val) - добавя елемент със стойност val, ако такъв вече не съществува. Сложност O(log(N))
• .clear() - изтрива всички елементи от множеството. Сложност O(N)
• .erase(T val) - изтрива елемента със стойност val, ако такъв съществува. Сложност O(log(N))
• .erase(iterator it) - изтрива елемента, сочен от итератора it. Сложност O(log(N))
• .erase(iterator begin, iterator end) - изтрива всички елементи, в интервал, зададен от два итератора. Забележете, че интервалът е полу-затворен: [it1, it2). Сложност O(М), където M е броят изтрити елементи
• .size() - връща колко елемента има в множеството. Сложност O(1)
• .empty() - връща true или false в зависимост дали .size() == 0. Сложност O(1)
• .begin() - връща итератор към началото на елементите. Сложност O(1)
• .end() - връща итератор към края на елементите. Сложност O(1)

Тъй като set изисква наредба на елементите, за да работи с дефинирани от вас структури или класове, те трябва да имат предефинирани operator < (за вкарване) и operator == (за търсене). Вижте края на темата за повече информация.
Ако искате да позволите съществуването на дубликатни стойности, можете да ползвате почти аналогичния multiset.

map

#include <map>
Това е може би най-полезната структура данни в STL след vector. Тя дава асоциативен масив, тоест масив от двойки <key, value>, като по даден ключ (key) ви връща стойност (value). Например в тази структура можете да запишете имената и ЕГН-тата на всички хора в България. Имената (от тип string) ще се ползват за ключ, а ЕГН-тата - за стойност (като string или long long). Така по дадено име структурата данни ще връща ЕГН-то, отговарящо за съответния човек.

Нещо повече, можете да направите обратното, по ЕГН да ви връща името на човека! Така ключът ви ще е long long или string (в зависимост как предпочитате да пазите ЕГН-то), а стойността - string.

Как става това? Отново с два темплейта, както беше при pair - един за ключа и един за стойността. Всъщност map е почти същото нещо, като set, чиито елементи са pair<K, T>. Типовете K и T може да са както различни, така и еднакви.


Ако забелязвате, тази структура данни надгражда нещата, които ни даваше set и донякъде обезмисля ползването му. Все пак ви препоръчваме да ползвате set, когато ви трябва множество, и map, когато ви трябва асоциативен масив.

• [K key] - връща стойността, съответстваща на ключа key. Ако такава стойност няма, то не е дефинирано какво точно се случва, затова винаги, когато не сте абсолютно сигурни, че елемент с даден ключ присъства в асоциативния масив, проверявайте с .count(key) или .find(key) != .end() дали това е така. Това е и стандартният начин да присвоявате стойности - например q[“Alexander”] = 42; (където q е асоциативен масив от тип <string, int>) би присвоило стойност 42 на елемента с ключ "Alexander", или би създало такъв, ако все още не съществува. Сложност O(log(N))
• .find(T val) - връща итератор към елемента с ключ val, или итератора .end(), ако няма елемент с такъв ключ. Сложност O(log(N))
• .count(T val) - намира колко на брой елемента с ключ val има в асоциативния масив. Тъй като не са разрешени повтарящи се ключове, този брой е винаги или 0, или 1. Сложност O(log(N))
• .lower_bound(T val) - връща итератор към първия елемент от асоциативния масив, чиито ключ е по-голям или равен на val. Сложност O(log(N))
• .upper_bound(T val) - връща итератор към първия елемент от асоциативния масив, който е по-голям от val. Сложност O(log(N))
• .insert(pair<K key, T val>) - добавя елемент с ключ key и стойност val, ако не съществува елемент с такъв ключ. Ако такъв елемент вече съществува, то стойността му бива променена на val. Сложност O(log(N))
• .clear() - изтрива всички елементи от асоциативния масив. Сложност O(N)
• .erase(T val) - изтрива елемента с ключ val, ако такъв съществува. Сложност O(log(N))
• .erase(iterator it) - изтрива елемента, сочен от итератора it. Сложност O(log(N))
• .erase(iterator begin, iterator end) - изтрива всички елементи, в интервал, зададен от два итератора. Забележете, че интервалът е полу-затворен: [it1, it2). Сложност O(М), където M е броят изтрити елементи
• .size() - връща колко елемента има в множеството. Сложност O(1)
• .empty() - връща true или false в зависимост дали .size() == 0. Сложност O(1)
• .begin() - връща итератор към началото на елементите. Сложност O(1)
• .end() - връща итератор към края на елементите. Сложност O(1)

Тъй като map изисква наредба на ключовете (тоест K), за да работи с дефинирани от вас структури или класове, те трябва да имат предефинирани operator < (за вкарване) и operator == (за търсене). Вижте края на темата за повече информация.
Това изискване, както при set, така и при map възниква поради факта, че елементите се държат в сортиран вид през цялото време. А за да сортираме елементи, то трябва те да са сравними. Забележете, че стойността (тоест T) може да е от произволен тип и няма изискване да е сравнима.
Ако искате да позволите съществуването на дубликатни стойности, можете да ползвате почти аналогичния multimap.

Итериране на set и map

Да обходите елементите на set или map не е едно от най-лесните неща. Има сравнително лесен workaround, ако не целите скорост и имате памет. Прехвърляте елементите на set-а или map-а във вектор и обхождате вектора. Това става по следния начин: Алтернативно, можете да ползвате малко по-сложния, но директен начин за обхождане на set или map. Както ще забележите, неговия синтаксис не е много интуитивен:

Алгоритми

#include <algorithm>
Всъщност освен няколкото по-сложни алгоритъма (като, например, сортиране), остатъка от STL-ските "алгоритми" са няколкоредови рутинни парчета код (като търсене на елемент, броене, сумиране и т.н.). Съветваме ви да погледнете пълния списък ето тук и да разгледате тези от тях, които смятате, че ще ви бъдат полезни. Тук ще покажем само някои от тях - и без друго информацията не е много различна от тази, която ще намерите в стандартната документация.

min

min(T a, T b)
Връща минимума на два елемента от еднакъв тип T. Би върнало 42 за min(42, 666), 13 за min(13, 13) и -2 за min(1, -2). Би дало грешка при компилация за min(42, 13.0).

max

max(T a, T b)
Връща максимума на два елемента от еднакъв тип T. Би върнало 666 за max(42, 666), 13 за max(13, 13) и 1 за max(1, -2). Би дало грешка при компилация за max(42, 13.0).

swap

swap(T a, T b)
Разменя местата на елементите a и b. Тази толкова проста функцийка е много удобна, тъй като ако искаме сами да разменим два елемента, ще ни трябва допълнителна променлива и (общо) три реда код. Чрез swap(a, b) много по-ясно си личи какво искаме да направим. Елементите се подават по референция, като така не се копират при викане на функцията (вътре във функцията, обаче, се копират при разменянето им, което няма как да се избегне).

sort

sort(итератор_към_началото, итератор_към_края)
И тъй като изобщо не искаме да ви занимаваме с това какво е итератор, то можете да си го представяте, че е просто указател. Тази представа всъщност е много близо до истината, тъй като можете да сортирате обикновен масив с числа (или обекти с дефиниран operator <) с подаване на указател към началото на масива и указател към позицията след последния елемент от интервала, който искате да сортирате. Забележете, че двата указателя задават полу-отворен интервал [begin, end). С други думи, за да сортирате масив с обекти от тип Student, за който сме дефинирали operator <, правим следното:
До тук добре. Сега да видим как можем да сортираме някои от другите структури данни, които вече разгледахме. Всъщност сортирането има смисъл само за някои от тях - например би било нелогично да сортираме опашка или стек. Свързан списък не можем да сортираме, тъй като липсва условието да имаме произволен достъп до елементите. Сетът вече е сортиран (както и STL-ския такъв). Остана динамичен масив, сиреч vector.

В нашата имплементация имаме достъп до масива и броя елементи, та лесно можем да ползваме стандартното сортиране на масиви. В STL-ския вектор, обаче, не можем да направим това. За щастие, при него са дадени два метода, които ни връщат точно тези итератори - те са .begin() и .end(). Лесно, нали? Така за да сортираме вектор от елементи с тип Student (ползваме същата структура от предходния пример) правим:

reverse

reverse(итератор_към_началото, итератор_към_края)

?	Дребен трик: ако искате да сортирате vector в обратен на стандартния ред, вместо да викате sort() и после reverse(), можете да извикате sort() с така наречените reverse iterators: sort(vectorName.rbegin(), vectorName.rend()), което би свършило именно това.

Обръща интервал наобратно. Ако е съдържал числата (7, 4, 42, 13, 666), то след извикването му ще бъде (666, 13, 42, 4, 7). Много хора го ползват веднага след сортиране - ако искат елементите да са сортирани в обратен ред.

Забележете, че аргументите отново са итератори, указващи интервал. Всъщност доста от алгоритмите в STL имат подобна сигнатура - както ще видим, следващите няколко отново са такива.

random_shuffle

random_shuffle(итератор_към_началото, итератор_към_края)
Прави произволно разбъркване на елементите. Удобно, когато искате да направите тест за някоя задача или пишете рандомизиран алгоритъм.

next_permutation

bool next_permutation(итератор_към_началото, итератор_към_края)
Преподрежда елементите в интервала в следващата лексикографска пермутация. Например след извикване върху (4, 1, 3, 2) ще получим (4, 2, 1, 3). Връща false, ако текущата пермутация е последната възможна.

Удобно е когато имаме задача, в която искаме да пробваме всички възможни пермутации (тоест някакъв тип изчерпващо решение). Забележете, че ако исакте да направите всички пермутации, то първоначално трябва поредицата да е сортирана, иначе бихте пропуснали всички пермутации преди началната.
Ето код, който намира и изпечатва всички възможни (различни) пермутации на числата {1, 3, 3, 7}.
Резултатът от изпълнението е:

nth_element

void nth_element(итератор_към_началото, итератор_към_позицията, итератор_към_края)
Слага на дадена позиция елемента, който би бил на тази позиция ако целият масив е сортиран. Полезно е най-често за намиране на медиана. Времето за работа в средния случай е O(N).
Например, ако имаме числата {101, 13, 17, 1337, 666, 42, 10, 69} и вземем nth_element с аргумент n = 4, функцията би подредила числата по такъв начин, че на позиция 4 да е елементът 69: елементът на позиция 4 от сортирания вариант на масива (10, 13, 17, 42, 69, 101, 666, 1337).

Как изглежда ако го ползваме с масиви: Или пък с вектори:

operator < и operator ==

Както споменахме по-горе, за някои от структурите данни (set, map, priority_queue, ...) а също така за някои от алгоритмите (sort(), next_permutation(), min(), max()) е нужно елементите на множеството, с което работим, да са сравними -- тоест при наличието на два от тях A и B да можем да кажем дали A < B, A > B или A == B. Работейки със стандартни типове (int, double, ...), а както и с типове от STL (string, set, etc.) това е тривиално, тъй като операторите за сравнение са дефинирани. Ако искаме да ползваме наша собствена структура, обаче, трябва да извършим малко допълнителна работа.

?	Дефинирането на operator < ви дава свобода лесно да постигнете "обратна" наредба на елементите. Примерно, ако в структурата имате едно единствено число value, то тялото на оператора може да бъде return value > other.value;, като така при сортиране елементите ще бъдат сортирани в намаляващ ред.

За наше щастие, това става сравнително просто и не ни пречи да го пишем по време на състезание (изисква едва 2-3 реда). Вътре в структурата (или класа) трябва да имаме метод със сигнатура bool operator < (const T& other) const;, където T е името на структурата или класа, който пишем, a other е просто име на променлива, което може да е всякакво. Например, ако правим клас за точки с целочислени координати в тримерното пространство, това би било: В случая наредбата на точките би била първо по x, при равен x - по y, и при равен x и y по z.

Допълнителни материали

1. Стандартна библиотека, част II (www.informatika.bg)
2. Standard Template Library (en.wikipedia.org)
3. Структури данни в STL (www.cplusplus.com)
4. Алгоритми в STL (www.cplusplus.com)
5. Друга документация на STL - вече не се поддържа (www.sgi.com)

предишна тема

версия за печат

следваща тема