Купу в STL реалізовано за принципом max-heap. При такій організації ключ елемента більше або дорівнює ключам дочірніх елементів. Завдяки цьому перший елемент купи є найбільшим елементом. При цьому дочірні елементи не мають бути відсортованими відносно одне одного.

Функції для роботи з купою (алгоритми)

Усі алгоритми очикують правильно організовану купу в якості параметрів. Список і іноді масив не можуть бути використаними оскільки перелічені алгоритми вимагають випадкового доступу до елементів та зміни розміру купи.

make_heap

Створює купу з вказаної послідовності на місці. Можна вказати власну функцію порівняння.

pop_heap

Перевпорядковує купу переміщуючи найбільший (перший) елемент в кінець. Доступ до елемента можна отримати за допомогою back(), вилучити елемент можна за допомогою pop_back().

push_heap

Перевпорядковує купу розміщуючи останній елемент, який повинно бути додано в останню позицію попередньо.

sort_heap

Сортує купу. Після сортування купа стає не валідною.

Приклад використання алгоритмів

int a[] = {12, 9, 8, 4, 6, 7, 5, 0, -1, 2, 3 }; size_t size = sizeof(a) / sizeof(a[0]); vector<int> v(a, a + size); make_heap(a, a + size); copy(a, a + size, ostream_iterator<int>(cout, " ")); cout << endl; // 12 9 8 4 6 7 5 0 -1 2 3 sort_heap(a, a + size); copy(a, a + size, ostream_iterator<int>(cout, " ")); cout << endl; // -1 0 2 3 4 5 6 7 8 9 12 make_heap(v.begin(), v.end()); v.push_back(10); push_heap(v.begin(), v.end()); copy(v.begin(), v.end(), ostream_iterator<int>(cout, " ")); cout << endl; // 12 9 10 4 6 8 5 0 -1 2 3 7 pop_heap(v.begin(), v.end()); copy(v.begin(), v.end(), ostream_iterator<int>(cout, " ")); cout << endl; // 10 9 8 4 6 7 5 0 -1 2 3 12

accumulate

Сумує значення елементів у послідовності з початковим значенням. Можна використовувати довільну бінарну операцію замість додавання.

adjacent_difference

Створює нову послідовність де кожен елемент крім першого містить різницю між поточним та попереднім елементами. Можна використовувати довільну бінарну операцію.

1 int a[] = {1, 1, 2, 3, 5, 8}; 2 list<int> result(sizeof(a) / sizeof(a[0])); 3 adjacent_difference(&a[0], &a[6], result.begin(), times<int>()); 4 copy(result.begin(), result.end(), ostream_iterator<int>(cout, " ")); 5 // 1 1 2 6 15 40

adjacent_find

Шукає першу пару елементів що дорівнюють одне одному. Можна використовувати довільний предікат.

binary_search

Бінарний пошук значення у послідовності. Можна використовувати довільну функцію порівняння.

copy

Копіює послідовність.

copy_backward

Копіює послідовність у зворотньому порядку.

count/count_if

Обчислює кількість вказаних значень у послідовності. Дозволяє вказати предікат.

equal

Порівнює дві послідовності, можна використовувати власний предікат.

equal_range

Повертає пару ітераторів для послідовності, перший аналогічний тому що поверне lower_bound, другий – upper_bound. Можна вказати предікат для порівняння.

fill/fill_n

Копіює значення у всі елементи послідовності.

find/find_if

Шукає значення у послідовності. Дозволяє вказати предікат для пошуку.

find_end

Шукає в першій послідовності останнє входження другої послідовності. Можна вказати власний предікат.

find_first_of

Шукає в першій послідовності перше входження будь-якого елементу з другої послідовності. Можна вказувати власний предікат.

for_each

Застосовує функцію до кожного елемента послідовності.

generate/generate_n

Заповнює послідовність результатом функції.

includes

Визначає чи містять елементи першої послідовності всі елементи другої послідовності. По замовчанню вважає що елементи відсортовані за зростанням, може бути використана довільна функція порівняння.

inner_product

Акамулює суму добутків двох послідовностей. Може бути використана довільна функція для пар значень та їх акумулювання.

1 int a1[] = {2, 3, 5, 8}; 2 int a2[] = {1, 2, 3, 4}; 3 int res = inner_product(&a1[0], &a1[4], &a2[0], 0, minus<int>(), plus<int>()); 4 // res = 0 - (2 + 1) - (3 + 2) - (5 + 3) - (8 + 4) == -28

inplace_merge

Зливає дві відсортовані послідовності елементів в одну. Можна вказати функцію порівняння.

1 int a[] = 2 { 3 9, 7, 5, 3, 1, 4 10, 8, 6, 4, 2 5 }; 6 7 inplace_merge(a, a + 5, a + 10, greater<int>()); 8 // a[] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1)

iter_swap

Обмінює значеннями елементи на які вказують ітератори.

lexicorgaphical_compare

Порівнює пари елементів з двох послідовностей доки не буде знайдено не рівні елементи, або одна з послідовностей не скінчиться. Повертає значення яке вказує чи перша послідовність лексиграфічно менша за другу. Можна вказати функцію порівняння.

lower_bound

Повертає ітератор на першу позицію у відсортованій послідовності в яку може бути вставлене вказане значення без порушення відсортованості. Можна вказати функцію порівняння.

1 int a[] = { 0, 2, 4, 6 }; 2 int *p = lower_bound(a, a + 4, 3); 3 // *p == 4 4 int *p = lower_bound(a, a + 4, 4); 5 // *p == 4

max/min

Повертає максимальний/мінімальний з двох елементів. Можна вказати функцію порівняння.

max_element/min_element

Повертає максимальний/мінімальний елемент послідовності. Можна вказати функцію порівняння.

merge

Комбінує дві відсортовані послідовності і розміщує їх в третю послідовніть. Повертає ітератор що вказає на елемент за останнім вставленим. Можна вказати функцію порівняння.

1 int a1[] = { 0, 2, 4, 6 }; 2 int a2[] = { 1, 3, 7 }; 3 int ar[7]; 4 5 merge(a1, a1 + 4, a2, a2 + 3, ar) 6 //ar[] = { 0, 1, 2, 3, 4, 6, 7 }

mismatch

Порівнює елементи двох послідовностей і повертає пару ітераторів на перші позиції в яких елементи не співпадають. Якщо в другій послідовності більше елементів то вони ігноруються. Якщо в першій послідовності більше елементів то поведінка не визначена. Можна вказати предикат порівняння.

1 struct e 2 { 3 bool operator()(int i1, int i2) 4 { 5 return i1 >= i2; 6 } 7 }; 8 9 int a1[] = { 0, 1, 4, 5, 8 }; 10 int a2[] = { 0, 1, 3, 7 }; 11 pair<int*, int*> p = mismatch(a1, a1 + 5, a2); 12 // *p.first == 4, *p.second == 3 13 14 p = mismatch(a1, a1 + 5, a2, e()); 15 // *p.first == 5, *p.second == 7

next_permutation

Для відсортованої послідовності генерує всі можливі комбінації усих її елементів. Повертає false якщо комбінацій більше не залишилося. Можна вказати функцію порівняння для елементів.

1 int a[] = { 1, 2, 3 }; 2 3 do 4 { 5 for_each(a, a + 3, [i] { cout << i << 't'; }); 6 cout << endl; 7 } 8 while (next_permutation(a, a + 3)); 9 // 1 2 3 10 // 1 3 2 11 // 2 1 3 12 // 2 3 1 13 // 3 1 2 14 // 3 2 1

nth_element

Перевпорядковує послідовність таким чином що всі її елементи менші за вказаний розміщуються перед ним, а більші – після нього.

partial_sort

Частково сортує частину послідовності відносно вказаного елемента. Менші за значенням елементи розміщуються зліва, більші зправа. Можна вказати метод порівняння.

Послідовність не буде відсортованою, вона лише буде містити менші елементи в одній частині і більші в іншій. Також дивись stable_sort, partial_sort_copy.

1 int ia[] = {29, 23, 20, 22, 17, 15, 26, 51, 19, 12, 35, 40 }; 2 partial_sort(ia, ia +5, ia + 12); 3 // 12 15 17 19 20 29 26 51 23 22 35 40

partia_sort_copy

Аналогічно partial_sort частково сортує послідовність, але результат копіює у вказаний контейнер. Причому скопійована послідовність є відсортованою.

1 int a1[] = {29, 23, 20, 22, 17, 15, 26, 51, 19, 12, 35, 40 }; 2 int a2[5]; 3 partial_sort_copy(a1, a1 + 7, a2, a2 + 5, greater<int>()); 4 // 29 26 23 22 20

partial_sum

Створює послідовність в якій кожний елемент є сумою усих попередніх. Можна вказати бінарний оператор.

1 int a1[] = { 1, 2, 3, 4, 5 }; 2 const int size = sizeof(a1) / sizeof(a1[0]); 3 int a2[size] = { 0 }; 4 partial_sum(a1, a1 + size, a2); 5 // a2[] = 1 3 6 10 15

partition

Перевпорядковує елементи у вказаному диапазоні таким чином що елементи для яких предикат є істинним розміщуються перед елементами для яких предікат є false. Також див. stable_partition.

1 struct even 2 { 3 bool operator()(int i) { return i % 2 == 0; } 4 }; 5 int a[] = { 1, 2, 3, 4, 5, 11, 13, 22, 18 }; 6 const int size = sizeof(a) / sizeof(a[0]); 7 partition(a, a + size, even()); 8 copy(a, a + size, ostream_iterator<int>(cout, " ")); 9 // a[] = 18 2 22 4 5 11 13 3 1

prev_permutation

Генерує попередню комбінацію перестановок для вказаної послідовності. У випадку якщо такої не існує повертає false. Можна вказати власну версію оператора порівняння елементів.

1 char a[] = { 'c', 'a', 'b' }; 2 int size = sizeof(a); 3 do { 4 copy(a, a + size, ostream_iterator<char>(cout, " ")); 5 cout << endl; 6 } while (prev_permutation(a, a + size)); 7 8 c a b 9 b c a 10 b a c 11 a c b 12 a b c

random_shuffle

Переставляє елементи у диапазоні випадковим чином. Можна вказати власний генератор випадкових чисел (повинен повертати значення у диапазоні [0,1]).

remove

Вилучає всі елементизі вказаним значенням у вказаному диапазоні. Елементи не прибираються з послідовності, натомість вони розміщуєьться в кінці послідовності. Повертає ітератор на перший елемент з тих що треба вилучити.

Також див. remove_if.

1 int a[] = { 0, 1, 0, 2, 0, 3, 0, 4 }; 2 size_t size = sizeof(a) / sizeof(a[0]); 3 remove(a, a + size, 0); 4 copy(a, a + size, ostream_iterator<int>(cout, " ")); 5 // 1 2 3 4 0 3 0 4

remove_copy

Копіює всі елементи що не дорівнюють вказаному значенню у вказаний контейнер. Повертає ітератор на останній скопійований елемент. Оригінальний контейнер не змінюється. Також див. remove_copy_if.

remove_if

Вилучає всі елементи у вказаному диапазоні дял яких є істиним вказаний предикат. Елементи не прибираються з послідовності, натомість вони розміщуєьться в кінці послідовності. Повертає ітератор на перший елемент з тих що треба вилучити. Також див. remove.

remove_copy_if

Копіює всі елементи що не задовольняють предикату у вказаний контейнер. Повертає ітератор на останній скопійований елемент. Оригінальний контейнер не змінюється.

1 struct Even 2 { 3 bool operator()(int x) { return x % 2 != 0; } 4 }; 5 6 int a[] = { 0, 1, 2, 3, 4, 5, 6 }; 7 size_t size = sizeof(a) / sizeof(a[0]); 8 9 vector<int> v(size); 10 auto it = remove_copy_if(a, a + size, v.begin(), Even()); 11 copy(v.begin(), it, ostream_iterator<int>(cout, " "));

Також див. remove_copy.

replace

Замінює всі елементи зі вказаним значенням на нове значення.

replace_copy

На відміну від replace вствляє нові значення в інший контейнер. Повертає ітератор на останній вставлений елемент. Оригінальний контейнер не змінюється.

replace_if

Замінює елементи у вказаному диапазоні для яких є істиним вказаний предикат новим значенням. Також див. replace_copy_if.

replace_copy_if

Працює аналогічно до replace_if, але нові значення вставляються в інший контейнер. Повертає ітератор на останній скопійований елемент. Оригінальний контейнер не змінюється.

reverse

Обертає послідовність ементів у контейнері. Також див. reverse_copy.

reverse_copy

Працює аналогічно до reverse, але нова послідовність копіюється в інший контейнер. Повертає ітератор на останній скопійований елемент. Оригінальний контейнер не змінюється.

rotate

Переміщує елементи у вказаному диапазоні в кінець контейнера. При цьому останній елемент диапазону стає першим у коллекції. Також див. rotate_copy.

rotate_copy

Працює аналогічно до rotate, але нова послідовність копіюється в інший контейнер. Повертає ітератор на останній скопійований елемент. Оригінальний контейнер не змінюється.

1 int a[] = {1, 2, 3, 4, 5, 6, 7 }; 2 size_t size = sizeof(a) / sizeof(a[0]); 3 4 vector<int> v(size); 5 rotate_copy(a, a + size / 2, a + size, v.begin()); 6 copy(v.begin(), v.end(), ostream_iterator<int>(cout, " ")); 7 // 4 5 6 7 1 2 3

search

Для двох вказаних диапазонів повертає ітератор на перше входження другого диапазона у перший як його підпослідовності, або ітератор на останній елемент першої послідовності якщо входження не знайдено. Можна вказати власниу предикат порівняння.

1 char str[] = "aababcdabcde"; 2 vector<char> v(3); 3 v[0] = 'a'; v[1] = 'b'; v[2] = 'c'; 4 copy(search(str, str + strlen(str), v.begin(), v.end()), 5 str + strlen(str), 6 ostream_iterator<char>(cout)); 7 // abcdabcde

search_n

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

1 char *s = "abbcccdddd"; 2 size_t size = strlen(s); 3 cout << search_n(s, s + size, 2, 'c'); 4 // cccdddd

set_difference

Конструює відсортовану послідовність елементів присутніх у першій колекції, але відсутніх у другій. Повертає ітератор на останній скопійований елемент. Можна вказати власну функцію порівняння. Також див. set_intersecton, set_symmetric_difference та set_union.

set_intersection

Конструює відсортовану послідовність з елементів присутніх у двох вказаних послідовностях. Елементи копіюються з першої послідовності. Повертає ітератор на останній скопійований елемент. Можна вказати власну функцію порівняння. Також див. set_difference, set_symmetric_difference та set_union.

set_symmetric_difference

Конструює відсортовану послідовність з елементів присутніх у першому контейнері і відсутніх у другому та елементів відсутніх у першому контейнері і присутніх у другому. Повертає ітератор на останній скопійований елемент. Можна вказати власну функцію порівняння. Також див. set_difference, set_intersection та set_union.

set_union

Конструює відсортовану послідовність елементів з двох контейнерів. Якщо елемент присутній в обох контейнерах то він копіюється лише з першого. Повертає ітератор на останній скопійований елемент. Можна вказати власну функцію порівняння. Також див. set_difference, set_intersection та set_symmetric_difference.

int a1[] = { 1, 2, 3, 4 }; size_t a1_size = sizeof(a1) / sizeof(a1[0]); int a2[] = { 1, 10, 100 }; size_t a2_size = sizeof(a2) / sizeof(a2[0]); set<int> res; set_union(a1, a1 + a1_size, a2, a2 + a2_size, inserter(res, res.begin())); cout << "set_union: "; copy(res.begin(), res.end(), ostream_iterator<int>(cout, " ")); res.clear(); set_intersection(a1, a1 + a1_size, a2, a2 + a2_size, inserter(res, res.begin())); cout << "nset_intersection: "; copy(res.begin(), res.end(), ostream_iterator<int>(cout, " ")); res.clear(); set_difference(a1, a1 + a1_size, a2, a2 + a2_size, inserter(res, res.begin())); cout << "nset_difference: "; copy(res.begin(), res.end(), ostream_iterator<int>(cout, " ")); res.clear(); set_symmetric_difference(a1, a1 + a1_size, a2, a2 + a2_size, inserter(res, res.begin())); cout << "nset_symmetric_difference: "; copy(res.begin(), res.end(), ostream_iterator<int>(cout, " ")); // set_union: 1 2 3 4 10 100 // set_intersection: 1 // set_difference: 2 3 4 // set_symmetric_difference: 2 3 4 10 100

sort

Перевпорядковує елементи послідовності за збільшенням. Можна вказати власну функцію порівняння.

stable_partition

Поведінка подібна до partition, але з гарантією збереження відносного порядку елементів у контейнері.

stable_sort

Перевпорядковує елементи контейнера зберігаючи порядок еквівалентних елементів. Можна вказати власну функцію порівняння.

swap

Обмінює значення у двох елементів.

swap_range

Обмінює значення елементів двох послідовностей. Якщо послідовності перетинаються то поведінку не визначено. Повертає ітератор на останній модифікований елемент другої послідовності.

transform

Генерує послідовність за допомогою виклику вказаного унарного оператора для кожного елемента вхідної послідовності.

Є версія для двох послідовностей і бінарного оператору. Якщо послідовності перетинаються то поведінку не визначено.

Повертає ітератор на елемент за останнім вставленим у результуючу послідовність.

int a[] = { 1, 2, 3, 4, 10 }; size_t size = sizeof(a) / sizeof(a[0]); vector<int> res(size); transform(a, a + size, res.begin(), [] (int n) { return n * n + n; }); copy(res.begin(), res.end(), ostream_iterator<int>(cout, " ")); // 2 6 12 20 110

unique

Вилучає дублікати для підряд ідучих елементів послідовності. Можна вказати власну функцію порівняння елементів. Елементи-дублікати поміщуються в кінець послідовності і функція повертає ітератор на перший з них.

char s[] = "Mississippi"; size_t size = strlen(s); auto it = unique(s, s + size); cout << s << endl; cout << it << endl; // Misisipippi // ppi

unique_copy

Копіює олдин екземпляр з кожної групи підряд ідучих елементів з однаковим значенням. Можна вказати власну функцію порівняння.

upper_bound

Повертає ітератор на останню позицію у відсортованій послідовностів яку вказане значення можна вставити без порушення відсортованості. Можна вказати функцію порівняння елементів. Див. також lower_bound.