stable_partition on forward iterators

Question

1. In the current standard draft the specification of std::stable_partition is:

template<class BidirectionalIterator, class Predicate>
BidirectionalIterator stable_partition(
    BidirectionalIterator first, BidirectionalIterator last, Predicate pred);

I didn't find the requirement that BidirectionalIterator should be a bidirectional iterator, but the name suggests so. (See below)

2. In the SGI STL, the specification is:

template <class ForwardIterator, class Predicate>
ForwardIterator stable_partition(
    ForwardIterator first, ForwardIterator last, Predicate pred);

Requirements on types: ForwardIterator is a model of Forward Iterator.

The specification of complexity is the same for both, current standard and SGI, versions: at most N log N swaps, only O(N) swaps if there is enough extra memory and exactly N applications of the predicate and projection.

3. The declaration in libstdc++ and libc++ looks like:

template<typename ForwardIterator, typename Predicate>
ForwardIterator stable_partition(
    ForwardIterator first, ForwardIterator last, Predicate pred);

In GCC and Clang std::stable_partition indeed works with forward iterators. For example:

int main() {
    std::forward_list<int> list{1, 4, 5, 2, 3, 0};
    std::stable_partition(list.begin(), list.end(), [](int i) { return i < 3;});

    for (auto v : list)
        std::cout << v << ' ';
}

compiles and produces the correct output. Microsoft's compiler fails to compile this code (no -- operator). Intel's one succeeds.

I have two related questions:

• Does std::stable_partition accepts at least bidirectional iterators by the standard or the name BidirectionalIterator is misleading?
• If it indeed accepts only bidirectional iterators, why the support of forward iterators has been dropped?

Edit.

Found this clause:

If an algorithm's template parameter is named BidirectionalIterator, BidirectionalIterator1, or BidirectionalIterator2, the template argument shall meet the Cpp17BidirectionalIterator requirements.

So, only the second question remains.

Answer 1

First of all, no support has been dropped, std::stable_partition has always required BidirectionalIterator by the standard. Which does not mean that the implementors of the library are disallowed to give less restrictions on input arguments (if it continues to comply with other parts of the standard ofc). And so Gcc, Clang and Intel use their rights and made the code even more generic. You can think of it as a compiler extension of standard library.

Having said that one may ask why standard requires BidirectionalIterator here. I suppose it is possible because the authors of the standard didn't see a way to comply with the complexity requirements without this requirement. It is possible that the authors of gcc found a way to do it better than anticipated by the standard. Looking at the gcc source code kinda confirms this. https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_algo.h#L1613

EDIT:

I have dug through GCC library implementation and I think I get it. Implementation for ForwardIterator, BidirectionalIterator and RandomAccessIterator are different for std::stable_partition. This is due to different implementations of std::rotate which is used by the partitioning algorithm. And so, for forward iterator number of swaps is greater and can exceed (last - first) * log(last - first). Look here and here.

Answer 2

The problem seems to have historical and not mathematical reasons. Looking through Alexander Stepanov's papers, I found this one: "Partition and Related Functions".

It contains the following passage:

Remark: It is interesting that this excellent algorithm is not in the C++ standard which requires bidirectional iterators for partition. I had known, implemented, and taught this algorithm for quite some time – since I first read about it in Bentley’s column in CACM in the mid-eighties. But my original STL proposal does, somehow, specify bidirectional iterators for both partition and stable_partition. Both of them were corrected in SGI STL, but most vendors are still behind. This little thing has been bothering me for over 10 years now; the most bothersome part being the fact of omission. How did it happen? I suspect that the explanation is quite simple: while in the early 90ties I already understood the idea of reducing every algorithms to its minimal requirements, and I also knew that the same operation could be implemented using better algorithms when we know more about the data to which they are applied, I was not yet fully aware of the need to provide an algorithm for the weakest case, if such an algorithm is available. It took several more years to understand the importance of “filling the algorithmic space.”

The following simple algorithm

template <typename I, // I models Forward Iterator
          typename N, // N models Integer
          typename P> // P models Unary Predicate
pair<I, I> stable_partition_inplace_n(I f, N n, P p)
{
    if (n == 0) return make_pair(f, f);
    if (n == 1) {
        I l = successor(f);
        if (p(*f)) l = f;
        return make_pair(f, l);
    }
    pair<I, I> i = stable_partition_inplace_n(f, n/2, p);
    pair<I, I> j = stable_partition_inplace_n(i.second, n – n/2, p);
    return make_pair(rotate(i.first, i.second, j.first), j.second);
}

is given in that paper. It works with forward iterators and performs O(N log N) swaps in the worst case.