What is the algorithmic (time) complexity of std::next and std::nth_element for a std::multiset in C++? I am interested in the latest gcc implementation, in particular, if it matters. I have a set of numbers in std::multiset and I need to compute their median. I have a feeling that it should be possible to do it in O(log N) for a balanced binary tree (or even in O(1) if the tree is perfectly balanced and, so the median element is at the root of the tree).
using Set = std::multiset<double>;
const Set x = {/*some numbers*/};
if(x.empty()) return 0;
const Set::size_type size = x.size();
const Set::size_type size2 = size/2;
const Set::const_iterator it = std::next(x.begin(), size2);
return size%2==1 ? *it : 0.5*(*std::next(it,-1) + *it);
If the numbers were in a std::vector, I could do it in O(1). To find Nth element in a std::multiset I use std::next, but I am thinking if std::nth_elment could be better (I hope they both use the fact that std::multiset is sorted).
If what I am doing to compute the median is not optimal, please, advise on a better way to do it.
Thank you very much for your help!
std::next is O(k) in the distance you move.
There is no other way to get the median, practically, if you have a multiset.
It is possible to write a more efficient advance operation on containers like this, but std does not contain it.
You could keep around two multisets and balance them using splicing operations such that the median is always the first element of the 2nd container. This will have asymptotically good performance characteristics.
It could make other operations a bit more of a pain.