in include/range/v3/algorithm/stable_partition.hpp [145:228]
static I impl(I begin, I end, C pred, P proj, D len, Pair p, concepts::BidirectionalIterator *bi)
{
// *begin is known to be false
// *end is known to be true
// len >= 2
if(len == 2)
{
ranges::iter_swap(begin, end);
return end;
}
if(len == 3)
{
I tmp = begin;
if(pred(proj(*++tmp)))
{
ranges::iter_swap(begin, tmp);
ranges::iter_swap(tmp, end);
return end;
}
ranges::iter_swap(tmp, end);
ranges::iter_swap(begin, tmp);
return tmp;
}
if(len <= p.second)
{ // The buffer is big enough to use
using value_type = iterator_value_t<I>;
std::unique_ptr<value_type, detail::destroy_n<value_type>> h{p.first, {}};
// Move the falses into the temporary buffer, and the trues to the front of the line
// Update begin to always point to the end of the trues
auto buf = ranges::make_counted_raw_storage_iterator(p.first, h.get_deleter());
*buf = iter_move(begin);
++buf;
auto res = partition_move(next(begin), end, begin, buf, std::ref(pred), std::ref(proj));
begin = std::get<1>(res);
// move *end, known to be true
*begin = iter_move(std::get<0>(res));
++begin;
// All trues now at start of range, all falses in buffer
// Move falses back into range, but don't mess up begin which points to first false
move(p.first, std::get<2>(res).base().base(), begin);
// h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
return begin;
}
// Else not enough buffer, do in place
// len >= 4
I middle = begin;
D half = len / 2; // half >= 2
advance(middle, half);
// recurse on [begin, middle-1], except reduce middle-1 until *(middle-1) is true, *begin know to be false
// F????????????????T
// f m l
I m1 = middle;
I begin_false = begin;
D len_half = half;
while(!pred(proj(*--m1)))
{
if(m1 == begin)
goto first_half_done;
--len_half;
}
// F???TFFF?????????T
// f m1 m l
begin_false = stable_partition_fn::impl(begin, m1, pred, proj, len_half, p, bi);
first_half_done:
// TTTFFFFF?????????T
// f ff m l
// recurse on [middle, end], except increase middle until *(middle) is false, *end know to be true
m1 = middle;
len_half = len - half;
while(pred(proj(*m1)))
{
if(++m1 == end)
return ranges::rotate(begin_false, middle, ++end).begin();
--len_half;
}
// TTTFFFFFTTTF?????T
// f ff m m1 l
I end_false = stable_partition_fn::impl(m1, end, pred, proj, len_half, p, bi);
// TTTFFFFFTTTTTFFFFF
// f ff m sf l
return ranges::rotate(begin_false, middle, end_false).begin();
// TTTTTTTTFFFFFFFFFF
// |
}