C++ 最值操作

在C++编程中，查找集合或值之间的最大值、最小值是很常见的需求。C++ STL提供了一系列用于这类操作的函数模板，这些函数不仅能够简化我们的代码，还能提高代码的效率与可读性。本文将详细介绍C++ STL中的最值操作函数和算法。

基本最值函数

min和max函数

STL提供了min()和max()函数，用于比较两个或多个值并返回其中的最小值或最大值。

cpp

#include <iostream>
#include <algorithm>  // 包含min和max函数

int main() {
    int a = 10, b = 20;
    
    std::cout << "min(a, b) = " << std::min(a, b) << std::endl;
    std::cout << "max(a, b) = " << std::max(a, b) << std::endl;
    
    return 0;
}

输出：

min(a, b) = 10
max(a, b) = 20

min()和max()函数还可以接受初始化列表作为参数，比较多个元素：

cpp

#include <iostream>
#include <algorithm>

int main() {
    int result = std::min({10, 5, 15, 25, 8});
    std::cout << "Min value: " << result << std::endl;
    
    result = std::max({10, 5, 15, 25, 8});
    std::cout << "Max value: " << result << std::endl;
    
    return 0;
}

输出：

Min value: 5
Max value: 25

minmax函数

minmax()函数返回一个包含最小值和最大值的std::pair对象：

cpp

#include <iostream>
#include <algorithm>

int main() {
    auto result = std::minmax(10, 20);
    std::cout << "Min: " << result.first << ", Max: " << result.second << std::endl;
    
    auto result2 = std::minmax({10, 5, 15, 25, 8});
    std::cout << "Min: " << result2.first << ", Max: " << result2.second << std::endl;
    
    return 0;
}

输出：

Min: 10, Max: 20
Min: 5, Max: 25

自定义比较器

上述所有函数都可以接受自定义比较器作为额外的参数，这使得我们可以根据特定需求定义比较规则：

cpp

#include <iostream>
#include <algorithm>
#include <string>

struct Person {
    std::string name;
    int age;
};

int main() {
    Person p1{"Alice", 25};
    Person p2{"Bob", 20};
    
    // 按年龄比较，返回年龄较小的人
    auto younger = std::min(p1, p2, [](const Person& a, const Person& b) {
        return a.age < b.age;
    });
    
    std::cout << "Younger person: " << younger.name << ", age: " << younger.age << std::endl;
    
    return 0;
}

输出：

Younger person: Bob, age: 20

容器范围内的最值操作

min_element和max_element函数

这两个函数用于在容器或数组的指定范围内查找最小值和最大值的位置：

cpp

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> numbers = {10, 5, 15, 25, 8};
    
    auto min_it = std::min_element(numbers.begin(), numbers.end());
    auto max_it = std::max_element(numbers.begin(), numbers.end());
    
    std::cout << "Min value: " << *min_it << " at position: " 
              << std::distance(numbers.begin(), min_it) << std::endl;
    std::cout << "Max value: " << *max_it << " at position: " 
              << std::distance(numbers.begin(), max_it) << std::endl;
    
    return 0;
}

输出：

Min value: 5 at position: 1
Max value: 25 at position: 3

minmax_element函数

minmax_element()函数同时返回最小值和最大值的迭代器：

cpp

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> numbers = {10, 5, 15, 25, 8};
    
    auto result = std::minmax_element(numbers.begin(), numbers.end());
    
    std::cout << "Min value: " << *(result.first) << " at position: " 
              << std::distance(numbers.begin(), result.first) << std::endl;
    std::cout << "Max value: " << *(result.second) << " at position: " 
              << std::distance(numbers.begin(), result.second) << std::endl;
    
    return 0;
}

输出：

Min value: 5 at position: 1
Max value: 25 at position: 3

备注

min_element、max_element和minmax_element函数返回的是迭代器，需要使用*运算符来获取对应的值。

带条件的最值操作

有时我们需要根据特定条件查找最值，如查找绝对值最大的元素：

cpp

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

int main() {
    std::vector<int> numbers = {-10, 5, -15, 25, -8};
    
    auto abs_max_it = std::max_element(numbers.begin(), numbers.end(),
                                      [](int a, int b) {
                                          return std::abs(a) < std::abs(b);
                                      });
    
    std::cout << "Element with max absolute value: " << *abs_max_it << std::endl;
    std::cout << "Its absolute value: " << std::abs(*abs_max_it) << std::endl;
    
    return 0;
}

输出：

Element with max absolute value: 25
Its absolute value: 25

实际应用场景

场景1：成绩统计系统

假设我们有一个学生成绩管理系统，需要找出最高分和最低分：

cpp

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

struct Student {
    std::string name;
    int score;
};

int main() {
    std::vector<Student> students = {
        {"Alice", 85},
        {"Bob", 92},
        {"Charlie", 78},
        {"Diana", 95},
        {"Edward", 70}
    };
    
    auto score_comp = [](const Student& a, const Student& b) {
        return a.score < b.score;
    };
    
    auto highest = std::max_element(students.begin(), students.end(), score_comp);
    auto lowest = std::min_element(students.begin(), students.end(), score_comp);
    
    std::cout << "Highest score: " << highest->name << " with " << highest->score << std::endl;
    std::cout << "Lowest score: " << lowest->name << " with " << lowest->score << std::endl;
    
    return 0;
}

输出：

Highest score: Diana with 95
Lowest score: Edward with 70

场景2：股票最佳买卖时机

假设我们有一个股票价格的历史数据，需要找出最佳买入点（最低价）和卖出点（最高价）：

cpp

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>

int main() {
    std::vector<double> stockPrices = {102.5, 101.8, 98.6, 97.2, 100.5, 105.2, 103.8};
    
    auto minmax = std::minmax_element(stockPrices.begin(), stockPrices.end());
    int buyDay = std::distance(stockPrices.begin(), minmax.first);
    int sellDay = std::distance(stockPrices.begin(), minmax.second);
    
    // 如果最低价出现在最高价之后，我们需要在各自子区间内找最佳时机
    if (buyDay > sellDay) {
        auto minFirstHalf = std::min_element(stockPrices.begin(), minmax.second + 1);
        auto maxSecondHalf = std::max_element(minmax.first, stockPrices.end());
        
        double profit1 = *minmax.second - *minFirstHalf;
        double profit2 = *maxSecondHalf - *minmax.first;
        
        if (profit1 > profit2) {
            buyDay = std::distance(stockPrices.begin(), minFirstHalf);
            sellDay = std::distance(stockPrices.begin(), minmax.second);
        } else {
            buyDay = std::distance(stockPrices.begin(), minmax.first);
            sellDay = std::distance(stockPrices.begin(), maxSecondHalf);
        }
    }
    
    std::cout << "Best day to buy: Day " << buyDay + 1 
              << " (Price: " << stockPrices[buyDay] << ")" << std::endl;
    std::cout << "Best day to sell: Day " << sellDay + 1 
              << " (Price: " << stockPrices[sellDay] << ")" << std::endl;
    std::cout << "Maximum profit: " << stockPrices[sellDay] - stockPrices[buyDay] << std::endl;
    
    return 0;
}

提示

实际的股票买卖问题会更复杂，上面的算法有简化。在实际应用中，我们可能需要考虑更多的约束条件，比如买入必须在卖出之前。

C++ 17中的新增功能：带初始值的最值操作

C++17为min、max和minmax函数添加了新的重载版本，允许指定一个初始值：

cpp

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> numbers = {5, 8, 3};
    
    // 在vector中查找大于等于10的最小值，如果没有则返回10
    int result = std::min({10}, std::greater<>());
    for (int num : numbers) {
        result = std::min(result, num, std::greater<>());
    }
    
    std::cout << "Smallest value >= 10: " << result << std::endl;  // 如果没有>=10的值，会输出10
    
    return 0;
}

性能考虑

最值操作的时间复杂度：

1. min()和max()比较两个值：O(1)
2. min_element()和max_element()在n个元素中查找：O(n)
3. minmax_element()在n个元素中同时查找最小值和最大值：O(n)，比单独调用min_element()和max_element()更高效（遍历次数减半）。

警告

使用自定义比较器时，确保比较器满足严格弱序关系（Strict Weak Ordering），否则可能导致不可预测的行为。

总结

C++ STL提供了多种强大的最值操作函数，可以轻松在各种场景中找到最大值、最小值或两者同时找出。这些函数支持：

• 基本类型之间的比较
• 初始化列表形式的多值比较
• 自定义比较器
• 容器范围内的最值查找
• 同时查找最小值和最大值

熟练掌握这些函数，可以让我们的代码更加简洁、高效且易于理解。

练习题

1. 编写程序找出一个整数向量中的最大值和最小值，并计算它们的差值。
2. 创建一个包含字符串的向量，找出其中最长和最短的字符串。
3. 实现一个函数，在一个二维点的向量中找出距离原点最远的点。
4. 在一个学生成绩系统中，找出每门课程的最高分和最低分，以及获得这些分数的学生。
5. 使用minmax_element函数，找出一个向量中最接近平均值的元素。

深入学习资源

• C++ Reference: Algorithm library
• Effective STL by Scott Meyers
• C++ Core Guidelines

通过学习和实践这些最值操作函数，你将能够更加高效地解决各种编程问题，提高代码质量。