please wait
- Forum
- General C++ Programming
- About sets of sets (set< set < KEY> >)
About sets of sets (set< set < KEY> >)
Nov 23, 2009 at 5:03pm
Creating a set of sets of <X> is possible, since operator < is already overloaded within STL's set class. (So please don't write an example program showing me it is possible). I'm trying to find out if this is a reliable container for a large scale program (you'll understand why later on). As far as I know, STL's set inserts the elements in a tree, according to it's key.
Mathemathically speaking, given two sets A and B, one, and only one of the following situations will happen A=B (every a from A is in B, and every b of B is in A) or A != B (At least one a from A is not in B or vice-versa). It makes no sense saying A<B or B<A (The closest thing you can say |A|<|B|, where |A|, and |B| represents the ammount of elements in A, and in B, respectively). That's why a tree implementation for a set of sets is mathematically absurd (you wouldn't make advantage of the tree. I'll explain this later on).
However, it's still possible to overload the operator < for sets and yet, make some sense. For instance:
Remember this implementation, since we'll use it later on.
Since STL's set uses a tree implementation of the data, this would only work correctly if comparisons within the insertions, searches and deletions are done in the same order (for example, "searched key" is compared to the "actual-tree"'s key (Actual = Searched, actual and searched are sets). If not found yet, we go to the "left sub-tree" (if Actual != Searched then //go to left sub tree). If not found yet, we go to the "right sub-tree"( Actual != Searched -> This situation will never happen).
If this works, we would have a list of sets, which works pretty much allright. The problem comes here: If set's data tree is rebalanced after each insertion, we'll lose permanently the access to several sets of data, due to the nature of the operator < overload.
That's why I am asking: Is it a good idea to use set < set <KEY> > in a large scale program?
Mathemathically speaking, given two sets A and B, one, and only one of the following situations will happen A=B (every a from A is in B, and every b of B is in A) or A != B (At least one a from A is not in B or vice-versa). It makes no sense saying A<B or B<A (The closest thing you can say |A|<|B|, where |A|, and |B| represents the ammount of elements in A, and in B, respectively). That's why a tree implementation for a set of sets is mathematically absurd (you wouldn't make advantage of the tree. I'll explain this later on).
However, it's still possible to overload the operator < for sets and yet, make some sense. For instance:
|
|
Remember this implementation, since we'll use it later on.
Since STL's set uses a tree implementation of the data, this would only work correctly if comparisons within the insertions, searches and deletions are done in the same order (for example, "searched key" is compared to the "actual-tree"'s key (Actual = Searched, actual and searched are sets). If not found yet, we go to the "left sub-tree" (if Actual != Searched then //go to left sub tree). If not found yet, we go to the "right sub-tree"( Actual != Searched -> This situation will never happen).
If this works, we would have a list of sets, which works pretty much allright. The problem comes here: If set's data tree is rebalanced after each insertion, we'll lose permanently the access to several sets of data, due to the nature of the operator < overload.
That's why I am asking: Is it a good idea to use set < set <KEY> > in a large scale program?
Last edited on Nov 23, 2009 at 5:06pm
Nov 23, 2009 at 5:44pm
No, because the operator< overload you have posited does not mean the strict weak ordering requirement.
http://www.sgi.com/tech/stl/set.html
http://www.sgi.com/tech/stl/set.html
Nov 23, 2009 at 6:01pm
I already know it idoes not meet the weak ordering requeriment. However, defining it as I've done, is perfectly valid if the tree they used is not rebalanced, and the search method is the same for insertions/deletions/etc...
I just don't know how the guys who made the STL created set: it is possible to instantiate the template as set < set <int> > and it seems to work properly on small-scale programs. (with 3 or 4 sets of ints). I'm talking about introducing 100-10000 sets of ints.
EDIT: Simplifying the question:
Does STL's set rebalance the tree on which it stores the data?
I just don't know how the guys who made the STL created set: it is possible to instantiate the template as set < set <int> > and it seems to work properly on small-scale programs. (with 3 or 4 sets of ints). I'm talking about introducing 100-10000 sets of ints.
EDIT: Simplifying the question:
Does STL's set rebalance the tree on which it stores the data?
Last edited on Nov 23, 2009 at 9:06pm
Nov 24, 2009 at 11:48am
The short answer is no, unless there was a specific reason to do so. In general, you wouldn't have a container of a container of objects. The cost of copies may be high and can be entirely avoided.
Nov 25, 2009 at 4:09pmThe cost of copies may be high and can be entirely avoided. |
Well, theoretically, STL's "set" does not insert elements that have already been inserted (In fact, that's what "multiset" is for : inserting sets of elements with key-duplicity).
This question seems to be somewhat strange and obscure. None of my lecturers knew the answer, so I don't expect a precise answer on how the STL works.
Anywas, thank you all for your contributions to the topic.
Nov 25, 2009 at 4:35pm
From experience, you cannot create ordered containers with a comparator that does not meet the strict weak ordering requirement. While you may find an STL implementation for which this works, it is not portable.
Most STL implementations use RB trees, which are self balancing.
Most STL implementations use RB trees, which are self balancing.
Topic archived. No new replies allowed.