集合论数据结构

Question

我有相当函数式编程的背景，但我不习惯（高效的）C++ 数据结构。我需要一个保留多个元素的数据结构，如struct element中所示。在集合中，字段id应该是唯一的。

我想像集合论中一样执行非常快速的集合比较，例如在比较集合 {x1,x2,x3} 和 {x4,x5} 我想要确定交集 {x5} （或 {x2} 在本例中相等）并从其他集合中减去集合，例如 {x1,x2,x3 } \ {x5} = {x1，x3}。

C++ 宇宙中是否存在……“集合论”数据结构？

struct element {
int id;
float value;
};

struct element x1 = {1, 1.0};
struct element x2 = {2, 2.0};
struct element x3 = {3, 3.0};

struct element x4 = {3, 3.1};
struct element x5 = {2, 2.0};

Answer 1

std::set 实现了动态集（动态意味着可以插入或删除元素）。为了使其适用于您的 element 结构，您需要一个仅查看 id 的自定义比较函数。或者，您可以使用 std::map，这可能更适合您的问题。

要查找两个集合的交集，请使用 std::set_intersection 算法。这需要排序范围，其中包括 std::set 或 std::map 中的迭代器范围。对于差异，请使用 std::set_difference。

Answer 2

只是想提一下，因为在处理集合时有一个非常好的数据结构，但它不能满足您的所有需求，

但是如果您有以下要求，您仍然可以记住它：

1）查询元素属于哪个集合

2）不同集合的

并集都在亚对数时间内，即几乎恒定。它称为不相交集数据结构
http://en.wikipedia.org/wiki/Disjoint-set_data_struct

Answer 3

struct element {
    int id;
    float value;

    element(int id_=0, float value_=0.0) : id(id_), value(value_) {}

    bool& operator==(const element& e) const
    {
        return id==e.id && value==e.value;
    }
};

element e1(1,1.0);

std::set<element> set_;
set_.insert(e1);

检查标准算法以了解您可以执行的操作。
http://www.cplusplus.com/reference/algorithm/