C++ is_sorted(STL is_sorted)排序演算法詳解

排序是要耗費時間的，尤其是在有大量元素時。測試元素段是否已經排好序可以避免不必要的排序操作。如果兩個疊代器引數所指定範圍內的元素是升序排列的，函數模板 is_sorted() 就會返回 true。

為了能夠順序處理元素，疊代器至少需要是正向疊代器。提醒一下，正向疊代器支援字首和字尾形式的自增運算。下面是一個使用 is_sorted() 的範例：

std::vector<int> numbers {22, 7, 93, 45, 19};
std::vector<double> data {1.5, 2.5, 3.5, 4.5};
std::cout << "numbers is "<<(std::is_sorted(std::begin (numbers), std::end(numbers)) ? "": "not ") << "in ascending sequence.n";
std::cout << "data is "<< (std::is_sorted(std::begin(data), std::end(data)) ?"":"not ") << "in ascending sequence." << std::endl;

預設使用的比較函數是 < 運算子。鑑於“data is”的輸出，表明 numbers 不是一個升序序列。還有一個版本也可以指定用於比較元素的函數物件：

std:: cout << "data reversed is "<< (std::is_sorted(std::rbegin(data), std::rend(data), std::greater<>()) ? "":"not ")<< "in descending sequence." << std::endl;

這條語句的輸出說明 data 中元素的逆序是降序。

也可用函數模板 is_sorted_until() 來判斷一個元素段是否有序。它的引數用來定義要測試的疊代器。這個函數會返回一個指向這段元素中升序序列上邊界元素的疊代器。例如：

std::vector<string> pets {"cat", "chicken", "dog", "pig", "llama", "coati", "goat"};
std::cout << "The pets in ascending sequence are:n";
std::copy(std::begin(pets), std::is_sorted_until(std::begin(pets), std::end (pets)) , std::ostream_iterator<string>{ std::cout," "});

copy() 演算法的前兩個引數分別是pets容器的開始疊代器以及當 is_sorted_until() 應用到 pets 中全部元素上時返回的疊代器。is_sorted_until() 演算法會返回指向 pets 中升序序列元素的上邊界，它是指向小於其前面元素的第一個元素的疊代器。如果序列是有序的，則返回一個結束疊代器。這段程式碼的輸出如下：

The pets in ascending sequence are:
cat chicken dog pig

"llama"是小於其前者的第一個元素，所以”pig”就是升序序列的第一個元素。

可以選擇提供一個用於比較元素的函數物件：

std::vector<string> pets {"dog", "coati", "cat", "chicken", "pig", "llama", "goat"};
std::cout << "The pets in descending sequence are:n";
std::copy(std::begin(pets),std::is_sorted_until(std::begin(pets), std::end (pets) , std::greater<>()),std::ostream_iterator<string>{ std::cout," "});

這一次我們會查詢降序元素，因為使用的是 string 類的成員函數 operator>() 來比較元素。輸出為：

The pets in descending sequence are:
dog coati cat

"chicken" 是大於其前者的第一個元素，所以 is_sorted_until() 返回的疊代器就指向這個元素，因而 "cat" 是降序序列的最後一個元素。