设定理论数据结构

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<int, float>,这可能更适合您的问题.

要查找两组的交集,请使用该std::set_intersection算法.这需要排序范围,其中包括迭代器的范围std::set或std::map.对于区别,请使用std::set_difference.