Establish data structure theory

Question

I come from a fairly functional programming background, and I'm not used to C ++ (efficient) data structures. I need a data structure that stores several elements, as shown in a struct element . In the collection, the field identifier must be unique.

I want to make a very quick comparison, for example, in set theory, for example, when comparing the sets {x1,x2,x3} and {x4,x5} . I want to define a set of intersections {x5} (or {x2} that are equal in this case) and sets from other sets, for example, {x1,x2,x3} \ {x5} = {x1,x3} .

Is there ... a "set-theoretic" data structure 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}; 

Answer 1

Here is std::set , which implements dynamic sets (elements of dynamic tools can be inserted or deleted). For it to work with the element structure, you need a custom comparison function that only looks in id . Alternatively, you can use std::map<int, float> , which may better suit your problem.

To find the intersection of two sets, use the std::set_intersection . This requires sorted ranges, which include iterator ranges in std::set or std::map . For a difference use std::set_difference .

Answer 2

I just want to mention this, because when working with sets, it’s a really great data structure, but it’s not suitable for all your needs,

But still, you can keep in mind if you have requirements such as

1) The request to which the item belongs belongs

2) Combining various sets

Both in sublogarithmic time, that is, almost constant. Its called Disjoint set Data Structure http://en.wikipedia.org/wiki/Disjoint-set_data_structure

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

Design a std algorithm for operations that you can perform. http://www.cplusplus.com/reference/algorithm/