c++ - 集合论数据结构

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};

score 5 · Accepted Answer

还有std::set，它实现了动态集（动态意味着可以插入或删除元素）。要使其适用于您的element结构，您需要一个仅查看id. 或者，您可以使用std::map<int, float>，这可能更适合您的问题。

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

score 1 · Accepted Answer

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

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

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

2) 不同集合的并集

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

score 1 · Accepted Answer

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/

c++ - 集合论数据结构

3 回答 3

Related

Reference