Re: std::set
From: tom_usenet (tom_usenet_at_hotmail.com)
Date: 07/13/04
- Next message: Richard Herring: "Re: Instantiation of classes"
- Previous message: Karl Heinz Buchegger: "Re: atoi problem"
- In reply to: ma740988: "std::set"
- Next in thread: ma740988: "Re: std::set"
- Reply: ma740988: "Re: std::set"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Tue, 13 Jul 2004 15:44:22 +0100
On 13 Jul 2004 05:28:17 -0700, ma740988@pegasus.cc.ucf.edu (ma740988)
wrote:
>The position returned via the STL std::set container never made much
>sense to me. When you insert elements within the container, the
>position returned - via find - does not reflect the actual position of
>the value within the container.
It is an iterator to the element - it reflects the exact position of
the element in the container.
> std::string - for instance - does.
>How then do I get the actual position of the value when using
>std::set?
What do you mean by "position"? I think you are trying to say "index",
in which case, index doesn't make all that much sense for a set, since
it isn't a sequence container. If you want to know where the element
lies in the sort order of the container, you can find out using
std::distance. e.g.
pos = s.insert(40).first;
int sortPosition = std::distance(s.begin(), pos); //O(pos) operation.
>my_string.find ('c') returns 2 for the position which makes sense.
>cc.find(40) on the other hand 'returns' the contents at the position
>not the actual position.
No, it returns an iterator, which *is* a position.
>Consider:
>std::set<int, greater<int> > mySet;
>mySet.insert (10);
>mySet.insert (40);
>mySet.insert (50);
>mySet.insert (35);
>mySet.insert (30);
>
>Based on the sort criteria, could I get a 'write up' - of sorts on
>how/when the actual 'sorting' happens?
The complexity and iterator requirements of std::set means that it is
always implemented as some kind of balanced tree structure, usually a
red-black tree. No sorting happens, the container stores inserts the
element into the appropriate position in the tree to maintain the
invariants of the tree, jiggling the nodes if necessary (which is
usually called "rebalancing").
>I envision per my reading of the C++ Std Library.
>10 gets inserted.
>40 gets inserted. Since 40 is greater than 10, 40 gets moved to the
>'top'.
What do you mean by "top"? The root of the tree? Or are you thinking
of a list?
>50 gets inserted. Since 50 is greater than 10 && 50 greater than 40,
>50 gets moved to the top. This describes the 'transitive' behavior of
>strick weak ordering.
>and so on ...?
Elements in sets never get moved (unless you count rebalancing as
moving). It is just that new elements get inserted in the correct
place.
>At some point I suspect I'll peruse the source (if avaibable) of
>std::set since I'm also not sure (but curious) of how the 'motor
>operates' - if you will.
>Take the case again where 50 gets inserted. This much is true,
>there's an operator() for the criteria, however, is it safe to state
>that operator() is called twice? Once to compare 50 against 10, and a
>second time to compare 50 against 40, except I now feel like I'm
>headed towards logarithimic complexity versus linear versus .. can't
>recall the other one.
Insertion is linear. Basically, the code walks down the tree towards
the bottom until it finds the correct location. The depth of the tree
is O(log size()), so insertion takes only O(log size() ) comparisons.
Read up on red-black trees. Implementing your own would be an
educational experience.
Tom
- Next message: Richard Herring: "Re: Instantiation of classes"
- Previous message: Karl Heinz Buchegger: "Re: atoi problem"
- In reply to: ma740988: "std::set"
- Next in thread: ma740988: "Re: std::set"
- Reply: ma740988: "Re: std::set"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
