Set Algorithms

Difference vs Symmetric Difference

What is the difference between set_difference() and set_symmetric_difference()?

Abstract art representing computer programming

std::ranges::set_difference() and std::ranges::set_symmetric_difference() are both algorithms used to find the difference between two sets, but they serve different purposes and produce different results.

std::ranges::set_difference()

The set_difference() algorithm returns elements that are in the first set but not in the second set. It essentially subtracts the elements of the second set from the first set.

For example, given two sets $A = 3$ and $B = 5$, the difference $A - B$ is $2$ because 3 is present in both sets and is thus excluded from the result.

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector<int> A{1, 2, 3};
  std::vector<int> B{3, 4, 5};
  std::vector<int> Results;
  Results.resize(A.size());

  auto [AEnd, DifferenceEnd] =
      std::ranges::set_difference(
        A, B, Results.begin());

  Results.erase(DifferenceEnd, Results.end());

  for (auto x : Results) {
    std::cout << x << ", ";
  }
}
1, 2,

std::ranges::set_symmetric_difference()

The set_symmetric_difference() algorithm, on the other hand, returns elements that are in either of the sets but not in both. It’s like the exclusive OR (XOR) operation.

Using the same sets $A = 3$ and $B = 5$, the symmetric difference $A \triangle B$ is $5$. This includes all elements except those that are common to both sets.

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector<int> A{1, 2, 3};
  std::vector<int> B{3, 4, 5};
  std::vector<int> Results;
  Results.resize(A.size() + B.size());

  auto [AEnd, BEnd, SymmetricDifferenceEnd] =
    std::ranges::set_symmetric_difference(
      A, B, Results.begin());

  Results.erase(
    SymmetricDifferenceEnd, Results.end());

  for (auto x : Results) {
    std::cout << x << ", ";
  }
}
1, 2, 4, 5,

Key Differences

  • Purpose: set_difference() is for subtracting one set from another, while set_symmetric_difference() is for finding elements unique to each set.
  • Result: set_difference() results in elements unique to the first set, set_symmetric_difference() results in elements unique to either set.

When to Use Each

  • Use set_difference() when you need to find elements that belong to one set but not another, such as finding tasks assigned to one person but not another.
  • Use set_symmetric_difference() when you need to find elements that are unique across both sets, such as comparing changes between two versions of a dataset.

Understanding these differences helps you choose the right algorithm for your specific set operations.

Answers to questions are automatically generated and may not have been reviewed.

Free, Unlimited Access

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Screenshot from Warhammer: Total War
Screenshot from Tomb Raider
Screenshot from Jedi: Fallen Order
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved