Re: STL: how to get the sequence number of a newly added item into a set
"bilgekhan" <bilgekhan@bilgekhanbilgekhan.net.tr> wrote:
"Daniel T." <daniel_t@earthlink.net> wrote:
"bilgekhan" <bilgekhan@bilgekhanbilgekhan.net.tr> wrote:
After doing a succcessful insert() or find() on a set<T> container
is it possible to get the item number of this item in the set?
(ie. its zero-based sequence number (position/location/rank/index)
within the sorted collection)
Additional info:
insert() returns a pair<T> and find() returns an iterator.
Using any of these two objects is it possible to get the
sequence number of the item these objects point to?
After the insert() or find() the container won't be modified.
set<int>::iterator it = s.insert( x ).first;
// or = s.find( x );
int seqNumb = distance( s.begin(), it );
Yes, distance() does what I wanted, but it is VERY slow!
It seems each time it walks all items from the beginning to the
item in question, ie. it practically does a find().
How else could it be done?
FYI: If I program this without STL (and then even using an unordered array
--> ie. each time doing a sequential search) then it is about 7 times
faster than the STL version that uses set<T> and distance() !
How come? :-)
Your comparing apples to oranges. In one implementation you are using an
unordered array where all the elements are contiguous, in the other
implementation the elements are ordered but not contiguous. But before
abandoning the set idea, make sure you have all optimizations turned on.
Many standard libraries have extensive error checking built in and make
a lot of calls that can be inlined, but the former doesn't get removed
and the latter doesn't get inlined unless optimizations are turned on.
The culprit is IMO the distance() call. One needs a better, a direct,
method without traversing the tree.
Like how?
A better way would have been if the insert() and find() functions would
optionally deliver the distance value on the fly
They would have to traverse the tree to do that.
As others have pointed out, "sequence numbers" aren't all that useful in
sets. It sounds like you would be better served by using a std::vector
and sorting it (using std::sort,) then you can do lookups with
std::lower_bound, upper_bound, equal_range, and binary_search and
getting the "sequence number" is simply a matter of a little pointer
math.