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

  ⇑

Связанные темы

  ⇑