// <algorithm> 
// 默认(1)    
template <class BidirectionalIterator>
    bool prev_permutation (
        BidirectionalIterator first,
        BidirectionalIterator last );
// 自定义(2)    
template <class BidirectionalIterator,
    class Compare>
    bool prev_permutation (
        BidirectionalIterator first,
        BidirectionalIterator last,
        Compare comp);

返回给定范围中的元素组成的上一个按字典序的排列。

该函数等价于:

template<class _BidIt,
class _Pr> inline
    bool _Prev_permutation(_BidIt _First, _BidIt _Last, _Pr _Pred)
{	// reverse permute and test for pure descending, using _Pred
    _BidIt _Next = _Last;
    if (_First == _Last || _First == --_Next)
        return (false);

    for (;;)
    {	// find rightmost element not smaller than successor
        _BidIt _Next1 = _Next;
        if (_DEBUG_LT_PRED(_Pred, *_Next1, *--_Next))
        {	// swap with rightmost element that's not smaller, flip suffix
            _BidIt _Mid = _Last;
            for (; !_DEBUG_LT_PRED(_Pred, *--_Mid, *_Next);)
                ;
            _STD iter_swap(_Next, _Mid);
            _STD reverse(_Next1, _Last);
            return (true);
        }

        if (_Next == _First)
        {	// pure ascending, flip all
            _STD reverse(_First, _Last);
            return (false);
        }
    }
}
  • firstlast

    分别指向序列中初始及末尾位置的双向迭代器(Bidirectional Iterators)。这个范围即 [first,last) ,包括 first 到 last 间的所有元素,包括 first 指向的元素,但不包括 last 指向的元素。

    comp

    二元谓词(Binary)函数,以范围中的两个元素为参数,然后返回一个可转换成 bool 类型的值。

    其返回值表明按所指定的严格弱序排序(Strict weak ordering)时,第一个参数所传进来的元素是否在第二个参数所传进来的元素前面。

    该函数不能修改其参数。

    可以是函数指针(Function pointer)类型或函数对象(Function object)类型。

  • 如果能重排生成更小的字典序(Lexicographically)排列,则返回 true

    否则,返回 false

  • 参照 std::sort 以获得与自定义函数谓词、函数对象谓词、对象数组、lambda 表达式 C++11、初始化列表 std::initializer_list C++11 等相关的例子。

    例 1

    #include <iostream>
    #include <algorithm>
    #include <iterator>
    #include <vector>
    
    
    namespace ClassFoo{
        void PrevPermutation_1() {
            std::vector<int> foo;
            foo.push_back(6);
            foo.push_back(5);
            foo.push_back(4);
            do{
                // 打印 foo
                std::copy(
                    foo.begin(),
                    foo.end(),
                    std::ostream_iterator<int>(std::cout, " "));
                std::cout << std::endl;
            } /* 返回下一组排列 */
            while (std::prev_permutation(foo.begin(), foo.end()));
        }
    }
    int main()
    {
        ClassFoo::PrevPermutation_1();
        return 0;
    }

    6 5 4
    6 4 5
    5 6 4
    5 4 6
    4 6 5
    4 5 6

  • 复杂度

    O(N/2)N 等值于 std::distance(first,last)

    数据争用相关

    修改在范围 [first,last) 中的元素。

    异常安全性相关

    如果元素交换(Swap)、或操作某个迭代器抛异常,该函数才会抛异常。

    注意 无效参数将导致未定义行为(Undefined behavior)