前向迭代器上的 stable_partition

问题描述

(见下文)

如果它确实只接受双向迭代器，为什么放弃了对前向迭代器的支持?

(See below)

If it indeed accepts only bidirectional iterators, why the support of forward iterators has been dropped?

Edit.

Found this clause:

So, only the second question remains.

解决方案

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.

这篇关于前向迭代器上的 stable_partition的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！