頭文件 <boost/algorithm/minmax.hpp> 頭文件 <boost/algorithm/minmax.hpp> 動機
概要
函數模板說明
定義
對類型的要求
前提條件
後置條件
複雜度
例子
備註
原理
性能說明
鳴謝
minmax 庫由兩個頭文件組成，
<boost/algorithm/minmax.hpp> 和 <boost/algorithm/minmax_element.hpp>(請見 原理)。這個庫解決了以下問題，即同時進行 min 和 max 計算只需要一次比較，而使用 std::min 和 std::max 則要兩次比較。更糟的是，計算 n 個元素中的最小和最大元素只需要 3n/2+1 次比較，而使用 std::min_element 和 std::max_element 則要 2n 次(計算兩遍)。我一直認為計算一個區間的邊界要調用兩個函數是一種浪費，這需要執行兩次輸入，而其實一次就夠了。這個庫解決了以上兩個問題。第一個文件實現了函數模板 minmax，它只是對C++標準的簡單的擴展。由於它返回一對 const&, 所以我們必須使用 Boost.tuple 庫來構造這對 const&. (請注意：目的不是修正 std::min 和 std::max 的缺省行為，而是增加一個組合它們兩個的算法；請看 原理)
第二個文件實現了函數模板 minmax_element. 另外，它還提議了一些 minmax 算法不能計算的變量，而且在有相等元素的情況時也更靈活。這些變量也可以用基於策略的設計來提供，不過我否決了這種方法(請見 原理)。
如果你關心 性能，你可以看到 minmax_element 只是比單個的 min_element 或 max_element 效率低一點點，即幾乎兩倍效率於兩次獨立的 min_element 和 max_element 調用。從理論觀點來看，minmax_element 函數執行最多 3n/2+1 次比較和正好 n 次 ForwardIterator 遞增。
#include <boost/tuple/tuple.hpp>
namespace boost {
template <class T>
tuple<T const&, T const&> >
minmax(const T& a, const T& b);
template <class T, class BinaryPredicate>
tuple<T const&, T const&> >
minmax(const T& a, const T& b, BinaryPredicate comp);
}
#include <utility> // for std::pair另外，還有幾個函數模板用於在有相等元素的情況下得到你想要的元素。它們是：
namespace boost {
template <class ForwardIterator>
std::pair<ForwardIterator,ForwardIterator>
minmax_element(ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class BinaryPredicate>
std::pair<ForwardIterator,ForwardIterator>
minmax_element(ForwardIterator first, ForwardIterator last,
BinaryPredicate comp);
}
minmax_element 語義上等同於 first_min_first_max_element.
First_min_element 和 first_max_element 在區間 [first, last) 中查找最小和最大的元素。如果有多個滿足條件的元素，則返回第一個。它們等同於 std::min_element 和 std::max_elementand，只是在本庫中是同時執行的。
Last_min_element 和 last_max_element 在區間 [first, last) 中查找最小和最大的元素。它們基本上等同於 std::min_element 和 std::max_elementand，只是返回最後一個最大/最小元素(而不是象 first_min_element 和 first_max_element 那樣返回第一個)。
這組算法中包含了 first_min_first_max_element, first_min_first_max_element, first_min_first_max_element, 和 first_min_first_max_element，它們可以描述如下(用 which 和 what 表示 first 或 last): which_min_what_max_element 在區間 [first, last) 中查找 (first 或 last, 取決於 which) 最小和 (first 或 last, 取決於 what) 最大的元素。第一個版本的語義等同於：
std::make_pair(boost::which_min_element(first,last),而第二個版本則等同於：
boost::what_max_element(first,last)),
std::make_pair(boost::which_min_element(first,last,comp),
boost::what_max_element(first,last,comp)).
注: first_min_last_max_element 也可以解釋為在區間中查找第一個和最後一個元素，如果該區間已被穩定排序。
對於其它所有函數模板的兩個模板參數的版本：
所有其它算法的複雜度均為線性。它們都執行剛好 n 次遞增操作，如果 [first,last) 為空則沒有執行比較操作，否則：
int main()
{
using namespace std;
boost::tuple<int const&, int const&> result1 = boost::minmax(1, 0);
assert( result1.get<0>() == 0 );
assert( result1.get<1>() == 1 );
list<int> L;
generate_n(front_inserter(L), 1000, rand);
typedef list<int>::const_iterator iterator;
pair< iterator, iterator > result2 = boost::minmax_element(L.begin(), L.end());
cout << "The smallest element is " << *(result2.first) << endl;
cout << "The largest element is " << *(result2.second) << endl;
assert( result2.first == std::min_element(L.begin(), L.end());
assert( result2.second == std::max_element(L.begin(), L.end());
}
[2] 這些算法至少執行 3n/2-2 次比較，這是任何情形下的比較次數的下限(Cormen, Leiserson, Rivest: "Introduction to Algorithms", 第 9.1 節，習題 9.1-)。這些算法是一對對進行元素比較的，對於頭兩個元素執行1次比較，然後對於剩下的每一對元素執行3次比較(一次用於排好這對元素，然後更新最小 和最大元素各需要一次)。如果元素數量為奇數，則最後一個元素需要分別與當前的最小和最大元素進行比較。另外，對於 minmax, 當出現某對元素相等的情況，更新會保存第二個元素，這時我們要同時保存第一個元素並在最後檢查是否應該使用第一個元素(在出現相等元素的情況下)。很難預知這最後一次比較是否會執行，所以在兩種情形都會發生最多次數的比較。
[3] 這些算法至少執行 3n/2-2 次比較，這是任何情形下的比較次數的下限。這與上面的備註 [2] 相同，同樣如果元素數量為奇數，則最後一個元素需要分別與當前的最小和最大元素進行比較。如果前一次比較成功，則可以避免後一次比較，因此在元素數量為奇數時，比較次數是最多而不是正好。
我知道 std::min 和 std::max 的問題，而且爭論一直在繼續(請參考
Alexandrescu 的論文 及那裡的鏈接)。但是我不認為這個庫應該修改已經是C++標準的任何東西。我認為這超出了這個庫的範圍。我寧可遵從標準，只是提供相同功能的多一個函數而已。如果其它人想修正 std::min, 他們也許也會同時修正 boost::minmax.在本庫的第一個版本中，我為所有算法提供了 _if 的版本(其實不是所有，因為那太多了)。不過，其實沒有理由這樣做，所有我曾經提供的版本都可以使用 <boost/iterator_adaptors.hpp> 庫很快地實現。即，對 min_element_if(first, last, pred) 的調用可以實現如下：
// 等價於 min_element_if(first, last, pred)是的，min_element_if 版本更短一點，不過使用迭代器適配器也沒增加多少，而且它們還避免了大量代碼(想想由 first/last 及其 _if 變體的所有組合！)
min_element(boost::make_filter_iterator(first, last, pred),
boost::make_filter_iterator(last, last, pred));
This rationale is somewhat historical, but explains why there are all these first/last_min/max_element functions.
C++ 標準要求 std::min_element 和 std::max_element 返回最小和最大元素的第一個實例(不是最後一個)。這種選擇是有些一致性的考慮的：例如對於類型 vector<int> 的 v, 以下表達式為true， std::min_element(v.begin(),v.end(),std::less<int>()) == std::max_element(v.begin(),v.end(),std::greater<int>()).
這當然沒有錯：這只是一種選擇。另一種指定 min_element 和 max_element 的方法是將它們分別定義為第一個元素和最後一個元素，如果該區間是穩定排序的(穩定排序是必須的，以消除兩個迭代器具有相同值時的歧義)。這種情況下，min 應返回第一個實例，而 max 應返回最後一個。那麼，這兩個函數有以下關係：reverse_iterator(std::first_min_element(v.begin(),v.end(),std::less<int>())) == std::last_max_element(v.rbegin(),v.rend(),std::greater<int>()). 這個定義與前一個的差異非常微妙。
當你試圖使用 (Cormen, Leiserson, Rivest: "Introduction to Algorithms", 第 9.1 節) 建議的方法來設計一個 minmax_element 時，定義的問題就浮現了。該方法可以生成一個算法，在 [first,last) 有 n 個元素時只進行 3n/2 次比較，但是如果你試圖寫一個調用 first_min_first_max_element() 的函數，在一個 pair 中同時返回 std::min_element 和 std::max_element, 簡單的實現是不行的。問題有些微妙，是有關於相等元素的：我不得不思考了一段時間以找到一種方法，只須對每對元素執行三次比較並且返回第一個 min 和第一個 max 元素。很長一段時間，所有這樣的嘗試都會在最壞情況時執行四次比較。而這個實現達到了三次。
不可能(也不值得)修改 max_element 的含義，不過提供一個 minmax_element 函數則還是有好處的，它返回一對 min_element 和 max_element. 雖然它可以通過調用 min_element 和 max_element 輕易實現，但是這需要 2(n-1) 次比較，而且需要遍歷兩次輸入。作為對比，minmax_element 要執行更少的比較和一次輸入。當迭代器類型不是裸指針時，所節省的時間是很顯著的，尤其是當迭代器僅僅滿足輸入迭代器的概念時(不過這種情況下要修改接口，因為返回的類型不可複製，你可以用值來返回)。
為了從算法的所有變體受益，我提議引入 first_min_element 和 last_min_element, 以及對應的 first_max_element 和 last_max_element. 我還提議了所有的算法變體：first_min_last_max_element 和 last_min_first_max_element, 它們最多執行 3n/2 次比較和單次輸入。實際上，可以證明為任意實例計算 minmax 至少需要 3(n/2)-2 次比較(Cormen, Leiserson, Rivest, 第2版, 第 9.1 節)。我給出的實現不會執行不必要的比較(即結果可以從以前的比較計算得到的那些比較)。
看起來 first_min_last_max_element 可能會只比單個 first_min_element 慢一點點，比分別執行 first_min_element 和 last_max_element 還是要快不少的。[2]
minmax 算法在計算一個區間的邊界時是很有用的。在計算機圖形學中，我們需要計算一組對象的邊界包。這種情況下，對單次遍歷的需要更為嚴格，必須一次處理三個方向。(精神糧食：一個好的泛型程序庫應該有可堆疊的 update_min 和 update_max 函數對象，它們保存一個到 min_result 和 max_result 變量的引用，可以與 for_each 算法共同使用)。
我相信，許多標準的順序算法都可以用累加器的形式來重新表示(如統計學中的期望值 / 方差 / 等等)。這看來是其它程序庫的空間，但我不認為它會與 minmax 構成競爭，而是將幾個算法(包括 minmax)擴展到累加器框架。不過，我覺得提供這樣的累加器已經超出了本庫的範圍。
是的，我可以那樣做，對於 min_element 和 max_element 來說，缺省的策略是返回第一個結果。這樣可以減少 minmax_element 變體的組合數量。不過它也意味著要改變 boost::minmax_element 的接口。minmax_element 算法的一個目標就是，它是對C++標準的增加，將 std::min_element 和 std::max_element 聯合起來(而且我覺得目前的實現是很自然的)。所以修改接口以加入相應的策略是不符合標準且背離了這一目標的。此外，不使用策略可以使得代碼更簡單和易讀。所以我很高興保持原樣。
One minmax_element implementation, which performs 3(n/2)+O(log n) comparisons on the average when the elements are random_shuffled, was suggested by my student Marc Glisse. The current one, which performs 3(n/2)+1 comparisons in the worst case, was suggested by John Iacono.
Finally, Matthew Wilson and Jeremy Siek contributed pre-review comments, while Gennadiy Rozental, John Maddock, Craig Henderson, Gary Powell participated in the review of the library, managed by Thomas Witt. In particular, Gennadiy suggested a factorization of the code; while I haven't followed it all the way, his suggestions do make the code more readable and still work with older compilers. Late after the review, as I finally scrounged to add the library for a release, Eric Niebler noted the bad behavior of std::pair for minmax and suggested to use Boost.tuple instead. All my thanks for the excellent advice and reviews from all.
© Copyright Hervé Brönnimann, Polytechnic University, 2002--2004. Use, modification, and distribution is subject to the Boost Software License, Version 1.0. (See accompanying file License_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)