사용자 정의 유형으로 std :: set, 중복이 없는지 확인하는 방법

사용자 정의 유형으로 std :: set, 중복이 없는지 확인하는 방법

---

그래서 나는 특정 순서를 유지하고 사용자 정의 (내가) 유형의 중복을 허용하지 않는 std :: set을 가지고 있습니다. 이제 내 유형에서 '<'연산자를 오버로드하여 순서가 올바르게 작동하도록 할 수 있습니다. 그러나 세트는 중복을 적절하게 감지하지 못하며 솔직히 내부적으로 어떻게 수행하는지 완전히 확신하지 못합니다. 나는 '=='연산자를 오버로드했지만 어떻게 든 이것이 세트가 실제로 사용하고 있는지 확실하지 않습니까? 그래서 질문은 값을 추가 할 때 세트가 중복을 어떻게 결정합니까? 다음은 관련 코드입니다.

사용자 정의 유형 :

//! An element used in the route calculation.
struct RouteElem {
    int shortestToHere; // Shortest distance from the start.
    int heuristic;      // The heuristic estimate to the goal.
    Coordinate position;
    bool operator<( const RouteElem& other ) const
    {
        return (heuristic+shortestToHere) < (other.heuristic+other.shortestToHere);
    }
    bool operator==( const RouteElem& other ) const
    {
        return (position.x == other.position.x && position.y == other.position.y);
    }
};

따라서 요소는 위치가 동일 할 때 동일하고, 결합 된 기능이 다른 요소보다 작 으면 요소가 다른 요소보다 작습니다. 정렬은 작동하지만 세트는 동일한 위치의 두 요소를 허용합니다.

---

operator==에서 사용되지 않습니다 std::set. 요소 a및 b동일한 iff로 간주!(a < b) && !(b < a)

---

std::set비교 함수 지정을 지원합니다. 기본값은 동등성을 확인 less하는 operator <데 사용할 것 입니다. 사용자 정의 함수를 정의하여 동등성을 확인하고 대신 사용할 수 있습니다.

std::set<RouteElem, mycomparefunction> myset; 

비교 함수와 정렬 함수를 분리 할 수 ​​없습니다. std::set이진 트리이고 이진 트리의 요소가 특정 요소보다 크거나 작지 않은 경우 동일한 위치에 있어야합니다. 장소 찾기 알고리즘에서 다음과 같은 작업을 수행합니다.

if (a < b) {
    // check the left subtree
} else if (b < a) {
    // check the right subtree
} else {
    // the element should be placed here.
}

---

rlbond의 비교기는 동일하게 비교되는 요소의 삽입을 방지하지 않습니다. rlbond는 std :: set이 !compare(a,b) && !compare(b,a)비교기에 대해 두 요소를 포함하지 않을 것이라고 보장한다고 생각하기 때문에 문자 제한이 주어지면 주석에서 이것을 증명하기가 어렵습니다 . 그러나 rlbond의 비교기는 엄격한 순서를 정의하지 않으므로 std :: set에 대한 유효한 매개 변수가 아닙니다.

#include <set>
#include <iostream>
#include <iterator>
#include <algorithm>

struct BrokenOrder {
    int order;
    int equality;

    public:
    BrokenOrder(int o, int e) : order(o), equality(e) {}

    bool operator<(const BrokenOrder &rhs) const {
        return order < rhs.order;
    }
    bool operator==(const BrokenOrder &rhs) const {
        return equality == rhs.equality;
    }
};

std::ostream &operator<<(std::ostream &stream, const BrokenOrder &b) {
    return stream << b.equality;
}

// rlbond's magic comparator
struct LessThan : public std::binary_function<BrokenOrder, BrokenOrder, bool> {
    bool operator()(const BrokenOrder& lhs, const BrokenOrder& rhs) const
    {
        return !(lhs == rhs) && (lhs < rhs);
    }
};

int main() {
    std::set<BrokenOrder,LessThan> s;
    for (int i = 0; i < 5; ++i) {
        s.insert(BrokenOrder(i,i));
    }
    for (int i = 0; i < 5; ++i) {
        s.insert(BrokenOrder(10-i,i));
    }
    std::copy(s.begin(), s.end(), 
        std::ostream_iterator<BrokenOrder>(std::cout, "\n"));
}

산출:

0
1
2
3
4
3
2
1
0

중복. 매직 비교기가 실패했습니다. 세트의 다른 요소는 동일한 값을 가지 equality므로 operator==삽입하는 동안 세트가 새 요소를 중복 요소와 비교하지 않았기 때문에과 동일합니다. 제외 된 유일한 복제는 4 개였습니다. 두 4의 정렬 순서는 4와 6이 있었기 때문입니다. 이렇게하면 서로 비교할 수있을만큼 세트에서 서로 가깝게 배치되었습니다.

C ++ 표준에서 : 25.3 : 3 "알고리즘이 올바르게 작동하려면 comp 는 값에 대해 엄격한 약한 순서를 유도해야합니다."

25.3 : 4 "... 요구 사항은 comp와 equiv가 모두 전 이적 관계라는 것입니다.

comp(a,b) && comp(b,c) implies comp(a,c)"

이제 요소를 고려 a = BrokenOrder(1,1), b = BrokenOrder(2,2)그리고 c = BrokenOrder(9,1), 그리고 comp마법의 비교기 물론 동일한의를. 그때:

• comp(a,b) 1! = 2 (같음) 및 1 <2 (순서)이므로 참입니다.
• comp(b,c) 2! = 1 (같음) 및 2 <9 (순서)이므로 참입니다.
• comp(a,c) 1 == 1 (같음)이므로 거짓 임

---

STL 집합 구현은 동등성을 감지하기 위해 개념적으로 다음과 같은 작업을 수행합니다.

bool equal = !(a < b) && !(b < a);

즉, 두 요소가 둘 다 다른 요소보다 작지 않으면 동일해야합니다. operator==()메서드에 중단 점을 설정하고 그것이 호출되는지 여부를 확인하여이를 확인할 수 있습니다.

나는 일반적으로 완전히 다른 것을 확인하는 비교 연산자를 의심합니다. 당신의 <연산자는 당신의 방법에서 분리 된 두 가지의 관점에서 정의 된 ==연산자가 정의된다. 일반적으로 이러한 비교는 일관된 정보를 사용하기를 원할 것입니다.

---

다음과 같은 것을 시도 할 수 있습니다.

//! An element used in the route calculation.
struct RouteElem {
    int shortestToHere; // Shortest distance from the start.
    int heuristic;              // The heuristic estimate to the goal.
    Coordinate position;
    bool operator<( const RouteElem& other ) const
    {
      return (heuristic+shortestToHere) < (other.heuristic+other.shortestToHere);
    }
    bool operator==( const RouteElem& other ) const
    {
      return (position.x == other.position.x && position.y == other.position.y);
    }
};

struct CompareByPosition {
    bool operator()(const RouteElem &lhs, const RouteElem &rhs) {
        if (lhs.position.x != rhs.position.x) 
            return lhs.position.x < rhs.position.x;
        return lhs.position.y < rhs.position.y;
    }
};

// first, use std::set to remove duplicates
std::set<RouteElem,CompareByPosition> routeset;
// ... add each RouteElem to the set ...

// now copy the RouteElems into a vector
std::vector<RouteElem> routevec(routeset.begin(), routeset.end());

// now sort via operator<
std::sort(routevec.begin(), routevec.end());

Obviously there's the copy in the middle, which looks slow. But any structure which indexes items by two different criteria is therefore going to have some kind of extra overhead per item compared with a set. The whole of the code above is O(n log n), assuming that your implementation of std::sort uses introsort.

If you have it, under this scheme you could use unordered_set instead of set to do the initial uniqueifying. Since the hash would only have to depend on x and y, it should be faster than the O(log N) comparisons required to insert into a set.

Edit: just noticed that you said you wanted to "keep" sort order, not that you wanted to process everything in a batch. Sorry about that. If you want to efficiently maintain order and exclude duplicates while adding elements, then I would recommend using the set or unordered set I define above, based on position, and also a std::multiset<RouteElem>, which will maintain the operator< order. For each new element, do:

if (routeset.insert(elem).second) {
    routemultiset.insert(elem);
}

Although beware that this offers no exception guarantee. If the second insert throws, then the routeset has been modified, so the state is no longer consistent. So I guess really you need:

if (routeset.insert(elem).second) {
    try {
        routemultiset.insert(elem); // I assume strong exception guarantee
    } catch(...) {
        routeset.erase(elem); // I assume nothrow. Maybe should check those.
        throw;
    }
}

Or an equivalent with RAII, which will be more verbose if there's only one place in your code you ever use the RAII class, but better if there's much repetition.

---

Beware of the ramifications of this. It looks like you are trying to do something like A*, and if you try to insert a "duplicate" it will be ignored, even if there is a "better" route.

NOTE: This solution doesn't work, see onebyone's explanation below

struct RouteElem 
{
    int shortestToHere; // Shortest distance from the start.
    int heuristic;              // The heuristic estimate to the goal.
    Coordinate position;
    bool operator<( const RouteElem& other ) const
    {
        return (heuristic+shortestToHere) < (other.heuristic+other.shortestToHere);
    }
    bool operator==( const RouteElem& other ) const
    {
        return (position.x == other.position.x && position.y == other.position.y);
    }
};

struct RouteElemLessThan : public std::binary_function<RouteElem, RouteElem, bool>
{
    bool operator()(const RouteElem& lhs, const RouteElem& rhs) const
    {
        return !(lhs == rhs) && (lhs < rhs);
    }
};

std::set<RouteElem, RouteElemLessThan> my_set;

참고URL : https://stackoverflow.com/questions/1114856/stdset-with-user-defined-type-how-to-ensure-no-duplicates