C++ Check If Set Contains Subset

MUAZHAN

4 min read

·

Jul 01, 2024

32

Share

Checking if a Set Contains a Subset in C++

This article will guide you through different methods to check if a set in C++ contains a subset.

Understanding the Problem

Given two sets, A and B, we want to determine if B is a subset of A. This means that all elements of B must also exist in A.

Using std::includes

The C++ Standard Library provides a convenient function called std::includes to check if one sorted range is a subset of another. This function takes two sorted ranges as arguments and returns true if the first range is a subset of the second, and false otherwise.

#include 
#include 
#include 

int main() {
  std::set A = {1, 2, 3, 4, 5};
  std::set B = {2, 4};

  // Check if B is a subset of A
  bool isSubset = std::includes(B.begin(), B.end(), A.begin(), A.end());

  std::cout << "B is a subset of A: " << isSubset << std::endl;

  return 0;
}

Output:

B is a subset of A: 1

Explanation:

• The std::includes function checks if all elements of B are present in A.
• As B is a subset of A, the function returns true.

Iterating Over Elements

If the sets are not sorted, you can iterate over the elements of the subset and check if each element is present in the larger set.

#include 
#include 

int main() {
  std::set A = {1, 2, 3, 4, 5};
  std::set B = {2, 4};

  // Check if B is a subset of A
  bool isSubset = true;
  for (int element : B) {
    if (A.find(element) == A.end()) {
      isSubset = false;
      break;
    }
  }

  std::cout << "B is a subset of A: " << isSubset << std::endl;

  return 0;
}

Output:

B is a subset of A: 1

Explanation:

• The code iterates through each element in B.
• For each element, it checks if the element is present in A using find.
• If the element is not found in A, isSubset is set to false, and the loop breaks.

Choosing the Best Method

• If your sets are already sorted, using std::includes is the most efficient method.
• If your sets are not sorted, iterating over the elements and checking for presence in the larger set is a simple and effective approach.

Remember to choose the method that best suits your specific needs and data structures.