C ++ STL 세트 차이

C ++ STL 세트 차이

---

C ++ STL 집합 데이터 구조에 집합 차이 연산자가 있습니까?

---

네, 이에,이 <algorithm>및 호출 됩니다. 사용법은 다음과 가변합니다.std::set_difference

#include <algorithm>
#include <set>
#include <iterator>
// ...
std::set<int> s1, s2;
// Fill in s1 and s2 with values
std::set<int> result;
std::set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),
    std::inserter(result, result.end()));

결국 세트 result에는 s1-s2.

---

예, 알고리즘 헤더에 set_difference 함수가 있습니다.

편집 :

참고로, 추천 데이터 구조는 문서에 사용할 수 있습니다 . 알고리즘은 일련의 정렬 된 컬렉션에 대한 반복기 정렬 된 컬렉션에 있습니다.

다른 사람들이 외부에서 언급 한 방법이 있습니다. 아마도 그것은 당신의 응용 프로그램에 좋습니다.

---

언어 적 의미에서 "연산자"는 표준 라이브러리에는 set_difference 알고리즘이 있습니다.

http://www.cplusplus.com/reference/algorithm/set_difference.html

물론, 링크 된 문서의 끝에있는 "참고 항목"섹션에서 제안한대로 다른 기본 집합 연산도 있습니다 (union 등).

---

선택한 내용은 있지만 구문 오류가 있습니다.

대신에

#include <algorithms>

사용하다

#include <algorithm>

대신에

std::insert_iterator(result, result.end()));

사용하다

std::insert_iterator<set<int> >(result, result.end()));

---

방법으로는 외부 알고리즘 함수 set_difference가 있습니다.

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
                              InputIterator2 first2, InputIterator2 last2,
                              OutputIterator result);

http://www.sgi.com/tech/stl/set_difference.html

---

분명히 그렇습니다.

SGI-set_difference

---

다시 한 번 구조를 강화하십시오.

#include <string>
#include <set>
#include <boost/range/algorithm/set_algorithm.hpp>

std::set<std::string> set0, set1, setDifference;
boost::set_difference(set0, set1, std::inserter(setDifference, setDifference.begin());

setDifference에는 set0-set1이 포함됩니다.

---

C ++는 차이 집합 연산자를 정의하지 않지만 다른 응답에 수 코드를 사용하여 직접 정의 할 수 있습니다.

template<class T>
set<T> operator -(set<T> reference, set<T> items_to_remove)
{
    set<T> result;
    std::set_difference(
        reference.begin(), reference.end(),
        items_to_remove.begin(), items_to_remove.end(),
        std::inserter(result, result.end()));
    return result;
}

---

내가 여기서 보는 모든 답은 O (n)입니다. 이게 더 낫지 않을까요? :

template <class Key, class Compare, class Allocator>   
std::set<Key, Compare, Allocator> 
set_subtract(std::set<Key, Compare, Allocator>&& lhs,
             const std::set<Key, Compare, Allocator>& rhs) {
    if (lhs.empty()) { return lhs; }
    // First narrow down the overlapping range:
    const auto rhsbeg = rhs.lower_bound(*lhs.begin());
    const auto rhsend = rhs.upper_bound(*lhs.rbegin());
    for (auto i = rhsbeg; i != rhsend; ++i) {
        lhs.erase(*i);
    }
    return std::move(lhs);
}

그것은 옳은 일을하는 것 같습니다. 나는 그 사건을 처리하는 방법을 모르겠어요 Compare경우에서와 같이 '의 형식이 완전히 동작을 지정하지 않는 CompareA는 std::function<bool(int,int)>하지만, 옆으로) 그에서이 작업 오른쪽으로 보인다 O는 ((NUM은 중복 같아야 • log ( lhs.size())).

를 lhs포함하지 않는 경우 *i, rhs.size()의 다음 요소 rhs> =의 다음 요소에 대해 O (log ( )) 검색을 수행하여 추가로 최적화 할 수 있습니다 lhs. 즉 그 경우 최적화 것 lhs = {0, 1000}및 rhs = {1, 2, ..., 999}로그 시간의 뺄셈을 할 수있다.

---

우리는 그냥 사용할 수 있습니까

 set_difference(set1.begin(), set1.end(), set2.begin(). set2,end(),std::back_inserter(result)).

참고 URL : https://stackoverflow.com/questions/283977/c-stl-set-difference