`<algorithm>`: `std::ranges::partition` falls back to forward algorithm for non-common bidirectional ranges

[mirion-dev]

Describe the bug

According to [alg.partitions#8.1], the algorithm should perform at most N / 2 swaps if the iterator models bidirectional_iterator.

However, the current implementation checks _Bidi_common, restricting the bidirectional path to common ranges. For non-common ranges, it falls back to the forward algorithm.

For reference, libstdc++ and libc++ handle this case correctly.

Test case

#include <algorithm>
#include <cassert>
#include <ranges>
#include <vector>

struct T {
    int value;

    static inline int count{};

    friend void swap(T& a, T& b) {
        std::swap(a.value, b.value);
        ++count;
    }
};

struct Se {
    std::vector<T>::iterator iter;

    bool operator==(std::vector<T>::iterator other) const {
        return iter == other;
    }
};

int main() {
    std::vector<T> v{ { 1 }, { 2 }, { 4 }, { 6 } };
    std::ranges::partition(v.begin(), Se{ v.end() }, [](auto& x) { return x.value % 2 == 0; });
    assert(T::count <= 2);
}

Expected behavior

assert succeeded.

STL version

Microsoft (R) C/C++ Optimizing Compiler Version 19.50.35718 for x64