C++,Visual C++,Теорія

C++. STL. Алгоритми для роботи з множинами

Алгоритми для роботи з множинами

Зміст

Пошук на інших ресурсах:

1. Алгоритм includes. Визначити чи одна послідовність може бути підпослідовністю іншої

Алгоритм includes робить перевірку, чи містить один відсортований діапазон усі елементи другого відсортованого діапазону. Порядок сортування та критерій еквівалентності елементів можна задати бінарним предикатом.

Поширені реалізації алгоритму наступні

template <class InputIterator1, class InputIterator2>
bool includes(
  InputIterator1 first1,
  InputIterator1 last1,
  InputIterator2 first2,
  InputIterator2 last2);

template <class InputIterator1, class InputIterator2, class Compare>
bool includes(
  InputIterator1 first1,
  InputIterator1 last1,
  InputIterator2 first2,
  InputIterator2 last2,
  Compare pred );

тут

  • first1, last1 – ітератори вводу, що задають перший впорядкований діапазон;
  • first2, last2 – ітератори вводу, що задають другий впорядкований діапазон;
  • pred – бінарний предикат, що задає критерій еквівалентності елементів.

Приклад 1.

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

void main()
{
  // Алгоритм includes.
  // Визначити, чи містить масив V1 підмасив V2
  // 1. Створити масив з 10 чисел
  vector<int> V1 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

  // 2. Створити підмасив з 4 чисел
  vector<int> V2 = { 5, 6, 7, 8 };

  // 3. Викликати алгоритм includes
  bool res = includes(V1.begin(), V1.end(), V2.begin(), V2.end());

  // 4. Обробити результат
  if (res)
    cout << "V2 <= V1" << endl;
  else
    cout << "V2 != V1" << endl;
}

Результат

V2 <= V1

 

Приклад 2.

У даному прикладі використовується функція Include().

#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <algorithm>
#include <functional>
using namespace std;

// Функція порівняння елементів
bool Include(int item1, int item2)
{
  // Така умова вимагає, щоб послідовності були впорядковані
  return item1 < item2;
}

void main()
{
  // Алгоритм includes.
  // Визначити, чи містить масив V1 підмасив V2
  // 1. Створити масив з 10 чисел
  vector<int> V1 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

  // 2. Створити підмасив з 3 чисел
  vector<int> V2 = { 5, 7, 9, 11 };

  // 3. Викликати алгоритм includes - версія 2
  bool res = includes(V1.begin(), V1.end(), V2.begin(), V2.end(), Include);

  // 4. Обробити результат
  if (res)
    cout << "V2 <= V1" << endl;
  else
    cout << "V2 != V1" << endl;
}

Результат

V2 != V1

  ⇑

2. Алгоритм set_union. Об’єднання послідовностей

Алгоритм set_union реалізує об’єднання двох впорядкованих послідовностей в одну результуючу за принципом об’єднання множин. Елемент, який зустрічається двічі додається до результуючої послідовності тільки один раз. Критерій відбору може бути заданий спеціальною функцією-предикатом. Наприклад

{ 2, 4, 8, 9 } И { 2, 3, 8, 11 } => { 2, 3, 4, 8, 9, 11 }

Відповідно до документації, поширені реалізації алгоритму мають наступні оголошення

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_union(
  InputIterator1 first1,
  InputIterator1 last1,
  InputIterator2 first2,
  InputIterator2 last2,
  OutputIterator result );

template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator set_union(
  InputIterator1 first1,
  InputIterator1 last1,
  InputIterator2 first2,
  InputIterator2 last2,
  OutputIterator result,
  Compare pred );

тут

  • first1, last1 – ітератори вводу, які задають межі першої впорядкованої послідовності;
  • first2, last2 – ітератори вводу, які задають межі другої впорядкованої послідовності;
  • result – ітератор виводу, який задає позицію першого елементу в діапазоні призначення. У цьому діапазоні об’єднуються два вихідних діапазони.

Приклад.

#include <iostream>
#include <algorithm>
#include <list>
using namespace std;

int main()
{
  // Алгоритм set_union - об'єднання послідовностей
  // 1. Створити два списки чисел
  list<int> L1 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  list<int> L2 = { 2, 3, 4, 11, 50 };

  // 2. Створити результуючий список - розмір списку як сума розмірів двох вихідних списків
  list<int> L3(L1.size() + L2.size());

  // 3. Оголосити ітератор, який буде вказувати елемент результуючого списку L3,
  // який слідує за останнім
  list<int>::iterator itRes;

  // 4. Визначення різниці між послідовностями без застосування предикату
  // 4.1. Викликати алгоритм set_difference
  //itRes = set_symmetric_difference(L1.begin(), L1.end(), L2.begin(), L2.end(), L3.begin());
  itRes = set_union(L1.begin(), L1.end(), L2.begin(), L2.end(), L3.begin());

  // 4.2. Вивести результат - значення ітератора в межах [L3.begin() ... itRes)
  list<int>::iterator it = L3.begin();

  while (it != itRes)
  {
    cout << *it << " ";
    it++;
  }
  cout << endl;
}

Результат

0 1 2 3 4 5 6 7 8 9 11 50

  ⇑

3. Алгоритм set_intersection. Визначити спільне між послідовностями (перетин множин)

Алгоритм set_intersection створює послідовність, яка містить спільні елементи двох вихідних послідовностей. Послідовності повинні бути посортовані. Критерій сортування може бути заданий бінарним предикатом. Наприклад

{ 2, 4, 8, 9 } З { 2, 3, 8, 11 } => { 2, 8 }

Поширені реалізації алгоритму мають наступні оголошення

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_intersection(
  InputIterator1 first1,
  InputIterator1 last1,
  InputIterator2 first2,
  InputIterator2 last2,
  OutputIterator result);

template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator set_intersection(
  InputIterator1 first1,
  InputIterator1 last1,
  InputIterator2 first2,
  InputIterator2 last2,
  OutputIterator result,
  Compare pred);

тут

  • first1, last1 – ітератори вводу, що задають діапазон значень першої послідовності;
  • first2, last2 – ітератори вводу, що задають межі другої послідовності;
  • result – ітератор вводу, що задає позицію першого елементу в результуючій послідовності;
  • pred – об’єкт функції-предикату, що задає умову коли один елемент менше за інший.

Приклад.

#include <iostream>
#include <algorithm>
#include <list>
using namespace std;

int main()
{
  // Алгоритм set_intersection - отримання спільного між послідовностями
  // 1. Створити два списки чисел
  list<int> L1 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  list<int> L2 = { 2, 3, 11, 50 };

  // 2. Створити результуючий список - розмір списку як сума розмірів двох вихідних списків
  list<int> L3(L1.size() + L2.size());

  // 3. Оголосити ітератор, який буде вказувати елемент результуючого списку L3,
  // який слідує за останнім
  list<int>::iterator itRes;

  // 4. Визначення різниці між послідовностями без застосування предикату
  // 4.1. Викликати алгоритм set_difference
  itRes = set_intersection(L1.begin(), L1.end(), L2.begin(), L2.end(), L3.begin());

  // 4.2. Вивести результат - значення ітератора в межах [L3.begin() ... itRes)
  list<int>::iterator it = L3.begin();

  while (it != itRes)
  {
    cout << *it << " ";
    it++;
  }
  cout << endl;
}

Результат

2 3

  ⇑

4. Алгоритм set_difference. Різниця послідовностей (різниця множин)

Алгоритм set_difference формує нову послідовність на основі двох посортованих послідовностей за правилом різниці цих послідовностей. У цьому випадку в першій послідовності залишаються тільки ті елементи, яких немає в другій послідовності. Наприклад:

{ 2, 4, 8, 9 } - { 2, 3, 8, 11 } => { 4, 9 }

Поширені реалізації алгоритму мають наступне оголошення

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_difference(
  InputIterator1 first1,
  InputIterator1 last1,
  InputIterator2 first2,
  InputIterator2 last2,
  OutputIterator result );

template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator set_difference(
  InputIterator1 first1,
  InputIterator1 last1,
  InputIterator2 first2,
  InputIterator2 last2,
  OutputIterator result,
  Compare pred );

тут

  • first1, last1 – ітератори вводу, що задають межі першої послідовності;
  • first2, last2 – ітератори вводу, що задають межі другої послідовності;
  • result – ітератор виводу, який вказує на початок результуючої послідовності;
  • pred – предикат, який задає умову коли один елемент менше за інший.

Приклад.

#include <iostream>
#include <algorithm>
#include <list>
using namespace std;

int main()
{
  // Алгоритм set_difference - різниця множин
  // 1. Створити два списки чисел
  list<int> L1 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  list<int> L2 = { 2, 3, 11, 50 };

  // 2. Створити результуючий список - розмір списку як сума розмірів двох вихідних списків
  list<int> L3(L1.size() + L2.size());

  // 3. Оголосити ітератор, який буде вказувати елемент результуючого списку L3,
  // який слідує за останнім
  list<int>::iterator itRes;

  // 4. Визначення різниці між послідовностями без застосування предикату
  // 4.1. Викликати алгоритм set_difference
  itRes = set_difference(L1.begin(), L1.end(), L2.begin(), L2.end(), L3.begin());

  // 4.2. Вивести результат - значення ітератора в межах [L3.begin() ... itRes)
  list<int>::iterator it = L3.begin();

  while (it != itRes)
  {
    cout << *it << " ";
    it++;
  }
  cout << endl;
}

Результат

0 1 4 5 6 7 8 9

  ⇑

5. Алгоритм set_symmetric_difference. Симетрична різниця. Отримати елементи, яких немає в обох послідовностях

Алгоритм set_symmetric_difference повертає послідовність елементів на основі двох посортованих послідовностей. В результуючу послідовність входять елементи, які є або в першій послідовності або в другій послідовності. Спільні елементи не входять у результуючу послідовність. Наприклад

{ 2, 4, 6, 8 } D { 2, 3, 4, 5 } => { 3, 5, 6, 8 }

Згідно з документацією оголошення найбільш поширених реалізацій алгоритму має вигляд

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_symmetric_difference(
  InputIterator1 first1,
  InputIterator1 last1,
  InputIterator2 first2,
  InputIterator2 last2,
  OutputIterator result );

template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator set_symmetric_difference(
  InputIterator1 first1,
  InputIterator1 last1,
  InputIterator2 first2,
  InputIterator2 last2,
  OutputIterator result,
  Compare pred );

тут

  • first1, last1 – ітератори вводу, що задають межі першої послідовності;
  • first2, last2 – ітератори вводу, що задають межі другої послідовності;
  • result – ітератор виводу, який вказує на початок результуючої послідовності;
  • pred – предикат, який задає умову коли один елемент менше за інший.

Приклад.

#include <iostream>
#include <algorithm>
#include <list>
using namespace std;

int main()
{
  // Алгоритм set_symmetric_difference - симетрична різниця двох послідовностей
  // 1. Створити два списки чисел
  list<int> L1 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  list<int> L2 = { 2, 3, 4, 11, 50 };

  // 2. Створити результуючий список - розмір списку як сума розмірів двох вихідних списків
  list<int> L3(L1.size() + L2.size());

  // 3. Оголосити ітератор, який буде вказувати елемент результуючого списку L3,
  // який слідує за останнім
  list<int>::iterator itRes;

  // 4. Визначення різниці між послідовностями без застосування предикату
  // 4.1. Викликати алгоритм set_difference
  itRes = set_symmetric_difference(L1.begin(), L1.end(), L2.begin(), L2.end(), L3.begin());

  // 4.2. Вивести результат - значення ітератора в межах [L3.begin() ... itRes)
  list<int>::iterator it = L3.begin();

  while (it != itRes)
  {
    cout << *it << " ";
    it++;
  }
  cout << endl;
}

Результат

0 1 5 6 7 8 9 11 50

  ⇑

Споріднені теми

  ⇑