select_best: yet another partitioning algorithm

Question

The title is somewhat a misnomer; my apologies. The goal of the procedure is to partition a range of first, last by mid for the postcondition

max(first, mid) <= min(mid, last)

The actual code (best_n.h):

#include <algorithm>
#include <iterator>

#if !defined(BidirectionalIterator)
#define BidirectionalIterator typename
#endif

template <BidirectionalIterator I>
void select_best(I first, I mid, I last) {
    using T = typename I::value_type;
    while (first != mid) {
        T pivot = *first;
        I pp = std::partition(first, last, [pivot](T elt) { return elt < pivot; });
        if (pp == first) std::advance(pp, 1);
        if (std::distance(first, pp) > std::distance(first, mid)) last = pp;
        else                                                      first = pp;
    }
}

Works fine if I didn't mistype anything.

Questions:

• Seeking overall improvements.
• What is a right name?
• Currently void. Is there anything useful to return?
• I don't like passing lambda to std::partition. Any suggestions to avoid it?
• A performance is weird. Regardless of a pivot selection strategy, an execution time stays pretty much constant as a function of mid. Obviously outperforms std::partial_sort for somewhat sizable initial ranges, but loses badly for short ones. Any suggestions?

PS: I have benchmarks if anybody's interested.

PPS: I am well aware of the beautiful best 2 Stepanov's approach. Challenging everybody to generalize it.

Answer 1

A couple of points on the style rather than the algorithm itself.

First, I find the #ifdef for the typename peculiar, it detracts from clarity, and is a pointless use of macros, it may be fine for a small snippet but in a large project or a library header such a thing can wreak havoc. Consider simply,

template <class BidirectionalIterator>

That said, note that C++11 relaxes std::partition to a ForwardIterator, so I would simply say,

template <class ForwardIterator>
void select_best(ForwardIterator first, ForwardIterator mid, ForwardIterator last);

The type T is also a bad choice to denote a value_type, it has too much baggage as a template parameter. Simply say,

using value_type = typename I::value_type;

Then consider avoiding the inadvertent copy of the value by changing the code to take a const reference of the pivot,

const T& pivot = *first;

The lambdas are arguably the preferred way to write the predicate (let's not venture into std::bind and std::min territory), but again I would capture the value by a reference to avoid a copy, and be less verbose,

[&](const T& elt) { return elt < pivot; }

Consider either using brackets with if-else clauses or at least put the conditional statement on a separate line.

if ( ... )
    statement;
else    

note that using std::distance implies that complexity of your function can blow up to O(n) for that use only (where n is the pp, somewhere around N/2), and if you want O(1) for the distance calculation you have to make sure your iterators are random access.

and last, please get rid of the ghastly space in else first = pp;.

For your question on the return value, would it be useful to return pp itself?