动机
概要
函数模板描述
定义
类型要求
前提条件
后置条件
复杂度
示例
注释
理由
性能说明
致谢
minmax 库由两个头文件组成，<boost/algorithm/minmax.hpp> 和 <boost/algorithm/minmax_element.hpp>。（参见 理由。）此库解决的问题是，同时计算最小值和最大值只需要一次比较，但是使用std::min和std::max会强制进行两次比较。更糟糕的是，要计算一个范围内的最小值和最大值，范围包含n个元素只需要3n/2+1次比较，而不是2n次比较（在两次遍历中），就像std::min_element和std::max_element那样。我一直认为，必须调用两个函数来计算一个范围的极值，对输入执行两次遍历，而一次就足够了，这是一种浪费。当前的库解决了这两个问题。
第一个文件实现了函数模板minmax作为 C++ 标准的直接扩展。由于它返回一个const&对，我们必须使用 Boost.tuple 库来构造这样的对。（请注意：目的不是修复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_element相同，仅包含在此库中以保持对称性。
Last_min_element和last_max_element查找范围[first, last)。它们几乎与std::min_element和std::max_element相同，只是它们返回最大元素的最后一个实例（而不是像first_min_element和last_max_element那样返回第一个实例）。
包含first_min_first_max_element, first_min_last_max_element, last_min_first_max_element，以及last_min_last_max_element的算法族可以按如下方式通用地描述（使用 which 和 what 表示first或last): which_min_what_max_element在范围[first, last)中查找（根据 which 是第一个还是最后一个）最小元素和（根据 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: "算法导论"，第 9.1 节，练习 9.1-）。这些算法本质上是成对比较元素，前两个元素执行 1 次比较，然后对于每个剩余的元素对执行 3 次比较（一次用于排序元素，一次用于更新最小值，一次用于更新最大值）。当元素数量为奇数时，最后一个元素需要与当前最小值和当前最大值进行比较。此外，对于minmax，在对中的两个成员可能相等的情况下，并且更新存储了第二个成员，我们保存第一个成员以便在最后检查更新是否应该存储第一个成员（在相等的情况下）。很难预测是否执行最后一次比较，因此在两种情况下都使用最多。
[3] 这些算法始终至少执行3n/2-2次比较，这在任何情况下都是比较次数的下界。该方法与注释 [2] 中相同，并且与上面类似，当元素数量为奇数时，最后一个元素需要与当前最小值和当前最大值进行比较。如果前者成功，我们可以避免后者的比较，因此在奇数情况下使用最多而不是精确地。
这是最初提出的并在正式审查中获得批准的设计。随着对 Boost.tuple 的需求变得清晰（由于 std::pair 的限制），对于不需要它的 minmax_element 而言，也需要另一个库变得令人恼火。因此，将其分成两个头文件。
我意识到了 std::min 和 std::max 的问题，以及所有正在进行的辩论（请查阅 Alexandrescu 的论文 和其中的链接）。但是我不认为这个库的目的是修复 C++ 标准的一部分。我谦虚地认为这超出了这个库的范围。相反，我遵循标准的方式，只是简单地提供同一系列的另一个函数。如果其他人想要修复 std::min，他们的修复程序可能也适用于 boost::minmax。
在库的第一个版本中，我提出了_if所有算法的版本（好吧，不是全部，因为那样会太多）。但是，根本没有理由这样做，并且我拥有的所有版本都使用出色的<boost/iterator_adaptors.hpp>库以同样快的速度实现。也就是说，调用min_element_if(first, last, pred)可以通过
// equivalent to min_element_if(first, last, pred)
min_element(boost::make_filter_iterator(first, last, pred),
boost::make_filter_iterator(last, last, pred));
来很好地实现。可以说，min_element_if版本在某种程度上更短，但是迭代器适配器的开销不大，并且它们摆脱了大量代码（想想 first/last 之间的所有组合，并将它们与 _if 变体加倍！）。
这个理由在某种程度上是历史性的，但解释了为什么存在所有这些first/last_min/max_element函数。
C++ 标准规定std::min_element和std::max_element返回最小和最大元素的第一个实例（而不是，例如，最后一个）。这种任意选择具有一定的连贯性：例如，对于 v 类型为 vector<int> 的情况，以下情况是正确的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: "算法导论"，第 9.1 节）中提出的过程来设计 minmax_element 时，定义问题就浮出水面了。如果3n/2次比较是可能的，如果[first,last)有n个元素，但是如果尝试编写一个名为first_min_first_max_element()的函数，该函数在一个对中返回std::min_element和std::max_element，则简单的实现不起作用。问题相当微妙，是关于相等元素：我不得不思考一段时间才能找到一种方法，即每个对只执行三次比较并返回第一个最小和第一个最大元素。长期以来，似乎任何尝试这样做都会在最坏的情况下消耗每个对四次比较。此实现实现了三次。
更改max_element的含义是不可能的（甚至是不希望的），但仍然有益于提供一个名为minmax_element的函数，该函数返回一对min_element和max_element。尽管调用min_element和max_element足够容易，但这会执行2(n-1)次比较，并且需要对输入进行两次遍历。相反，minmax_element将执行更少的比较，并对输入执行单次遍历。当迭代器类型不是原始指针时，或者甚至只是 InputIterator 概念的模型时，节省可能是显着的（尽管在这种情况下，接口必须更改，因为返回类型无法复制，因此可以例如返回一个值）。
为了从算法的所有变体中获益，我建议引入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，第二版，第 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 相关联（并且我感觉这非常自然，考虑到实现的简洁性，以及使其正确所需的并非微不足道的细节）。因此，通过添加策略来更改接口将不幸地意味着偏离标准，并为实现该目标设置障碍。此外，在没有策略的情况下，代码仍然相当可读和简单。所以我很高兴保持这样。
我在 CS903（Polytechnic Univ., http://photon.poly.edu/~hbr/cs903/）的学生，他们的minmax_element作为一项作业，帮助澄清了问题，并提出了first_min_last_max_element的最佳比较次数。围绕max_element问题的识别完全是我自己的。
一个minmax_element实现，当元素为random_shuffled 时，平均执行3(n/2)+O(log n)次比较，是由我的学生 Marc Glisse 提出的。当前的实现，在最坏的情况下执行3(n/2)+1次比较，是由 John Iacono 提出的。
最后，Matthew Wilson 和 Jeremy Siek 贡献了预审评论，而 Gennadiy Rozental、John Maddock、Craig Henderson、Gary Powell 参与了由 Thomas Witt 管理的库审查。特别是，Gennadiy 建议对代码进行分解；虽然我没有完全遵循它，但他的建议确实使代码更具可读性，并且仍然适用于较旧的编译器。在审查后期，当我最终努力为发布添加库时，Eric Niebler 注意到std::pair的minmax不良行为，并建议改用 Boost.tuple。非常感谢大家提供的出色建议和审查。
© 版权所有 Hervé Brönnimann, Polytechnic University, 2002--2004。使用、修改和分发受 Boost 软件许可证 1.0 版的约束。（请参阅随附文件 License_1_0.txt 或复制于 https://boost.ac.cn/LICENSE_1_0.txt）