Previous
Next
C++ Set Operations on Sorted Ranges: set_union, intersection

C++ Set Operations on Sorted Ranges: set_union, intersection

· 20분 읽기 · 수정 Intermediate tutorial
C++ Set Operations on Sorted Ranges: set_union, intersection

이 글의 핵심

Run set_union, set_intersection, set_difference, set_symmetric_difference, and includes on sorted ranges — complexity, duplicates, and output iterators.

What are set algorithms?

They implement set operations on sorted ranges (not only std::set): union, intersection, difference, symmetric difference, and subset test includes. Operations

AlgorithmNotationMeaning
set_union∪All elements from both sets
set_intersection∩Elements in both sets
set_differenceA − BElements in A but not in B
set_symmetric_difference△Elements in exactly one set
includes⊇Tests if B ⊆ A

Requirements

Critical: Both input ranges must be sorted with the same comparator.

The following example demonstrates the concept in cpp:

#include <algorithm>
#include <vector>
std::vector<int> a = {1, 2, 3, 4};
std::vector<int> b = {3, 4, 5, 6};
// ✅ Both sorted
std::vector<int> result;
std::set_union(a.begin(), a.end(),
               b.begin(), b.end(),
               std::back_inserter(result));
// Result: {1, 2, 3, 4, 5, 6}

set_union

Combines all elements from both ranges:

The following example demonstrates the concept in cpp:

#include <algorithm>
#include <vector>
std::vector<int> a = {1, 3, 5, 7};
std::vector<int> b = {2, 3, 6, 7};
std::vector<int> result;
std::set_union(a.begin(), a.end(),
               b.begin(), b.end(),
               std::back_inserter(result));
// Result: {1, 2, 3, 5, 6, 7}

Time complexity: O(n + m)

set_intersection

Elements present in both ranges:

The following example demonstrates the concept in cpp:

std::vector<int> a = {1, 2, 3, 4, 5};
std::vector<int> b = {3, 4, 5, 6, 7};
std::vector<int> result;
std::set_intersection(a.begin(), a.end(),
                      b.begin(), b.end(),
                      std::back_inserter(result));
// Result: {3, 4, 5}

set_difference

Elements in first but not in second:

The following example demonstrates the concept in cpp:

std::vector<int> a = {1, 2, 3, 4, 5};
std::vector<int> b = {3, 4, 5, 6, 7};
std::vector<int> result;
std::set_difference(a.begin(), a.end(),
                    b.begin(), b.end(),
                    std::back_inserter(result));
// Result: {1, 2}  (in a but not in b)

set_symmetric_difference

Elements in exactly one of the two ranges:

The following example demonstrates the concept in cpp:

std::vector<int> a = {1, 2, 3, 4, 5};
std::vector<int> b = {3, 4, 5, 6, 7};
std::vector<int> result;
std::set_symmetric_difference(a.begin(), a.end(),
                              b.begin(), b.end(),
                              std::back_inserter(result));
// Result: {1, 2, 6, 7}  (in a XOR b)

includes

Tests if second range is subset of first:

std::vector<int> a = {1, 2, 3, 4, 5};
std::vector<int> b = {2, 3, 4};
bool isSubset = std::includes(a.begin(), a.end(),
                              b.begin(), b.end());
// true: all elements of b are in a

Real-world applications

1. Permission system

#include <algorithm>
#include <vector>
#include <string>
class PermissionChecker {
    std::vector<std::string> userPerms_;
    std::vector<std::string> requiredPerms_;
    
public:
    PermissionChecker(std::vector<std::string> user,
                     std::vector<std::string> required) 
        : userPerms_(std::move(user))
        , requiredPerms_(std::move(required)) {
        std::sort(userPerms_.begin(), userPerms_.end());
        std::sort(requiredPerms_.begin(), requiredPerms_.end());
    }
    
    bool hasAllPermissions() const {
        return std::includes(userPerms_.begin(), userPerms_.end(),
                           requiredPerms_.begin(), requiredPerms_.end());
    }
    
    std::vector<std::string> getMissingPermissions() const {
        std::vector<std::string> missing;
        std::set_difference(requiredPerms_.begin(), requiredPerms_.end(),
                          userPerms_.begin(), userPerms_.end(),
                          std::back_inserter(missing));
        return missing;
    }
};
// Usage
PermissionChecker checker(
    {"read", "write", "execute"},
    {"read", "write", "delete"}
);
if (!checker.hasAllPermissions()) {
    auto missing = checker.getMissingPermissions();
    // missing = {"delete"}
}

2. File synchronization

#include <algorithm>
#include <vector>
#include <string>
#include <filesystem>
struct SyncResult {
    std::vector<std::string> toAdd;     // In remote, not local
    std::vector<std::string> toDelete;  // In local, not remote
    std::vector<std::string> common;    // In both
};
SyncResult compareDirectories(std::vector<std::string> local,
                              std::vector<std::string> remote) {
    std::sort(local.begin(), local.end());
    std::sort(remote.begin(), remote.end());
    
    SyncResult result;
    
    std::set_difference(remote.begin(), remote.end(),
                       local.begin(), local.end(),
                       std::back_inserter(result.toAdd));
    
    std::set_difference(local.begin(), local.end(),
                       remote.begin(), remote.end(),
                       std::back_inserter(result.toDelete));
    
    std::set_intersection(local.begin(), local.end(),
                         remote.begin(), remote.end(),
                         std::back_inserter(result.common));
    
    return result;
}

3. Tag filtering

#include <algorithm>
#include <vector>
#include <string>
std::vector<std::string> findPostsWithAllTags(
    const std::vector<std::string>& postTags,
    const std::vector<std::string>& requiredTags
) {
    std::vector<std::string> sortedPost = postTags;
    std::vector<std::string> sortedRequired = requiredTags;
    
    std::sort(sortedPost.begin(), sortedPost.end());
    std::sort(sortedRequired.begin(), sortedRequired.end());
    
    if (std::includes(sortedPost.begin(), sortedPost.end(),
                     sortedRequired.begin(), sortedRequired.end())) {
        return postTags;  // Has all required tags
    }
    return {};
}

Performance benchmarks

Test setup: GCC 13, -O3, sorted vectors

OperationSize ASize BTime (μs)
set_union1000100015
set_intersection1000100012
set_difference1000100011
set_symmetric_difference1000100014
includes10005008
All are O(n + m) — single linear pass through both ranges.

Common mistakes

Mistake 1: Unsorted inputs

std::vector<int> a = {3, 1, 4};  // ❌ Not sorted
std::vector<int> b = {2, 5, 1};  // ❌ Not sorted
std::vector<int> result;
std::set_union(a.begin(), a.end(),
               b.begin(), b.end(),
               std::back_inserter(result));
// ❌ Undefined behavior! Results are garbage

Fix: Sort first:

std::sort(a.begin(), a.end());
std::sort(b.begin(), b.end());
std::set_union(a.begin(), a.end(),
               b.begin(), b.end(),
               std::back_inserter(result));

Mistake 2: Overlapping output

std::vector<int> a = {1, 2, 3};
std::vector<int> b = {3, 4, 5};
// ❌ Undefined behavior: output overlaps input
std::set_union(a.begin(), a.end(),
               b.begin(), b.end(),
               a.begin());
// ✅ Use separate output
std::vector<int> result;
std::set_union(a.begin(), a.end(),
               b.begin(), b.end(),
               std::back_inserter(result));

Mistake 3: Forgetting duplicates

std::vector<int> a = {1, 2, 2, 3};  // Has duplicate
std::vector<int> b = {2, 3, 4};
std::vector<int> result;
std::set_union(a.begin(), a.end(),
               b.begin(), b.end(),
               std::back_inserter(result));
// Result: {1, 2, 2, 3, 4}  — duplicate 2 preserved!
// ✅ Remove duplicates first if needed
a.erase(std::unique(a.begin(), a.end()), a.end());

Comparison with std::set container

Algorithm approach (on vectors)

std::vector<int> a = {1, 3, 5};
std::vector<int> b = {3, 5, 7};
std::vector<int> result;
std::set_intersection(a.begin(), a.end(),
                      b.begin(), b.end(),
                      std::back_inserter(result));

Pros: Fast for sorted vectors, no tree overhead
Cons: Must maintain sorted order manually

Container approach (std::set)

std::set<int> a = {1, 3, 5};
std::set<int> b = {3, 5, 7};
std::set<int> result;
std::set_intersection(a.begin(), a.end(),
                      b.begin(), b.end(),
                      std::inserter(result, result.begin()));

Pros: Automatically sorted, unique elements
Cons: O(log n) insertions, memory overhead

Keywords

set_union, set_intersection, set_difference, set_symmetric_difference, includes, sorted range, STL, C++, algorithm, set operations

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. Run set_union, set_intersection, set_difference, set_symmetric_difference, and includes on sorted ranges — complexity, d… 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

이 글에서 다루는 키워드 (관련 검색어)

C++, Algorithm, set, union, STL 등으로 검색하시면 이 글이 도움이 됩니다.