STL——查找算法及实例

一 前言

        STL算法部分主要由头文件,,组成。要使用 STL中的算法函数必须包含头文件，对于数值算法须包含，中则定义了一些模板类，用来声明函数对象。
STL中算法大致分为四类：
1）、非可变序列算法：指不直接修改其所操作的容器内容的算法。
2）、可变序列算法：指可以修改它们所操作的容器内容的算法。
3）、排序算法：包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作。
4）、数值算法：对容器内容进行数值计算。

 二 查找算法(13个)

判断容器中是否包含某个值

    adjacent_find

  在iterator对标识元素范围内，查找一对相邻重复元素，找到则返回指向这对元素的第一个元素的ForwardIterator。否则返回last。重载版本使用输入的二元操作符代替相等的判断。

#include 
#include 
#include 
 
int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 4, 5, 6};
    
    // Find the first pair of adjacent repeated elements
    auto it = std::adjacent_find(numbers.begin(), numbers.end());
    
    if (it != numbers.end()) {
        std::cout << "Found adjacent repeated elements: " << *it << " and " << *(it + 1) << std::endl;
    } else {
        std::cout << "No adjacent repeated elements found" << std::endl;
    }
    
    return 0;
}
 
输出：
 
Found adjacent repeated elements: 4 and 4

   binary_search

        在有序序列中查找value，找到返回true。重载的版本实用指定的比较函数对象或函数指针来判断相等。

#include 
#include 
#include 
 
int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5, 6};
    int value = 3;
    
    // Check if value exists in the sorted sequence
    bool found = std::binary_search(numbers.begin(), numbers.end(), value);
    
    if (found) {
        std::cout << "Value " << value << " found" << std::endl;
    } else {
        std::cout << "Value " << value << " not found" << std::endl;
    }
    
    return 0;
}
 
输出
Value 3 found

    count 

        利用等于操作符，把标志范围内的元素与输入值比较，返回相等元素个数。

#include 
#include 
#include 
 
int main() {
    std::vector<int> numbers = {1, 2, 3, 2, 2, 4, 5};
 
    int value = 2;
 
    // Count the occurrences of value in the range
    int count = std::count(numbers.begin(), numbers.end(), value);
 
    std::cout << "Number of occurrences of " << value << ": " << count << std::endl;
 
    return 0;
}
 
输出：
Number of occurrences of 2: 3

    count_if 

        利用输入的操作符，对标志范围内的元素进行操作，返回结果为true的个数。

#include 
#include 
#include 
 
bool isEven(int number) {
    return number % 2 == 0;
}
 
int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5, 6};
 
    // Count the number of even elements in the range
    int count = std::count_if(numbers.begin(), numbers.end(), isEven);
 
    std::cout << "Number of even elements: " << count << std::endl;
 
    return 0;
}
 
输出：
Number of even elements: 3

    equal_range

        功能类似equal，返回一对iterator，第一个表示lower_bound，第二个表示upper_bound。

std::vector<int> nums = {1, 2, 3, 4, 4, 5};
auto range = std::equal_range(nums.begin(), nums.end(), 4);
// range.first指向第一个等于4的元素位置，range.second指向第一个大于4的元素位置
// 在这个例子中，range.first指向索引3处的元素(值为4)，range.second指向索引5处的元素(值为5)

    find  

        利用底层元素的等于操作符，对指定范围内的元素与输入值进行比较。当匹配时，结束搜索，返回该元素的一个InputIterator。

std::vector<int> nums = {1, 2, 3, 4, 5};
auto it = std::find(nums.begin(), nums.end(), 3);
// it指向索引2处的元素(值为3)

    find_end

        在指定范围内查找"由输入的另外一对iterator标志的第二个序列"的最后一次出现。找到则返回最后一对的第一个ForwardIterator，否则返回输入的"另外一对"的第一个ForwardIterator。重载版本使用用户输入的操作符代替等于操作。

std::vector<int> nums = {1, 2, 3, 4, 1, 2, 3, 4};
std::vector<int> subseq = {3, 4};
auto it = std::find_end(nums.begin(), nums.end(), subseq.begin(), subseq.end());
// it指向索引6处的元素(值为3)，即最后一次出现子序列{3, 4}的位置

   find_first_of        

        在指定范围内查找"由输入的另外一对iterator标志的第二个序列"中任意一个元素的第一次出现。重载版本中使用了用户自定义操作符。

std::vector<int> nums = {1, 2, 3, 4, 5};
std::vector<int> search_nums = {4, 6};
auto it = std::find_first_of(nums.begin(), nums.end(), search_nums.begin(), search_nums.end());
// it指向索引3处的元素(值为4)，即首次出现search_nums中任意一个元素{4, 6}的位置

    find_if  

        使用输入的函数代替等于操作符执行find。

std::vector<int> nums = {1, 2, 3, 4, 5};
auto it = std::find_if(nums.begin(), nums.end(), [](int num) { return num % 2 == 0; });
// it指向索引1处的元素(值为2)，即第一个满足条件(num % 2 == 0)的元素的位置

    lower_bound

         返回一个ForwardIterator，指向在有序序列范围内的可以插入指定值而不破坏容器顺序的第一个位置。重载函数使用自定义比较操作。

std::vector<int> nums = {1, 2, 3, 4, 5};
auto it = std::lower_bound(nums.begin(), nums.end(), 4);
// it指向索引3处的元素(值为4)，即第一个大于等于4的元素的位置

    upper_bound

        返回一个ForwardIterator，指向在有序序列范围内插入value而不破坏容器顺序的最后一个位置，该位置标志一个大于value的值。重载函数使用自定义比较操作。

std::vector<int> nums = {1, 2, 3, 4, 5};
auto it = std::upper_bound(nums.begin(), nums.end(), 4);
// it指向索引4处的元素(值为5)，即第一个大于4的元素的位置

    search:

         给出两个范围，返回一个ForwardIterator，查找成功指向第一个范围内第一次出现子序列(第二个范围)的位置，查找失败指向last1。重载版本使用自定义的比较操作。

#include 
#include 
#include 
 
bool customCompare(int a, int b) {
    // 自定义比较函数，检查是否a和b相差为1
    return (std::abs(a - b) == 1);
}
 
int main() {
    std::vector<int> vec1 {1, 2, 3, 4, 5};
    std::vector<int> vec2 {3, 4};
 
    auto it = std::search(vec1.begin(), vec1.end(), vec2.begin(), vec2.end());
 
    if (it != vec1.end()) {
        std::cout << "子序列在位置 " << std::distance(vec1.begin(), it) << " 处找到" << std::endl;
    } else {
        std::cout << "未找到子序列" << std::endl;
    }
 
    // 使用自定义比较函数
    it = std::search(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), customCompare);
 
    if (it != vec1.end()) {
        std::cout << "子序列在位置 " << std::distance(vec1.begin(), it) << " 处找到" << std::endl;
    } else {
        std::cout << "未找到子序列" << std::endl;
    }
 
    return 0;
}

    search_n

        在指定范围内查找val出现n次的子序列。重载版本使用自定义的比较操作。

#include 
#include 
#include 
 
bool customCompare(int a, int b) {
    // 自定义比较函数，检查是否a和b相差为1
    return (std::abs(a - b) == 1);
}
 
int main() {
    std::vector<int> numbers {1, 2, 3, 4, 5, 6, 7, 8, 9};
 
    // 在numbers中查找连续出现3个值为2的子序列
    auto it = std::search_n(numbers.begin(), numbers.end(), 3, 2);
 
    if (it != numbers.end()) {
        std::cout << "Found the subsequence at index: "
                  << std::distance(numbers.begin(), it) << std::endl;
    } else {
        std::cout << "Subsequence not found!" << std::endl;
    }
 
    // 使用自定义比较函数在numbers中查找连续出现3个相邻的元素
    it = std::search_n(numbers.begin(), numbers.end(), 3, 0, customCompare);
 
    if (it != numbers.end()) {
        std::cout << "Found the subsequence at index: "
                  << std::distance(numbers.begin(), it) << std::endl;
    } else {
        std::cout << "Subsequence not found!" << std::endl;
    }
 
    return 0;
}