Algorithms for working with sets

---

Contents

• 1. Algorithm includes. Determine if one sequence can be a subsequence of another
• 2. Algorithm set_union. Combining sequences
• 3. Algorithm set_intersection. Determine what is common between sequences (section of sets)
• 4. Algorithm set_difference. Sequence difference (set difference)
• 5. Algorithm set_symmetric_difference. Symmetric difference. Get elements that are not in both sequences
• Related topics

---

Search other resources:

1. Algorithm includes. Determine if one sequence can be a subsequence of another

The includes algorithm checks if one sorted range contains all the elements of the second sorted range. The sort order and the element equivalence criterion can be specified by a binary predicate.

Common implementations of the algorithm are as follows

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 );

here

• first1, last1 – input iterators that define the first ordered range;
• first2, last2 – input iterators specifying the second ordered range;
• pred – binary predicate that specifies a criterion for the equivalence of elements.

Example 1.

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

void main()
{
  // Algorithm includes.
  // Determine if the array V1 contains a subarray V2
  // 1. Create an array of 10 numbers
  vector<int> V1 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

  // 2. Create a subarray of 4 numbers
  vector<int> V2 = { 5, 6, 7, 8 };

  // 3. Call the includes algorithm
  bool res = includes(V1.begin(), V1.end(), V2.begin(), V2.end());

  // 4. Process the result
  if (res)
    cout << "V2 <= V1" << endl;
  else
    cout << "V2 != V1" << endl;
}

Result

V2 <= V1

 

Example 2.

This example uses the Include() function.

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

// Function for comparing elements
bool Include(int item1, int item2)
{
  // Such a condition requires the sequences to be ordered
  return item1 < item2;
}

void main()
{
  // Algorithm includes.
  // Determine if the array V1 contains a subarray V2
  // 1. Create an array of 10 numbers
  vector<int> V1 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

  // 2. Create a sub-array of 3 numbers
  vector<int> V2 = { 5, 7, 9, 11 };

  // 3. Call includes algorithm - version 2.
  bool res = includes(V1.begin(), V1.end(), V2.begin(), V2.end(), Include);

  // 4. Process the result
  if (res)
    cout << "V2 <= V1" << endl;
  else
    cout << "V2 != V1" << endl;
}

Result

V2 != V1

  ⇑

2. Algorithm set_union. Combining sequences

The set_union algorithm implements the union of two ordered sequences into one resulting sequence according to the principle of union of sets. An element that occurs twice is added to the resulting sequence only once. The selection criterion can be set by a special predicate function. For example

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

According to the documentation, common algorithm implementations have the following declarations

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 );

here

• first1, last1 – input iterators that define the boundaries of the first ordered sequence;
• first2, last2 – input iterators that define the boundaries of the second ordered sequence;
• result – output iterator that specifies the position of the first element in the destination range. The two output ranges are combined in this range.

Example.

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

int main()
{
  // The set_union algorithm is a union of sequences.
  // 1. Create two lists of numbers
  list<int> L1 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  list<int> L2 = { 2, 3, 4, 11, 50 };

  // 2. Create the resulting list - the size of the list as the sum of the sizes of the two source lists
  list<int> L3(L1.size() + L2.size());

  // 3. Declare an iterator that will point to the next element of the L3 resulting list
  list<int>::iterator itRes;

  // 4. Determining the difference between sequences without applying a predicate
  // 4.1. Call the set_difference algorithm
  //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. Output the result - the value of the iterator within [L3.begin() ... itRes)
  list<int>::iterator it = L3.begin();

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

Result

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

  ⇑

3. Algorithm set_intersection. Determine what is common between sequences (section of sets)

The set_intersection algorithm creates a sequence containing common elements of the two source sequences. The sequences must be sorted. The sort criterion can be specified by a binary predicate. For example

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

Common algorithm implementations have the following declarations

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);

here

• first1, last1 – input iterators specifying the range of values of the first sequence;
• first2, last2 – input iterators specifying the range of the second sequence;
• result – input iterator that specifies the position of the first element in the resulting sequence;
• pred – predicate function object that specifies the condition when one element is less than another.

Example.

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

int main()
{
  // Algorithm set_intersection - getting common between sequences
  // 1. Create two lists of numbers
  list<int> L1 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  list<int> L2 = { 2, 3, 11, 50 };

  // 2. Create the resulting list - the size of the list as the sum of the sizes of the two source lists
  list<int> L3(L1.size() + L2.size());

  // 3. Declare an iterator that will point to the next element of the resulting L3 list.
  list<int>::iterator itRes;

  // 4. Determining the difference between sequences without applying a predicate
  // 4.1. Call the set_difference algorithm
  itRes = set_intersection(L1.begin(), L1.end(), L2.begin(), L2.end(), L3.begin());

  // 4.2. Print the result - the value of the iterator within [L3.begin() ... itRes)
  list<int>::iterator it = L3.begin();

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

Result

2 3

  ⇑

4. Algorithm set_difference. Sequence difference (set difference)

The set_difference algorithm generates a new sequence based on two sorted sequences according to the rule of the difference of these sequences. In this case, only elements that are not in the second sequence remain in the first sequence. For example:

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

Common algorithm implementations have the following declarations

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 );

where

• first1, last1 – input iterators that define the limits of the first sequence;
• first2, last2 – input iterators specifying limits of the second sequence;
• result – output iterator pointing to the beginning of the resulting sequence;
• pred – a predicate that specifies a condition when one element is less than another.

Example.

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

int main()
{
  // Algorithm set_difference
  // 1. Create two lists of numbers
  list<int> L1 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  list<int> L2 = { 2, 3, 11, 50 };

  // 2. Create resulting list - list size as the sum of the sizes of the two original lists
  list<int> L3(L1.size() + L2.size());

  // 3. Declare an iterator that will point to the next element after the last element of the resulting L3 list
  list<int>::iterator itRes;

  // 4. Determining differences between sequences without applying a predicate.
  // 4.1. Call the set_difference algorithm
  itRes = set_difference(L1.begin(), L1.end(), L2.begin(), L2.end(), L3.begin());

  // 4.2. Output the result - the value of the iterator within [L3.begin() ... itRes)
  list<int>::iterator it = L3.begin();

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

Result

0 1 4 5 6 7 8 9

  ⇑

5. Algorithm set_symmetric_difference. Symmetric difference. Get elements that are not in both sequences

The set_symmetric_difference algorithm returns a sequence of elements based on two sorted sequences. The resulting sequence contains elements that are either in the first sequence or in the second sequence. Common elements are not included in the resulting sequence. For example

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

According to the documentation, the declaration of the most common implementations of the algorithm is

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 );

where

• first1, last1 – input iterators that define the limits of the first sequence;
• result – output iterator pointing to the beginning of the resulting sequence;
• pred – a predicate that specifies a condition when one element is less than another.

Example.

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

int main()
{
  // set_symmetric_difference algorithm - symmetric difference of two sequences
  // 1. Create two lists of numbers
  list<int> L1 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  list<int> L2 = { 2, 3, 4, 11, 50 };

  // 2. Create the resulting list - the size of the list as the sum of the sizes of the two source lists.
  list<int> L3(L1.size() + L2.size());

  // 3. Declare an iterator that will point to the next element of the resulting L3 list
  list<int>::iterator itRes;

  // 4. Determining the difference between sequences without applying a predicate
  // 4.1. Call the set_difference algorithm
  itRes = set_symmetric_difference(L1.begin(), L1.end(), L2.begin(), L2.end(), L3.begin());

  // 4.2. Output the result - the value of the iterator within [L3.begin() ... itRes)
  list<int>::iterator it = L3.begin();

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

Result

0 1 5 6 7 8 9 11 50

  ⇑

---

Related topics

• Algorithms for working with data which are presented according to the heap principle. Algorithms make_heap, push_heap, pop_heap, sort_heap
• Algorithms for determining the minimum and maximum. Algorithms min, min_element, max, max_element, lexicographical_compare
• Permutation algorithms. Algorithms next_permutation, prev_permutation
• Non-modifying algorithms. Search. Examples. Algorithms find, find_if, find_first_of, find_end, adjanced_find, search, search_n
• Non-modifying algorithms. Algorithms count, count_if, equal, equal_range, mismatch

  ⇑

---