c++ - 如何使用set实现无序数据结构？

Question

我想为我的Face结构构建一个无序集合，即

class myFace
{
public:
    //the three points
    int u;
    int v;
    int k;
    myFace() = default;
    myFace(int u, int v, int k) : u(u), v(v), k(k) {}

    bool operator< (const myFace& e) const
    {
        bool result = true;
        min(u, v, k);
        if ((u == e.u && v == e.v && k == e.k) ||
            (u == e.u && v == e.k && k == e.v) ||
            (u == e.v && v == e.u && k == e.k) ||
            (u == e.v && v == e.k && k == e.u) ||
            (u == e.k && v == e.u && k == e.v) ||
            (u == e.k && v == e.v && k == e.u))
        {
            result = false;
        }
        return result;
    }
};

我要确保:

set<myFace> con;
myFace f1(1,2,3);
myFace f2(2,3,1);
myFace f3(3,1,2);

con.insert(f1);
con.insert(f2);
con.insert(f3);
cout << con.size() << endl;

输出应为1。
由于f1，f2，f3相同。

或者我们可以说如何实现3个无序元素的集合，即123,132,213,231,312,321都相同。

Answer 1

秘诀是为您的类(class)使用正确的Comparator并将其提供给集合。我对集here使用了类似的方法。

我采用了此解决方案，并创建了以下示例代码:

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

struct myFace
{
    //the three points
    int u;
    int v;
    int k;
    myFace() = default;
    myFace(int u, int v, int k) : u(u), v(v), k(k) {}
};


struct Comparator {
    bool operator () (const myFace& lhs, const myFace& rhs) const {
        // Convert the structs to vectors
        std::vector<int> v1 = { lhs.u, lhs.v, lhs.k };
        std::vector<int> v2 = { rhs.u, rhs.v, rhs.k };
        // Sort them 
        std::sort(v1.begin(), v1.end());
        std::sort(v2.begin(), v2.end());
        // Compare them
        return v1 < v2;
    }
};

int main() {
    std::set<myFace, Comparator> con;

    myFace f1(1, 2, 3);
    myFace f2(2, 3, 1);
    myFace f3(3, 1, 2);

    con.insert(f1);
    con.insert(f2);
    con.insert(f3);

    std::cout << con.size() << std::endl;

    return 0;
}