C++11新特性應用--介紹幾個新增的便利算法(用於排序的幾個算法)

C++11新特性應用--介紹幾個新增的便利算法(用於排序的幾個算法)

繼續C++11在頭文件algorithm中增加的算法。

至少我覺得，在stl的算法中，用到最多的就是sort了，我們不去探索sort的源碼，就是介紹C++11新增的幾個關於排序的函數。

對於一個序列，我們怎麼知道他是不是有序的呢？這就用到了：

is_sorted
原型：

template 
  ForwardIterator is_sorted_until (ForwardIterator first, ForwardIterator last);

template 
  ForwardIterator is_sorted_until (ForwardIterator first, ForwardIterator last,
                                   Compare comp);

作用：
排隊[first, last)是否有序。
這裡需要注意的是，有兩種原型。
第一種是默認的，即只有兩個參數，這樣是判斷[first, last)是否按升序排列，即<。
第二種是三個參數的，這樣是判斷[first, last)區間是否按comp進行排序的。

應用：

#include      // std::cout
#include      // std::cout
#include     // std::is_sorted, std::prev_permutation
#include         // std::array
bool compare(int a, int b)
{
    return a>b;   //升序排列，如果改為return a>b，則為降序
}
int main() {
    std::array foo{ 2,4,1,3 };
    std::array foo2{ 2,4,1,3 };
    do {
        // try a new permutation:
        std::prev_permutation(foo.begin(), foo.end());

        // print range:
        std::cout << "foo:";
        for (int& x : foo) std::cout << ' ' << x;
        std::cout << '\n';

    } while (!std::is_sorted(foo.begin(), foo.end()));

    std::cout << "the range is sorted!\n";


    do {
        // try a new permutation:
        std::prev_permutation(foo2.begin(), foo2.end());

        // print range:
        std::cout << "foo2:";
        for (int& x : foo2) std::cout << ' ' << x;
        std::cout << '\n';

    } while (!std::is_sorted(foo2.begin(), foo2.end(), compare));

    std::cout << "the range is Descending sorted!\n";

    return 0;
}
//輸出：
//  foo: 2 3 4 1
//  foo : 2 3 1 4
//  foo : 2 1 4 3
//  foo : 2 1 3 4
//  foo : 1 4 3 2
//  foo : 1 4 2 3
//  foo : 1 3 4 2
//  foo : 1 3 2 4
//  foo : 1 2 4 3
//  foo : 1 2 3 4
//  the range is sorted!
//  foo2 : 2 3 4 1
//  foo2 : 2 3 1 4
//  foo2 : 2 1 4 3
//  foo2 : 2 1 3 4
//  foo2 : 1 4 3 2
//  foo2 : 1 4 2 3
//  foo2 : 1 3 4 2
//  foo2 : 1 3 2 4
//  foo2 : 1 2 4 3
//  foo2 : 1 2 3 4
//  foo2 : 4 3 2 1
//  the range is Descending sorted!

這裡用到了一個全排列算法，不是C++11新增的內容，就不再贅述。
上面的代碼展示了兩種使用is_sorted的version。

另一一點需要注意的是：
如果范圍內的元素個數少於兩個，總是返回true.

is_sorted_until
原型：

template 
  ForwardIterator is_sorted_until (ForwardIterator first, ForwardIterator last);

template 
  ForwardIterator is_sorted_until (ForwardIterator first, ForwardIterator last,
                                   Compare comp);

作用：
Find first unsorted element in range
Returns an iterator to the first element in the range [first,last) which does not follow an ascending order.
If the entire range is sorted, the function returns last.
應用：

#include      // std::cout
#include     // std::is_sorted_until, std::prev_permutation
#include         // std::array

int main () {
  std::array foo {2,4,1,3};
  std::array::iterator it;

  do {
    // try a new permutation:
    std::prev_permutation(foo.begin(),foo.end());

    // print range:
    std::cout << "foo:";
    for (int& x:foo) std::cout << ' ' << x;
    it=std::is_sorted_until(foo.begin(),foo.end());
    std::cout << " (" << (it-foo.begin()) << " elements sorted)\n";

  } while (it!=foo.end());

  std::cout << "the range is sorted!\n";

  return 0;
}