Короткий звіт про тиждень що я його провів на зльоті представників комітету зі стандартизації С++, розробників компіляторів та бібліотек, розробників що займаються оптимізацією коду та “промислових” представників галузі: розробників ігор, дослідників ведучих наукових закладів та представники найвідоміших компаній.

Усього було присутньо більше 600 людей. Щодня сесії на різні теми починалися 0 9 ранку, закінчувалися о 6 вечора з 2-годинною перервою на обід. О 8 вечора починалися воркшопи (класи) де можна було поговорити скажімо з авторами бібліотек boost, представниками комітету зі стандартизації С++ або іншими видатними людьми. Паралельно доповіді тривалістю в 1-1.5 години читалися у шести аудиторіях проіменаваних на честь видатних вчених: Паскаль, Ньютон, Ферма, Лейбніц, Декарт та Ейлер.

Цього року більшість доповідей було присвячено паралельному програмуванню (~80%) на відміну від попередніх років коли акцент робився на метапрограмування (шаблони).

Багато також говорили про новий стандарт С++14 в який увійде все те що було недороблено в С++11. А вже в С++17 буде багато нових змін які будуть підкориговані в С++20.

Ну і декілька речей які особисто мені запам’яталися.

Всюди auto

Сучасна рекомендація полягає в тому щоб використовувати auto де тільки можна. І суть в тому що це не лише коротший запис, але і безпечніший: скажімо при зміні типів в алгоритмах/інтерфейсах/структурах данних на відбувається прихованого приведення типів. Тому замість

for (list:const_iterator it = l.begin(); it != l.end(); ++it) {...use(*it);...}

В С++11 можна (і треба) писати

for (const auto& i: l) {...use(i);...}

А в С++14 стане можливим навіть

for (i: l) {...use(i);...}

Але авто-виведення корисне не лише для циклів та ітераторів, але і для лямбд, які за новим стандартом можуть повертати лямбди як результат:

auto plus = [](auto x){ retur [](auto y){ return x + y; } };
auto plus4 = plus(4);

auto s6 = plus4(2);
auto s10 = plus(4)(6);

Правила виведення типів

Через додання авто-виведення типів в мову довелося додати правила за якими це виведення відбувається. Усього цих правил більше 10 зараз і тим хто розробляє бібліотеки треба їх усі знати і розуміти дуже добре. І в цілому тенденція така що мова для тих хто пише біблітетеки мова стає складнішою і дозволяє робити тонкіші речі, а для тих хто користується бібліотеками мова навпаки стає простішою.

Так от для виведення типів треба враховавати що діють правила як для шаблонів, а для шаблонів тип шаблону залежить від параметрів методів. Крім того авто-типи втрачають константніть/волатильність. Ну і для типів-значень правила виведення завдяки слайсінгу складніші ніж для вказівників та посилань.

Нові рекомендації для програмістів:

  • для обов’язкових параметрів які не будуть змінюватися використовувати const &
  • для обов’язкових параметрів які будуть змінюватися використовувати &
  • для необов’язкових параметрів використовувати *
  • для оптимізаційних трюків і передачі прав володіння використовувати && та  std::move(). Але при цьому важливо на 100% розуміти що робиш бо такий код майже гарантовано вбиває всю оптимізацію яку міг би зробити компілятор.

 

Ніяких new/delete

Залиште new/delete людям які пишуть біблітотеки та аллокатори, почніть використовувати unique_ptr/shared_ptr. І не забувайте що unique_ptr є фактично безкоштовним і фактично це голий вказівник, але безпечний! А shared_ptr використовуйте коли у об’єкта може бути лише один власник.

Наприклад замість

widget* f();

void n(){
  widget* w = f();
  gadget* g = new gadget();
  use(*w, *g);
  delete g;
  delete w;
}

Треба писати

unique_ptr<widget> f();
void n(){
  auto w = f();
  auto g = make_unique>gadget>();
  use(*w, *g);
}

Небезпечний код

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

У короткому підсумку код

 

do_something();

cleanup();

Не є небезпечним через те що в ньому ніяк не перехоплюються та не оброблюються виключення і не даються гарантії що алоковані ресурси буде звільнено у правильному порядку. Із застосуванням методіки RAII (Resource Acquisition Is Initialization) небезпечний код має виглядати так:

do_something();

Досягається це дотриманням простих правил:

  • конструктор ніколи не кидає виключення та не викликає код який може кинути виключення само собою
  • так само і деструктор ніколи не кидає виключення
  • оператор присвоєння ніколи не кидає виключення і має бути транзакційним. Досягається це створенням тимчасового об’єкту який і ініціалізують як копію, а потім просто замінюють, щось типу такого:
class A {
  A& operator=(const A& a)
  {
    A tmp(a);
    using std::swap;
    swap(tmp);
    return *this;
}

До речі звернічть увагу що swap рекомендується використовувати саме так і не викликати std::swap() на випадок якщо swap() перевантажено для типу.

Ну і взагалі там неймовірно багато усього було. Наприклад розбір того чому код

f(shared_ptr(new A()), shared_ptr(new B());
}

є небезпечним. Ось тут https://github.com/CppCon/CppCon2014/blob/master/Presentations/Exception-Safe%20Code/Exception-Safe%20Code%20-%20Jon%20Kalb%20-%20CppCon%202014.pdf?raw=true файл з усіма слайдами з цієї доповіді.

С++ на Марсі

Виступав ведучий програміст проекту Куріосіті (http://mars.jpl.nasa.gov/msl/) і розповідав в основному те як працює система руху цієї машини. Той С++ що вони там використовують це дуже порізана мова: нема шаблонів, виключень, потоків, множинного успадкування, перевантаження операторів, тощо.

У них там кожна підсистема незалежна і продубльована. Наприклад система руху на останньому марсоході побудувана на платі з процесором PowerPC RAD750 (133 MHz), має 128 Мб пам’яті, використовує ОС VxWorks. В цій ОС є пакетна обробка задач і розділена пам’ять, тому вони написали свій менеджер пам’яті.

Взагалі цікаво що 4 з 19 камер марсоходу належать системі руху (по 2 на кожен комп’ютер) і використовуються майже як людина використовує очі. Максимальна швидкість складає 1.5 см на секунду, але після цього треба зупинитися, зробити стерео-фото двома камерами, розбити катринку на сітку врахувавши перспективу і оцінити кожну клітинку після чого вибрати оптимальний/найнебезпечніший маршрут. Прикол ще в тому що колеса можуть або крутитися, або повертати, одночасно і те і інше не можливо робити. За день марсохід може зробити максимум 100 метрів.

Прикольні баги там у них. Наприклад коли машинці довірили самостійно проїхати кілька десятків метрів вона зупинилася і відмовилася їхати далі тільки коли прокручування (сковзання) колес перевищило допустимий показник. З’ясувалося що заїхали в пісчану дюну і наступні 2 місяці витратили щоб вручну вивести машину з ловушки (так, кожну команду відсилали на Марс окремо). Тобто за 2 місяці щоденної роботи проїхали назад 20 метрів.

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

 

С++ в іграх

Представники галузі говорили в основному про оптимізацію коду і на кожен слайд з С++ кодом у них було по 3-5 слайдів з асемблером. Всякі хитрі трюки оптимізації що вимагають знання принципів роботи заліза і таке інше.

Але ось вам кілька цікавих фактів: в коді Assassin’s Creed 6.5 мільйонів (!) рядків коду на С++ самої гри плюс 9 мільйонів рядків С++ інструментів (це різні редактори, пакувальники і таке інше) та 5 мільйонів рядків на С#. При цьому в коді гри нема RTTI, виключень, шаблонів (ні STL, ні boost).

 

Кілька нових фіч

Це все або ось-ось з’явиться, або вже підтримується деякими компіляторами (читайте у вікіпедії подробиці):

  • constexpr  дозволяють писати код який виконується в процесі компіляції.
  • бар’єри пам’яті (дуже складна тема сама по собі) неймовірно спрощують написання програм у паралельному стилі і є набагато дешевшими за синхронізацію: lock_guard, conditional_variable, atomic, compare_exchange_weak/compare_exchange_strong. Про це все треба читати, воно не те щоб складне, але треба якісь приклади писати для пояснення.
  • atomic<T> можна буде використовувати для shared_ptr. Звучить це як щось звичайне, але насправді така підтримка дозволить уникнути багатьох проблем у реалізації lock-free алгоритмів та значно скоротити і спростити код.
  • обмеження шаблонів – можна буде вказати що шаблон чи функція призначені, наприклад, лише для колекцій які можна сортувати:
template<typename S, typename T>

requires Sequence<S> &&

  Sortable<S> &&

  Equality_compare<Value_type<S>, T>

Iterator<S> sort(S& seq);
...
sort(vector{ 5, 4, 1 }); //Ok
sort(list{5, 4, 1 }); // Error: not Sortable

Ну або скоротити все це до

auto sort(Sortable& seq);

Можна буде писати свої обмеження якось ось так:

 

requires(C x){ { f(x)} –> int }

що означає “має бути можливим викликати функцію f для об’єкту типу С і потім привести результат до типу int”.

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

 

Звісно при всьому бажанні я не можу переказати всього що там було, ось вам кілька посилань щоб почитати самостійно:

  • відеозаписи доповідей буде викладено на http://cppcon.org/. Якщо ви будете дивитися усього по 2 доповіді на тиждень то якраз завершите перегляд перед початком CppCon 2015
  • слайди презентацій доступні на https://github.com/CppCon/CppCon2014
  • Книга Effective Modern C++ добре описує всі нововведення та механізми С++ – http://shop.oreilly.com/product/0636920033707.do
  • Нова книга Страуструпа дуже коротко описує сучасний С++ усього на 180 сторінках (офіційний опис стандарту мови зараз складає понад 800 сторінок) – http://www.stroustrup.com/Tour.html

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