Категорія: STL

Купу в 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

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

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

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

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

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

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

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

count/count_if

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

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

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

fill/fill_n

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

find/find_if

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

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

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

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

generate/generate_n

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

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

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

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

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

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)

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

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

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

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_element/min_element

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

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

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 }

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

 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

Для відсортованої послідовності генерує всі можливі комбінації усих її елементів. Повертає 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

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

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

Послідовність не буде відсортованою, вона лише буде містити менші елементи в одній частині і більші в іншій. Також дивись 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

Аналогічно 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

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

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

Перевпорядковує елементи у вказаному диапазоні таким чином що елементи для яких предикат є істинним розміщуються перед елементами для яких предікат є 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

Генерує попередню комбінацію перестановок для вказаної послідовності. У випадку якщо такої не існує повертає 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

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

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

Також див. 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_if.

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

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

 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_if.

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

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

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

Переміщує елементи у вказаному диапазоні в кінець контейнера. При цьому останній елемент диапазону стає першим у коллекції. Також див. 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    char s[] = "Mississippi";
    size_t size = strlen(s);

    auto it = unique(s, s + size);
    cout << s << endl;
    cout << it << endl;
    
    // Misisipippi
    // ppi

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

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