---
title: "views::set_ operations"
document: P3741R1
date: 2026-06-30
audience: LEWG, SG9 (Ranges)
reply-to:
  - "Hewill Kang <hewillk@gmail.com>"
---

# views::set_*operations*

## Abstract

This paper proposes four range adaptors for set operations rated as Tier 3 in [P2760](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p2760r1.html), namely `views::set_difference`, `views::set_intersection`, `views::set_union`, and `views::set_symmetric_difference`, to extend the breadth of Ranges.

These adaptors complement existing set algorithms by enabling composable, lazy, and allocation-free views for common set operations. They fill a notable gap in the Ranges library for many practical applications.

## Revision history

### R0

Initial revision.

### R1 (based on SG9's feedback in Brno)

1. Support custom comparator.

2. Provide `reserve_hint` member.

3. Support variadic template version.

4. Specify EB (Erroneous Behavior) when the range is not sorted.

## Motivation

Although there are corresponding constrained algorithm versions of set operations, they all need to output the results to some sort of output range. This brings advantages of the view's lazy evaluation: we can construct set elements on the fly without allocating memory in advance.

Given that set operations are extremely common in the real world, introducing corresponding range adaptors is valuable and facilitates the user experience with Ranges:

```cpp
  /* algorithm approach */
  std::vector<int> dest;
  ranges::set_union(v1, v2, std::back_inserter(dest));

  /* no allocation, composable, n-ary */
  auto union = views::set_union(v1, v2, v3, ...);
```

## Design

### Pipe syntax is Not support

The union and intersection operations support variadic templates, which requires them to be implemented as Customization Point Objects (CPOs) rather than range adaptors.

This design inherently precludes pipe syntax. Even if they were adaptors, pipe syntax would create ambiguity. For instance, in an expression like `views::set_union(r2, r3)`, it is unclear whether `views::set_union(r2, r3)` is intended to be a range adaptor expecting `r1` as input, or a view factory that computes the union of `r2` and `r3`.

We have also decided against pipe syntax for other two. Set operations generally require sorted ranges; since a range passed through a pipe is rarely guaranteed to be sorted, users would likely need to sort it manually first. Given that we currently lack eager algorithms like `action::sort` to facilitate this within a pipeline, the utility of pipe syntax for these operations is limited. We believe that maintaining a consistent API design across all set operations is preferable.

### Constraint for intersection / difference

Intersection

A

B

Difference

A

B

For `views::set_*operations*(A, B)`, both intersection and difference produce only elements from A, so the result is just a subset of A; the element type of B is irrelevant for output, only its order matters. The only thing that matters is making sure the elements of both ranges are strictly weakly ordered so that they can be compared meaningfully.

The standard already has a concept for this, namely `indirect_strict_weak_order`, which is also used for the corresponding constrained algorithm (a component of `mergeable` concept). The signatures of the two classes would be:

```cpp
 template<view V1, view V2>
    requires input_range<V1> && input_range<V2> &&
             indirect_strict_weak_order<ranges::less, iterator_t<V1>, iterator_t<V2>>
  class set_meow_view;
```

### Constraint for union / symmetric difference

Union

A

B

Symmetric
        Difference

A

B

Unlike the above, union and symmetric difference produce elements from both A and B. In addition to ensuring that both ranges are strictly weakly ordered, we also need to ensure that the element types of both ranges are somehow compatible.

Thanks to the fact that it is already `concat_view` in the standard, the `*concatable*` concept is perfect for such a purpose. The signatures of both would be:

```cpp
  template<view V1, view V2>
    requires input_range<V1> && input_range<V2> &&
             indirect_strict_weak_order<ranges::less, iterator_t<V1>, iterator_t<V2>> &&
             concatable<V1, V2>
  class set_meow_view;
```

### Iterator design for intersection / difference

The iterators of the four views all follow a similar design. When they are constructed, we first find the next valid element through the `*satisfy*()` function, and then in each `operator++()`, we increment the underlying iterator and call the `*satisfy*()` again to find the next valid element, and so on.

Since in `*satisfy*()`, we also need to check whether the iterators of A or B have reached the end to determine the next valid element, we need to know the information of the sentinels of both, which means we need to store both sentinels in the iterator.

For `set_intersection_view`, its iterator signature is as follows:

```cpp
  class set_intersection_view::iterator {
    iterator_t<V1> current1_;
    sentinel_t<V1> end1_;
    iterator_t<V2> current2_;
    sentinel_t<V2> end2_;

    constexpr void
    satisfy() {
      while (current1_ != end1_ && current2_ != end2_) {
         /* Find the next valid element in the first range */ 
      }
    }

    constexpr iterator(iterator_t<V1> current1, sentinel_t<V1> end1,
                       iterator_t<V2> current2, sentinel_t<V2> end2)
      : current1_(std::move(current1)), end1_(end1),
        current2_(std::move(current2)), end2_(end2) {
      satisfy();
    } 

  public:
    constexpr decltype(auto) operator*() const { return *current1_; }

    constexpr iterator&
    operator++() {
      ++current1_;
      ++current2_;
      satisfy();
      return *this;
    }

    friend constexpr bool
    operator==(const iterator& x, default_sentinel_t) {
      return x.current1_ == x.end1_ || x.current2_ == x.end2_;
    }
  };
  
```

We can slightly modify the logic of the three functions above,

*satisfy*()

,

operator++()

, and

operator==()

, to make a
  corresponding iterator for

set_difference_view

:

```cpp
  class set_difference_view::iterator {
    iterator_t<V1> current1_;
    sentinel_t<V1> end1_;
    iterator_t<V2> current2_;
    sentinel_t<V2> end2_;

    constexpr void
    satisfy() {
      while (current1_ != end1_ && current2_ != end2_) {
        /* New condition to find the next valid element in the first range */
      }
    }

    constexpr iterator(iterator_t<V1> current1, sentinel_t<V1> end1,
                       iterator_t<V2> current2, sentinel_t<V2> end2)
      : current1_(std::move(current1)), end1_(end1),
        current2_(std::move(current2)), end2_(end2) {
      satisfy();
    } 

  public:
    constexpr decltype(auto) operator*() const { return *current1_; }

    constexpr iterator&
    operator++() {
      ++current1_;
      /* ++current2_; */
      satisfy();
      return *this;
    }

    friend constexpr bool
    operator==(const iterator& x, default_sentinel_t) {
      return x.current1_ == x.end1_ /* || x.current2_ == x.end2_*/;
    }
  };
    
```

### Iterator design for union / symmetric_difference

For `set_union_view`'s iterator, it is necessary to know which underlying iterator is active right now, so an additional flag is need to indicate that.

In addition, since the resulting set contains elements from two different ranges, the new reference type needs to be a common reference of the two, in which case `*concat-reference-t*` nicely fits the purpose:

```cpp
    class set_union_view::iterator {
      iterator_t<V1> current1_;
      sentinel_t<V1> end1_;
      iterator_t<V2> current2_;
      sentinel_t<V2> end2_;
      size_t active_idx_;
  
      constexpr void
      satisfy() {
        /* Find the next valid element from two ranges */
      }
  
      constexpr iterator(iterator_t<V1> current1, sentinel_t<V1> end1,
                         iterator_t<V2> current2, sentinel_t<V2> end2)
        : current1_(std::move(current1)), end1_(end1),
          current2_(std::move(current2)), end2_(end2) {
        satisfy();
      } 
  
    public:
      constexpr concat-reference-t<V1, V2>
      operator*() const {
        if (active_idx_ == 0)
          return *current1_;
        return *current2_;
      }

      constexpr iterator&
      operator++() {
        if (active_idx_ == 0)
          ++current1_;
        else
          ++current2_;
        satisfy();
        return *this;
      }
  
      friend constexpr bool
      operator==(const iterator& x, default_sentinel_t) {
        return x.current1_ == x.end1_ && x.current2_ == x.end2_;
      }
    };
      
```

Similarly, we can make

set_symmetric_difference_view

's iterator by modifying

*satisfy()*

to skip the invalid part.

### Variadic version for intersection/union

During the Brno, SG9 suggested exploring variadic template versions for these views to increase flexibility. However, after further technical consideration, we believe that only intersection and union are actually worth having variadic template versions because they are inherently less ambiguous. Making the other two into variadic templates is neither reasonable nor worthwhile.

The reason only first two are viable comes down to their mathematical properties. Both are strictly associative and commutative. For instance, an expression like `(A ∪ B) ∪ C` yields the exact same result as `A ∪ (B ∪ C)`. Under multiset semantics, evaluating the first grouping yields a final element frequency of `max(max(a, b), c)`, while the second yields `max(a, max(b, c))`. Since the max operation is associative, both groupings produce an identical range.

The exact same logic applies to intersection, where an expression like `(A ∩ B) ∩ C` is identical to `A ∩ (B ∩ C)`. The final frequency for both groupings is a deterministic `min(min(a, b), c) = min(a, min(b, c))`. Because both operations yield identical element frequencies and order, a variadic version eliminates ambiguity around evaluation order.

Union (A ∪ B ∪
        C)

A

B

C

Intersection (A ∩ B ∩
        C)

A

B

C

Note that under the variadic mathematical definition, a unary `set_union` or `set_intersection` simply yields the range itself.

In stark contrast, set difference is non-associative. An expression like `(A \ B) \ C` yields a completely different result than `A \ (B \ C)`, because the former removes elements found in either B or C from A, while the latter removes elements from A that are in B but not in C. A variadic API would force users to guess which evaluation order the library implements.

Similarly, while symmetric difference is associative,meaning `(A Δ B) Δ C` does equal `A Δ (B Δ C)`, adding a variadic version just is not worth the implementation complexity. In a multi-range context, a variadic symmetric difference mathematically evaluates to elements that appear an odd number of times. This is a highly niche mathematical artifact; in real-world engineering, developers are usually looking for elements that appear exactly once across all ranges, making this behavior counter-intuitive and practically useless.

Difference ((A \ B) \
        C)

A

B

C

Symmetric Diff (A Δ B Δ
        C)

A

B

C

### Constraint for Variadic version for intersection/union

For the variadic version of `set_union`, a **pairwise** constraint is strictly required because the output contains elements from all ranges. Any element may need to be compared with any other in downstream operations:

```cpp
// Pack... must be pairwise compatible
template<view... Vs>
  requires (input_range<Vs> && ...) &&
           (indirect_strict_weak_order<ranges::less, iterator_t<Vi>, iterator_t<Vj>> /* for every i, j */) &&
           concatable<Vs...>
class set_union_view;
```

For `set_intersection`, the implementation technically only requires comparing the first range `V1` against all subsequent ranges, since the output is strictly a subset of `V1`:

```cpp
// Implementation minimum requirement
template<view V1, view... Vs>
  requires input_range<V1> && (input_range<Vs> && ...) &&
           (indirect_strict_weak_order<ranges::less, iterator_t<V1>, iterator_t<Vs>> && ...)
class set_intersection_view;
```

However, from a theoretical standpoint, intersection is fundamentally commutative and associative, meaning that a valid relationship exists between all elements regardless of their order. To respect this mathematical property, `set_intersection` should adopt the same pairwise constraint as `set_union`.

This also avoid confusing behavior in practice. Without pairwise constraints, an expression like `set_intersection(A, B, C)` might compile, but changing it to `set_intersection(B, A, C)` would suddenly fail just because B and C cannot be compared directly. Ordering the arguments differently shouldn't break the build, so aligning the constraints ensures consistent behavior.

### Customized comparison is support

While range/v3 supports both custom comparisons and projections like `views::set_operations(rng1, rng2, pred, proj1, proj2)`, we believe only supporting a custom comparison is reasonable, since several views like `views::filter` or `views::chunk_by` already take custom predicates.

On the other hand, supporting custom projections does not really fit the direction of the Ranges library, as no range adaptor supports them. This feature offers little practical usability improvement, considering users can just use `views::transform` to achieve equivalent behavior. Instead, adding projections forces the view class to store extra fields for the projections, which introduces a heavyweight cost.

Furthermore, supporting projections gets ugly once we move to variadic templates, which would end up with a messy interface like `views::set_operations(pred, proj1, proj2, proj3..., r1, r2, r3...)`. Nobody wants to write or read that.

### Borrowed ranges is Not support

Supporting a custom comparison also impacts whether these views can be borrowed ranges. If a custom comparison object is provided, it must be stored within the view class itself. Consequently, the iterator needs to maintain a pointer back to its parent view to access this comparator. Because the iterator holds a dependency on the view's member, these views cannot model `borrowed_range` .

According to [P3117R1](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p3117r1.html) *Extending Conditionally Borrowed*, if the comparator is a `tiny-func`, the iterator does not need a parent pointer because it can construct the comparator on the fly. This theoretically allows us to support `borrowed_range`.

However, without a parent pointer, the iterator must independently store the end iterators of all underlying ranges to safely drive its traversal logic. For non-variadic ones, this requires storing 2 extra end iterators inside the iterator class. For a variadic version, the iterator would have to carry a whole collection of end iterators. This massive size increase makes the iterator too heavyweight, meaning supporting `borrowed_range` this way is simply not worth the cost.

### Common range is Not support

The fundamental reason these views cannot universally support `common_range` is an implementation impossibility; the exact end positions of the underlying iterators cannot be known in advance. For example, `set_difference(r1, r2)` finishes the moment `r1` reaches its end. But at that exact moment, where should the iterator for `r2` be pointing? Its final position depends entirely on the runtime data.

The same fundamental issue applies to `set_intersection`. The traversal stops as soon as any underlying range hits its end, meaning we can never predict which one will exhaust first, nor where the remaining iterators will be sitting at that moment.

On the other hand, `set_union` and `set_symmetric_difference` require fully exhausting all participating ranges to complete their traversal, providing `common_range` support specifically for these two views is feasible. The paper does currenly not to provide any to keep the design simple and consistent.

### Bidirectional is Not support

Theoretically, these views could support bidirectional iteration, but doing so provides little value. For `set_difference` and `set_intersection`, it is only known that one range has reached its end, while the final positions of the other ranges remain unknown. Consequently, these views cannot model `common_range`, which makes supporting `bidirectional_range` meaningless because it is impossible to execute `--view.end()`.

For `set_union` and `set_symmetric_difference`, reverse traversal cannot be correctly supported without tracking the traversal history when the underlying ranges contain duplicate elements:

```cpp
// Input ranges
{ 2, 3, [4] }
{ 2, 3, (4), <4> }

// Forward Traversal for set_union:
{ 2, 3, [4], <4> }
// Final state: r1_it == r1.end(), r2_it == r2.end()

// Reverse Traversal from set_union:
{ [4], (4), 3, 2 }  // <-- Wrong elements
```

It is also worth noting that supporting bidirectional iteration would introduce potential use-after-move issues due to element comparisons between the two ranges. For instance, composing `views::as_rvalue | views::reverse` could lead to undefined behavior.

Therefore, the author does not plan to support bidirectional iteration, which is consistent with the design of [range/v3](https://github.com/ericniebler/range-v3/blob/master/include/range/v3/view/set_algorithm.hpp).

### Non const-iterable (even for pure input-range)

Except for set union, `*satisfy()*` for other operations has the worst complexity of O(n) because we need to skip the invalid white area to locate the next valid element. In order to ensure the amortized constant time complexity of `begin()` required by the `range` concept, we need to cache the iterator in the first call to `begin()`, which means that other view classes except `set_union_view` are not `const`-iterable.

It is worth noting that while C++26 introduced const-iterable support for `filter_view` when the underlying range is an pure input range, a similar optimization is unnecessary for our views. Although input-only ranges do not require iterator caching to maintain complexity guarantees, all set operations fundamentally require their input sequences to be sorted.

Since pre-sorted sequence in an input-only context is exceedingly rare in practical scenarios, adding extra implementation complexity to support a non-caching `const begin()` for this niche edge case provides no real-world motivation. Therefore, the author chose not to provide such support, keeping the design pragmatic and clean.

Here is the summary table:

| View | `const`-Iterable | Caches `begin()` | Complexity |
| --- | --- | --- | --- |
| `set_difference_view` | ❌ | ✅ | Amortized constant |
| `set_intersection_view` | ❌ | ✅ | Amortized constant |
| `set_union_view` | ✅ | ❌ | Constant |
| `set_symmetric_difference_view` | ❌ | ✅ | Amortized constant |

### Provide reserve_hint() member

During the Brno meeting, SG9 suggested that providing a `reserve_hint` member function would still be valuable, even if it only offers a loose upper bound. The primary motivation is to allow downstream operations, such as `ranges::to<std::vector>()`, to pre-allocate memory and reduce the overhead of frequent reallocations.

The implementation logic for computing these upper bounds is straightforward. For a union or a symmetric difference, the maximum possible size is simply the sum of both range sizes, or `size(A) + size(B)`. For an intersection, the resulting size can never exceed the size of the smaller range, which is `std::min(size(A), size(B))`. Lastly, for a set difference, the size of the output is strictly bounded by the size of the first range, `size(A)`.

### No customized iter_swap() specializations

It doesn't make sense to provide `iter_swap` specializations for these new iterators, since we'd break the origin order by swapping the elements which leads to undefined behavior.

### Erroneous behavior for unsorted input ranges

Following feedback from SG9, violating the sorted precondition for input ranges is designated as Erroneous Behavior rather than Undefined Behavior.

While set operations require both input ranges to be sorted to ensure correct semantics, treating unsorted inputs as erroneous behavior strikes the right balance, which allows implementations to catch these contract violations.

### Provide base() member

intersection and difference can be seen as a subset of the first range, so it makes sense to provide `base()` members for it and its iterator to access the first underlying view and iterator.

## Implementation experience

The author implemented four `views::set_*operations*`s based on libstdc++, see [godbolt](https://godbolt.org/z/b3P5Yzv4h).

## Wording

This wording is relative to the [latest working draft](https://eel.is/c++draft).

## References

[P2760R1]

Barry Revzin. A Plan for C++26 Ranges. URL:

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p2760r1.html

[range/v3]

Eric Niebler.

views::set_*operations*

implementation. URL:

https://github.com/ericniebler/range-v3/blob/master/include/range/v3/view/set_algorithm.hpp