STL set question

[Stefan Istrate]

How can I find the k-th position in a STL set? I want to do this in
O(logN) time, where N is the dimension of the set.
Thank you!

 

[Victor Bazarov]

How can I find the k-th position in a STL set? I want to do this in
O(logN) time, where N is the dimension of the set.

I don't think it's possible. The only way I know (without going
into the implementation) is to 'advance' the 'begin()' iterator
'k' times. That's O(k) time, most likely amortized. To make it
better you have to rely on a certain implementation of the list,
which isn't specified (although could be deduced, probably).

V

 

[James Kanze]

I don't think it's possible. The only way I know (without
going into the implementation) is to 'advance' the 'begin()'
iterator 'k' times. That's O(k) time, most likely amortized.
To make it better you have to rely on a certain implementation
of the list, which isn't specified (although could be deduced,
probably).

From time to time, it is suggested to use a sorted vector
instead of a set. Depending on what he's doing with it, it may
even be faster as well. Generally, insertions and deletions
are slower, lookups, using lower_bound, are faster. But there
are exceptions to even this rule. And of course, finding the
nth element is clearly O(1), with a very, very small constant
term as well.

 

[Victor Bazarov]

From time to time, it is suggested to use a sorted vector
instead of a set. Depending on what he's doing with it, it may
even be faster as well. Generally, insertions and deletions
are slower, lookups, using lower_bound, are faster. But there
are exceptions to even this rule. And of course, finding the
nth element is clearly O(1), with a very, very small constant
term as well.

One of the ways we combined the two in our practice is to form
the collection in a set and then copy it into a vector. The
copying is O(N). Of course this means huge savings iff the
"formation" (insertions) happens before the "use" (lookups).
Not all algorithms can be massaged into that scheme, but those
that can gain significantly.

V

 

[Joe Greer]

One of the ways we combined the two in our practice is to form
the collection in a set and then copy it into a vector. The
copying is O(N). Of course this means huge savings iff the
"formation" (insertions) happens before the "use" (lookups).
Not all algorithms can be massaged into that scheme, but those
that can gain significantly.

V

Does that turn out faster than just pushing them onto the vector and
doing one sort at the end or when lookup is needed? I hadn't really
thought of bringing two collections into play like this before. My gut
instinct thinks that the allocations involved in the set would out
weight the benefits if you delayed the sort until a lookup was
requested. I haven't done any tests though.

joe

 

[Victor Bazarov]

Does that turn out faster than just pushing them onto the vector and
doing one sort at the end or when lookup is needed?

Not sure. Perhaps this is even better. The only reason I think I
would need to have them in the set to begin with is to perform some
/rare/ lookups during the process of inserting the new ones. This
is better than re-sorting the vector after every insertion or having
to insert in the middle.

I hadn't really
thought of bringing two collections into play like this before. My
gut instinct thinks that the allocations involved in the set would out
weight the benefits if you delayed the sort until a lookup was
requested. I haven't done any tests though.

Yes, I think your gut instinct is spot on, except when some lookups
are still needed during the formation process.

V