设定理论数据结构 [英] Set theory data structure

问题描述

我来自一个相当功能的编程背景，我不习惯（高效）C ++数据结构。我需要一个数据结构，保留多个元素，如 struct element 中所描述的。在集合中，字段id将是唯一的。

我想执行一个非常快速的集合比较，如集合理论，即比较集合 {x1，x2，x3} code>和 {x4，x5} 我想确定交集集 {x5} （或 {x2} 在这种情况下是相等的）和其他集合的子集，例如 {x1，x2，x3} \ {x5} = {x1，x3} 。

...在C ++ Universe中设置理论数据结构？

  struct element {
 int id; 
浮点值; 
}; 
 
结构元素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}; 
  

解决方案

有 std :: set ，它实现动态集（动态元素可以插入或删除）。要使其与您的元素结构一起使用，您需要一个仅查看 id 的自定义比较函数。或者，您可以使用 std :: map< int，float> ，这可能更适合您的问题。

要查找两组的交集，请使用 std： ：set_intersection 算法。这需要排序范围，其中包括 std :: set 或 std :: map 中的迭代器范围。有关区别，请使用 std :: set_difference 。

I come from a rather functional programming background and I'm not used to (efficient) C++ data structures. I need a data structure that keeps multiple elements like depicted in struct element. In the collection, the field id shall be unique.

I want to perform a very fast set comparison like in set theory i.e. for example when comparing the sets {x1,x2,x3} and {x4,x5} I want to determine the intersection set {x5} (or {x2} which are equal in this case) and substract sets from other sets like e.g. {x1,x2,x3} \ {x5} = {x1,x3}.

Is there a ... "set theoretic" datastructure out there in the C++ universe?

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

解决方案

There's std::set, which implements dynamic sets (dynamic means elements can be inserted or deleted). To make it work with your element structure, you need a custom comparison function that looks only at the id. Alternatively, you could use std::map<int, float>, which might be a better fit to your problem.

To find the intersection of two sets, use the std::set_intersection algorithm. That requires sorted ranges, which includes ranges of iterators into std::set or std::map. For the difference, use std::set_difference.

这篇关于设定理论数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！