std::ranges::set_difference, std::ranges::set_difference_result
| 헤더에 정의됨 <algorithm>
|
||
| 호출 시그니처 |
||
template< std::input_iterator I1, std::sentinel_for<I1> S1,
std::input_iterator I2, std::sentinel_for<I2> S2,
std::weakly_incrementable O, class Comp = ranges::less,
class Proj1 = std::identity, class Proj2 = std::identity >
requires std::mergeable<I1, I2, O, Comp, Proj1, Proj2>
constexpr set_difference_result<I1, O>
set_difference( I1 first1, S1 last1, I2 first2, S2 last2,
O result, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {} );
|
(1) | (C++20부터) |
template< ranges::input_range R1, ranges::input_range R2,
std::weakly_incrementable O, class Comp = ranges::less,
class Proj1 = std::identity, class Proj2 = std::identity >
requires std::mergeable<ranges::iterator_t<R1>, ranges::iterator_t<R2>,
O, Comp, Proj1, Proj2>
constexpr set_difference_result<ranges::borrowed_iterator_t<R1>, O>
set_difference( R1&& r1, R2&& r2, O result, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {} );
|
(2) | (C++20부터) |
| 헬퍼 타입 |
||
template< class I, class O >
using set_difference_result = ranges::in_out_result<I, O>;
|
(3) | (C++20부터) |
정렬된 입력 범위 [first1, last1)에서 정렬된 입력 범위 [first2, last2)에 없는 요소들을 result에서 시작하는 출력 범위로 복사합니다.
동작은 다음 조건에서 정의되지 않습니다.
- 입력 범위가
comp및proj1또는proj2에 대해 각각 정렬되지 않은 경우, 또는 - 결과 범위가 입력 범위 중 하나와 겹치는 경우.
comp를 사용하여 비교됩니다.r1를 첫 번째 범위로 사용하고 r2를 두 번째 범위로 사용합니다. 마치 ranges::begin(r1)를 first1로, ranges::end(r1)을 last1로, ranges::begin(r2)을 first2로, ranges::end(r2)을 last2로 사용하는 것과 같습니다.이 페이지에서 설명하는 함수형 엔티티는 알고리즘 함수 객체입니다 (비공식적으로 니블로이드라고 함). 즉:
- 명시적 템플릿 인자 목록은 이들 중 하나를 호출할 때 지정할 수 없습니다.
- 이들 중 어느 것도 인자 종속 검색에 보이지 않습니다.
- 이들 중 하나가 함수 호출 연산자 왼쪽의 이름으로 일반 비한정 검색에 의해 발견되면, 인자 종속 검색이 억제됩니다.
매개변수
| first1, last1 | - | 첫 번째 정렬된 입력 range 의 요소들을 정의하는 iterator-sentinel 쌍 |
| first2, last2 | - | 두 번째 정렬된 입력 range 의 요소들을 정의하는 iterator-sentinel 쌍 |
| r1 | - | 첫 번째 정렬된 입력 범위 |
| r2 | - | 두 번째 정렬된 입력 범위 |
| result | - | 출력 범위의 시작점 |
| comp | - | 투영된 요소들에 적용할 비교자 |
| proj1 | - | 첫 번째 범위의 요소들에 적용할 투영 |
| proj2 | - | 두 번째 범위의 요소들에 적용할 투영 |
반환값
{ last1, result_last } , 여기서 result_last 는 구성된 범위의 끝입니다.
복잡도
최대 2·(N 1 +N 2 )-1 번의 비교와 각 프로젝션의 적용이 필요하며, 여기서 N 1 과 N 2 는 각각 ranges:: distance ( first1, last1 ) 와 ranges:: distance ( first2, last2 ) 입니다.
가능한 구현
struct set_difference_fn { template<std::input_iterator I1, std::sentinel_for<I1> S1, std::input_iterator I2, std::sentinel_for<I2> S2, std::weakly_incrementable O, class Comp = ranges::less, class Proj1 = std::identity, class Proj2 = std::identity> requires std::mergeable<I1, I2, O, Comp, Proj1, Proj2> constexpr ranges::set_difference_result<I1, O> operator()(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const { while (!(first1 == last1 or first2 == last2)) { if (std::invoke(comp, std::invoke(proj1, *first1), std::invoke(proj2, *first2))) { *result = *first1; ++first1; ++result; } else if (std::invoke(comp, std::invoke(proj2, *first2), std::invoke(proj1, *first1))) ++first2; else { ++first1; ++first2; } } return ranges::copy(std::move(first1), std::move(last1), std::move(result)); } template<ranges::input_range R1, ranges::input_range R2, std::weakly_incrementable O, class Comp = ranges::less, class Proj1 = std::identity, class Proj2 = std::identity> requires std::mergeable<ranges::iterator_t<R1>, ranges::iterator_t<R2>, O, Comp, Proj1, Proj2> constexpr ranges::set_difference_result<ranges::borrowed_iterator_t<R1>, O> operator()(R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const { return (*this)(ranges::begin(r1), ranges::end(r1), ranges::begin(r2), ranges::end(r2), std::move(result), std::move(comp), std::move(proj1), std::move(proj2)); } }; inline constexpr set_difference_fn set_difference {}; |
예제
#include <algorithm> #include <cassert> #include <iostream> #include <iterator> #include <string_view> #include <vector> auto print = [](const auto& v, std::string_view end = "") { std::cout << "{ "; for (auto n{v.size()}; auto i : v) std::cout << i << (--n ? ", " : " "); std::cout << "} " << end; }; struct Order // 매우 흥미로운 데이터를 가진 구조체 { int order_id{}; friend std::ostream& operator<<(std::ostream& os, const Order& ord) { return os << '{' << ord.order_id << '}'; } }; int main() { const auto v1 = {1, 2, 5, 5, 5, 9}; const auto v2 = {2, 5, 7}; std::vector<int> diff{}; std::ranges::set_difference(v1, v2, std::back_inserter(diff)); print(v1, "∖ "); print(v2, "= "); print(diff, "\n\n"); // 이전 상태와 새 상태 사이에서 어떤 주문들이 "차이"를 보이는지 알고 싶습니다: const std::vector<Order> old_orders{{1}, {2}, {5}, {9}}; const std::vector<Order> new_orders{{2}, {5}, {7}}; std::vector<Order> cut_orders(old_orders.size() + new_orders.size()); auto [old_orders_end, cut_orders_last] = std::ranges::set_difference(old_orders, new_orders, cut_orders.begin(), {}, &Order::order_id, &Order::order_id); assert(old_orders_end == old_orders.end()); std::cout << "old orders = "; print(old_orders, "\n"); std::cout << "new orders = "; print(new_orders, "\n"); std::cout << "cut orders = "; print(cut_orders, "\n"); cut_orders.erase(cut_orders_last, end(cut_orders)); std::cout << "cut orders = "; print(cut_orders, "\n"); }
출력:
{ 1, 2, 5, 5, 5, 9 } ∖ { 2, 5, 7 } = { 1, 5, 5, 9 }
old orders = { {1}, {2}, {5}, {9} }
new orders = { {2}, {5}, {7} }
cut orders = { {1}, {9}, {0}, {0}, {0}, {0}, {0} }
cut orders = { {1}, {9} }
참고 항목
(C++20) |
두 집합의 합집합을 계산합니다 (알고리즘 함수 객체) |
(C++20) |
두 집합의 교집합을 계산합니다 (알고리즘 함수 객체) |
| 두 집합의 대칭차집합을 계산합니다 (알고리즘 함수 객체) | |
(C++20) |
한 시퀀스가 다른 시퀀스의 부분 수열인지 확인합니다 (알고리즘 함수 객체) |
| 두 집합의 차집합을 계산합니다 (함수 템플릿) |