C++ 非修改序列操作

在C++标准模板库(STL)中，算法是处理容器中数据的强大工具。而非修改序列操作是一类不会改变容器中元素的算法，它们只是对容器进行查询、计数、搜索等操作，是初学者学习STL算法的良好起点。

什么是非修改序列操作？

非修改序列操作是STL算法库中的一组函数，它们在执行过程中不会修改序列中的元素值。这些操作主要用于:

• 查找元素
• 计数统计
• 比较序列
• 检查序列特性

这些算法在<algorithm>头文件中定义，使用前需要包含该头文件。

常用的非修改序列操作

1. all_of, any_of, none_of

这三个算法用于检查序列中的元素是否满足特定条件：

cpp

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

int main() {
    std::vector<int> nums = {2, 4, 6, 8, 10};
    
    // 检查是否所有元素都是偶数
    bool allEven = std::all_of(nums.begin(), nums.end(), 
                              [](int n){ return n % 2 == 0; });
    
    // 检查是否有任意元素大于8
    bool anyGreaterThan8 = std::any_of(nums.begin(), nums.end(), 
                                      [](int n){ return n > 8; });
    
    // 检查是否没有元素小于0
    bool noneNegative = std::none_of(nums.begin(), nums.end(), 
                                    [](int n){ return n < 0; });
    
    std::cout << "All even? " << (allEven ? "Yes" : "No") << std::endl;
    std::cout << "Any greater than 8? " << (anyGreaterThan8 ? "Yes" : "No") << std::endl;
    std::cout << "None negative? " << (noneNegative ? "Yes" : "No") << std::endl;
    
    return 0;
}

输出：

All even? Yes
Any greater than 8? Yes
None negative? Yes

2. for_each

遍历容器中的每个元素并对其执行操作，但不修改元素本身：

cpp

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

void printElement(int n) {
    std::cout << n << " ";
}

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5};
    
    std::cout << "Elements in the vector: ";
    std::for_each(nums.begin(), nums.end(), printElement);
    std::cout << std::endl;
    
    // 使用lambda表达式
    std::cout << "Square of each element: ";
    std::for_each(nums.begin(), nums.end(), [](int n) {
        std::cout << n * n << " ";
    });
    std::cout << std::endl;
    
    return 0;
}

输出：

Elements in the vector: 1 2 3 4 5 
Square of each element: 1 4 9 16 25 

3. find, find_if, find_if_not

这些算法用于在容器中查找元素：

cpp

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

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

int main() {
    std::vector<int> nums = {10, 20, 30, 40, 50};
    
    // 查找特定值
    auto it1 = std::find(nums.begin(), nums.end(), 30);
    if (it1 != nums.end()) {
        std::cout << "Found 30 at position: " << (it1 - nums.begin()) << std::endl;
    }
    
    // 查找满足条件的元素
    auto it2 = std::find_if(nums.begin(), nums.end(), 
                          [](int n) { return n > 35; });
    if (it2 != nums.end()) {
        std::cout << "First element > 35 is: " << *it2 << std::endl;
    }
    
    // 创建一个Person对象的向量
    std::vector<Person> people = {
        {"Alice", 25},
        {"Bob", 30},
        {"Charlie", 35},
        {"David", 40}
    };
    
    // 查找不满足条件的元素
    auto it3 = std::find_if_not(people.begin(), people.end(),
                              [](const Person& p) { return p.age < 35; });
    if (it3 != people.end()) {
        std::cout << "First person not younger than 35: " << it3->name << std::endl;
    }
    
    return 0;
}

输出：

Found 30 at position: 2
First element > 35 is: 40
First person not younger than 35: Charlie

4. count, count_if

这些算法用于计数：

cpp

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

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 2, 5, 2, 6};
    
    // 计算特定值出现的次数
    int count2 = std::count(nums.begin(), nums.end(), 2);
    std::cout << "Number 2 appears " << count2 << " times" << std::endl;
    
    // 计算满足条件的元素个数
    int countEven = std::count_if(nums.begin(), nums.end(), 
                                [](int n) { return n % 2 == 0; });
    std::cout << "Even numbers: " << countEven << std::endl;
    
    return 0;
}

输出：

Number 2 appears 3 times
Even numbers: 5

5. equal

比较两个序列是否相等：

cpp

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

int main() {
    std::vector<int> vec1 = {1, 2, 3, 4, 5};
    std::vector<int> vec2 = {1, 2, 3, 4, 5};
    std::vector<int> vec3 = {5, 4, 3, 2, 1};
    
    bool isEqual1 = std::equal(vec1.begin(), vec1.end(), vec2.begin());
    bool isEqual2 = std::equal(vec1.begin(), vec1.end(), vec3.begin());
    
    std::cout << "vec1 and vec2 are " << (isEqual1 ? "equal" : "not equal") << std::endl;
    std::cout << "vec1 and vec3 are " << (isEqual2 ? "equal" : "not equal") << std::endl;
    
    return 0;
}

输出：

vec1 and vec2 are equal
vec1 and vec3 are not equal

警告

使用equal时，必须确保第二个序列至少有与第一个序列相同数量的元素，否则会导致未定义行为。

6. mismatch

查找两个序列中第一个不匹配的位置：

cpp

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

int main() {
    std::string str1 = "Hello World";
    std::string str2 = "Hello C++";
    
    auto [it1, it2] = std::mismatch(str1.begin(), str1.end(), str2.begin());
    
    std::cout << "First mismatch at position: " << (it1 - str1.begin()) << std::endl;
    std::cout << "Characters at mismatch: '" << *it1 << "' and '" << *it2 << "'" << std::endl;
    
    return 0;
}

输出：

First mismatch at position: 6
Characters at mismatch: ' ' and 'C'

7. search, find_end, find_first_of

这些算法用于在序列中查找子序列或元素集合：

cpp

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

int main() {
    std::vector<int> haystack = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};
    std::vector<int> needle = {3, 4};
    std::vector<int> any_of = {10, 20, 3, 30};
    
    // 查找子序列的第一次出现
    auto it1 = std::search(haystack.begin(), haystack.end(), 
                         needle.begin(), needle.end());
    if (it1 != haystack.end()) {
        std::cout << "First occurrence of {3, 4} at position: " 
                  << (it1 - haystack.begin()) << std::endl;
    }
    
    // 查找子序列的最后一次出现
    auto it2 = std::find_end(haystack.begin(), haystack.end(), 
                           needle.begin(), needle.end());
    if (it2 != haystack.end()) {
        std::cout << "Last occurrence of {3, 4} at position: " 
                  << (it2 - haystack.begin()) << std::endl;
    }
    
    // 查找任何一个元素的第一次出现
    auto it3 = std::find_first_of(haystack.begin(), haystack.end(), 
                                any_of.begin(), any_of.end());
    if (it3 != haystack.end()) {
        std::cout << "First occurrence of any element from {10, 20, 3, 30} is " 
                  << *it3 << " at position: " << (it3 - haystack.begin()) << std::endl;
    }
    
    return 0;
}

输出：

First occurrence of {3, 4} at position: 2
Last occurrence of {3, 4} at position: 7
First occurrence of any element from {10, 20, 3, 30} is 3 at position: 2

8. adjacent_find

查找容器中第一对相邻且相等（或满足特定条件）的元素：

cpp

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

int main() {
    std::vector<int> nums = {1, 3, 5, 5, 7, 9, 9};
    
    // 查找第一对相邻且相等的元素
    auto it = std::adjacent_find(nums.begin(), nums.end());
    if (it != nums.end()) {
        std::cout << "First adjacent equal elements: " << *it 
                  << " at position " << (it - nums.begin()) << std::endl;
    }
    
    // 使用自定义条件：查找第一对相邻且差值大于2的元素
    auto it2 = std::adjacent_find(nums.begin(), nums.end(), 
                                [](int a, int b) { return (b - a) > 2; });
    if (it2 != nums.end()) {
        std::cout << "First adjacent elements with difference > 2: " 
                  << *it2 << " and " << *(it2 + 1) 
                  << " at position " << (it2 - nums.begin()) << std::endl;
    }
    
    return 0;
}

输出：

First adjacent equal elements: 5 at position 2

实际应用场景

场景1：数据验证

假设我们有一个用户提交的表单数据，需要验证所有字段是否填写正确：

cpp

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

struct FormField {
    std::string name;
    std::string value;
    bool isRequired;
    
    bool isValid() const {
        return !isRequired || !value.empty();
    }
};

bool validateForm(const std::vector<FormField>& form) {
    return std::all_of(form.begin(), form.end(), 
                     [](const FormField& field) { return field.isValid(); });
}

int main() {
    std::vector<FormField> form = {
        {"name", "John Doe", true},
        {"email", "john@example.com", true},
        {"phone", "555-1234", false},
        {"address", "", false}
    };
    
    bool isValid = validateForm(form);
    std::cout << "Form is " << (isValid ? "valid" : "invalid") << std::endl;
    
    // 测试无效表单
    form.push_back({"comment", "", true});  // 必填字段但为空
    isValid = validateForm(form);
    std::cout << "Updated form is " << (isValid ? "valid" : "invalid") << std::endl;
    
    return 0;
}

输出：

Form is valid
Updated form is invalid

场景2：日志分析

假设我们有一个日志文件的条目集合，需要查找特定类型的错误：

cpp

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

enum LogLevel { INFO, WARNING, ERROR, CRITICAL };

struct LogEntry {
    std::string timestamp;
    LogLevel level;
    std::string message;
    
    LogEntry(const std::string& ts, LogLevel lvl, const std::string& msg)
        : timestamp(ts), level(lvl), message(msg) {}
};

int main() {
    std::vector<LogEntry> logs = {
        LogEntry("2023-10-01 10:15:30", INFO, "Application started"),
        LogEntry("2023-10-01 10:16:15", WARNING, "Low memory"),
        LogEntry("2023-10-01 10:20:45", ERROR, "Database connection failed"),
        LogEntry("2023-10-01 10:25:10", INFO, "User logged in"),
        LogEntry("2023-10-01 10:30:22", CRITICAL, "System crash")
    };
    
    // 计算错误和关键错误的数量
    int errorCount = std::count_if(logs.begin(), logs.end(), 
                                 [](const LogEntry& entry) { 
                                     return entry.level == ERROR || entry.level == CRITICAL; 
                                 });
    
    std::cout << "Number of errors and critical issues: " << errorCount << std::endl;
    
    // 查找第一个关键错误
    auto criticalError = std::find_if(logs.begin(), logs.end(),
                                    [](const LogEntry& entry) { 
                                        return entry.level == CRITICAL; 
                                    });
    
    if (criticalError != logs.end()) {
        std::cout << "First critical error: " << criticalError->timestamp 
                  << " - " << criticalError->message << std::endl;
    }
    
    return 0;
}

输出：

Number of errors and critical issues: 2
First critical error: 2023-10-01 10:30:22 - System crash

STL非修改序列操作的优势

1. 安全性：这些操作不会修改原始数据，降低出错风险
2. 提高代码可读性：使用STL算法比手动编写循环更清晰
3. 性能优化：STL算法经过优化，通常比自定义实现更高效
4. 通用性：可以用于多种容器类型，增强代码复用性

总结

非修改序列操作是C++ STL算法库中一组非常实用的工具，它们允许你在不改变容器内容的情况下执行查找、计数、比较等操作。这些算法包括：

• all_of, any_of, none_of - 检查条件是否适用于所有、任何或没有元素
• for_each - 对每个元素执行操作
• find, find_if, find_if_not - 查找特定元素
• count, count_if - 计算元素数量
• equal, mismatch - 比较序列
• search, find_end, find_first_of - 查找子序列
• adjacent_find - 查找相邻元素

掌握这些非修改序列操作是迈向成为高效C++程序员的重要一步，能够帮助你编写更简洁、更易理解和维护的代码。

练习

1. 编写一个程序，使用all_of检查一个向量中的所有数字是否都是质数。
2. 使用find_if查找一个字符串中第一个大写字母。
3. 使用count_if计算一个向量中能被3整除的数字个数。
4. 编写一个程序，使用equal比较两个不同类型的容器中的元素是否相等。
5. 使用search在一个文本字符串中查找一个子字符串，并输出它的位置。

提示

记住，STL算法的强大之处在于它们的通用性和可组合性。尝试组合使用这些算法来解决更复杂的问题！