std::next_permutation实现解释似乎效率不高

Question

我很好奇std:next_permutation是如何实现的，所以我提取了gnu libstdc++ 4.7版本，并清理了标识符和格式，以生成以下演示…

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
template<typename It>
bool next_permutation(It begin, It end)
{
    if (begin == end)
            return false;
    It i = begin;
    ++i;
    if (i == end)
            return false;
    i = end;
    --i;
    while (true)
    {
            It j = i;
            --i;
            if (*i < *j)
            {
                    It k = end;
                    while (!(*i < *--k))
                            /* pass */;
                    iter_swap(i, k);
                    reverse(j, end);
                    return true;
            }
            if (i == begin)
            {
                    reverse(begin, end);
                    return false;
            }
    }

}

  int main()
 {
             vector<int> v = { 1, 2, 3, 4 };
    do
    {
            for (int i = 0; i < 4; i++)
            {
                    cout << v[i] << " ";
            }
            cout << endl;
    }
    while (::next_permutation(v.begin(), v.end()));

}

我的问题是:

while (!(*i < *--k))
  /* Iterating linearly */;

为什么我们不能做一个二进制搜索，而不是一个朴素的线性迭代作为序列从[i+1, end)是递减顺序?这将提高搜索的效率。"algorithm.h"中的标准函数怎么能忽略这样一个导致更好的性能和效率的事情?

Answer 1

您很少会有一个包含超过15个元素(实际上甚至更少)的数组，因为这将需要您处理15个元素!> 10^12种不同的排列。对于如此小的数组，二进制搜索的效率低于简单的线性搜索。