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!
O(logN) time, where N is the dimension of the set.
Thank you!
-
-
Re: STL set question
Stefan Istrate wrote:I don't think it's possible. The only way I know (without goingHow 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.
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
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
-
Re: STL set question
On Feb 20, 12:10 am, "Victor Bazarov" <v.Abaza...@com Acast.netwrote:Stefan Istrate wrote: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.From time to time, it is suggested to use a sorted vectorI 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).
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:-).
--
James Kanze (GABI Software) email:james.kan ze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Comment
Comment