C++ STL 算法 find 的不同应用场景

1. 基础应用：在简单数组中查找元素

在C++ 编程中，std::find 是STL（标准模板库）提供的一个非常实用的算法，用于在指定范围内查找特定元素。其最基础的应用场景便是在简单数组中查找元素。

std::find 的函数原型如下：

template<class InputIt, class T>
InputIt find(InputIt first, InputIt last, const T& value);

其中，first 和 last 定义了要搜索的范围，value 是要查找的目标元素。函数返回一个迭代器，指向范围内第一个等于 value 的元素。如果未找到匹配元素，则返回 last。

下面来看一个简单的示例，在整型数组中查找特定值：

#include <iostream>
#include <algorithm>

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int target = 30;

    int* result = std::find(std::begin(arr), std::end(arr), target);

    if (result != std::end(arr)) {
        std::cout << "元素 " << target << " 找到，位置为：" << std::distance(std::begin(arr), result) << std::endl;
    } else {
        std::cout << "元素 " << target << " 未找到" << std::endl;
    }

    return 0;
}

在上述代码中，我们定义了一个整型数组 arr 和目标元素 target。通过 std::find 函数在数组 arr 的整个范围内查找 target。如果找到了，通过 std::distance 函数计算目标元素在数组中的位置并输出；如果未找到，则输出相应提示。

1.1 处理不同数据类型数组

std::find 不仅适用于整型数组，对于其他基本数据类型数组同样适用，比如 char、double 等。以 char 数组为例：

#include <iostream>
#include <algorithm>

int main() {
    char charArr[] = {'a', 'b', 'c', 'd', 'e'};
    char targetChar = 'c';

    char* charResult = std::find(std::begin(charArr), std::end(charArr), targetChar);

    if (charResult != std::end(charArr)) {
        std::cout << "字符 " << targetChar << " 找到，位置为：" << std::distance(std::begin(charArr), charResult) << std::endl;
    } else {
        std::cout << "字符 " << targetChar << " 未找到" << std::endl;
    }

    return 0;
}

对于自定义数据类型数组，只要定义了合适的相等比较运算符 ==，std::find 同样可以正常工作。例如，我们定义一个简单的 Point 类：

#include <iostream>
#include <algorithm>

class Point {
public:
    int x;
    int y;

    Point(int a, int b) : x(a), y(b) {}

    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

int main() {
    Point points[] = {Point(1, 2), Point(3, 4), Point(5, 6)};
    Point targetPoint(3, 4);

    Point* pointResult = std::find(std::begin(points), std::end(points), targetPoint);

    if (pointResult != std::end(points)) {
        std::cout << "点 (" << targetPoint.x << ", " << targetPoint.y << ") 找到，位置为：" << std::distance(std::begin(points), pointResult) << std::endl;
    } else {
        std::cout << "点 (" << targetPoint.x << ", " << targetPoint.y << ") 未找到" << std::endl;
    }

    return 0;
}

在这个示例中，我们为 Point 类定义了 == 运算符，使得 std::find 能够在 Point 数组中查找目标点。

2. 在容器中查找元素

C++ 的STL提供了多种容器，std::find 可以方便地在这些容器中查找元素。

2.1 在序列容器（Sequence Containers）中查找

2.1.1 std::vector

std::vector 是最常用的序列容器之一，它提供了动态数组的功能。使用 std::find 在 std::vector 中查找元素非常直接。

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

int main() {
    std::vector<int> vec = {10, 20, 30, 40, 50};
    int target = 30;

    auto result = std::find(vec.begin(), vec.end(), target);

    if (result != vec.end()) {
        std::cout << "元素 " << target << " 找到，位置为：" << std::distance(vec.begin(), result) << std::endl;
    } else {
        std::cout << "元素 " << target << " 未找到" << std::endl;
    }

    return 0;
}

在这个例子中，我们使用 std::vector<int> 定义了一个整型向量 vec，然后通过 std::find 在 vec 中查找目标元素 target。

2.1.2 std::list

std::list 是双向链表容器，它在插入和删除元素方面具有优势。在 std::list 中使用 std::find 与在 std::vector 中类似。

#include <iostream>
#include <list>
#include <algorithm>

int main() {
    std::list<int> lst = {10, 20, 30, 40, 50};
    int target = 30;

    auto result = std::find(lst.begin(), lst.end(), target);

    if (result != lst.end()) {
        std::cout << "元素 " << target << " 找到，位置为：" << std::distance(lst.begin(), result) << std::endl;
    } else {
        std::cout << "元素 " << target << " 未找到" << std::endl;
    }

    return 0;
}

需要注意的是，由于 std::list 是链表结构，不支持随机访问，所以计算位置时使用 std::distance 相对 std::vector 效率会低一些，因为 std::list 的迭代器需要逐个移动来计算距离。

2.1.3 std::deque

std::deque（双端队列）结合了数组和链表的优点，支持在两端快速插入和删除元素。在 std::deque 中查找元素也很简单。

#include <iostream>
#include <deque>
#include <algorithm>

int main() {
    std::deque<int> deq = {10, 20, 30, 40, 50};
    int target = 30;

    auto result = std::find(deq.begin(), deq.end(), target);

    if (result != deq.end()) {
        std::cout << "元素 " << target << " 找到，位置为：" << std::distance(deq.begin(), result) << std::endl;
    } else {
        std::cout << "元素 " << target << " 未找到" << std::endl;
    }

    return 0;
}

std::deque 的迭代器支持随机访问，所以在计算位置时与 std::vector 类似，效率相对较高。

2.2 在关联容器（Associative Containers）中查找

2.2.1 std::map

std::map 是一个键值对容器，它根据键进行排序。虽然 std::map 有自己的 find 成员函数，但我们也可以使用 std::find 来查找元素。不过需要注意的是，std::map 的 find 成员函数效率更高，因为它利用了红黑树的特性进行快速查找。

#include <iostream>
#include <map>
#include <algorithm>

int main() {
    std::map<int, std::string> myMap = {
        {1, "one"},
        {2, "two"},
        {3, "three"}
    };

    auto it = std::find(myMap.begin(), myMap.end(), std::make_pair(2, "two"));

    if (it != myMap.end()) {
        std::cout << "元素找到，键为：" << it->first << "，值为：" << it->second << std::endl;
    } else {
        std::cout << "元素未找到" << std::endl;
    }

    return 0;
}

在这个例子中，我们使用 std::find 在 std::map 中查找特定的键值对。由于 std::map 是根据键排序的，使用 std::find 进行查找的时间复杂度相对较高，为 O(n)，而 std::map 自身的 find 成员函数时间复杂度为 O(log n)。

2.2.2 std::unordered_map

std::unordered_map 也是键值对容器，但它基于哈希表实现，不保证元素的顺序。同样，std::unordered_map 有自己的高效 find 成员函数，不过我们也可以使用 std::find。

#include <iostream>
#include <unordered_map>
#include <algorithm>

int main() {
    std::unordered_map<int, std::string> myUnorderedMap = {
        {1, "one"},
        {2, "two"},
        {3, "three"}
    };

    auto it = std::find(myUnorderedMap.begin(), myUnorderedMap.end(), std::make_pair(2, "two"));

    if (it != myUnorderedMap.end()) {
        std::cout << "元素找到，键为：" << it->first << "，值为：" << it->second << std::endl;
    } else {
        std::cout << "元素未找到" << std::endl;
    }

    return 0;
}

std::unordered_map 自身的 find 成员函数平均时间复杂度为 O(1)，而使用 std::find 的时间复杂度为 O(n)，因此在实际应用中，应优先使用 std::unordered_map 的 find 成员函数进行查找。

2.2.3 std::set

std::set 是一个有序集合，它存储的元素是唯一的，并且根据元素值进行排序。使用 std::find 在 std::set 中查找元素如下：

#include <iostream>
#include <set>
#include <algorithm>

int main() {
    std::set<int> mySet = {10, 20, 30, 40, 50};
    int target = 30;

    auto result = std::find(mySet.begin(), mySet.end(), target);

    if (result != mySet.end()) {
        std::cout << "元素 " << target << " 找到" << std::endl;
    } else {
        std::cout << "元素 " << target << " 未找到" << std::endl;
    }

    return 0;
}

与 std::map 类似，std::set 也有自己的 find 成员函数，其时间复杂度为 O(log n)，而使用 std::find 的时间复杂度为 O(n)，所以通常优先使用 std::set 的 find 成员函数。

2.2.4 std::unordered_set

std::unordered_set 是无序集合，基于哈希表实现，元素也是唯一的。在 std::unordered_set 中使用 std::find 查找元素：

#include <iostream>
#include <unordered_set>
#include <algorithm>

int main() {
    std::unordered_set<int> myUnorderedSet = {10, 20, 30, 40, 50};
    int target = 30;

    auto result = std::find(myUnorderedSet.begin(), myUnorderedSet.end(), target);

    if (result != myUnorderedSet.end()) {
        std::cout << "元素 " << target << " 找到" << std::endl;
    } else {
        std::cout << "元素 " << target << " 未找到" << std::endl;
    }

    return 0;
}

同样，std::unordered_set 自身的 find 成员函数平均时间复杂度为 O(1)，使用 std::find 时间复杂度为 O(n)，实际应用中优先使用其自身的 find 成员函数。

3. 自定义比较函数的应用

在某些情况下，默认的相等比较运算符 == 不能满足我们的查找需求，这时可以使用自定义的比较函数。std::find_if 算法可以实现这一功能，它会在指定范围内查找满足特定条件的元素。不过，我们也可以通过包装 std::find 来达到类似效果。

假设有一个包含字符串的 std::vector，我们想要忽略大小写查找某个字符串。可以定义如下自定义比较函数：

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

bool ignoreCaseCompare(const std::string& a, const std::string& b) {
    if (a.size() != b.size()) return false;
    for (size_t i = 0; i < a.size(); ++i) {
        if (std::tolower(a[i]) != std::tolower(b[i])) {
            return false;
        }
    }
    return true;
}

int main() {
    std::vector<std::string> strVec = {"Hello", "world", "HELLO"};
    std::string target = "hello";

    auto it = std::find_if(strVec.begin(), strVec.end(), [&target](const std::string& s) {
        return ignoreCaseCompare(s, target);
    });

    if (it != strVec.end()) {
        std::cout << "字符串 " << target << " 找到" << std::endl;
    } else {
        std::cout << "字符串 " << target << " 未找到" << std::endl;
    }

    return 0;
}

在上述代码中，我们定义了 ignoreCaseCompare 函数来进行忽略大小写的字符串比较。然后通过 std::find_if 和 lambda 表达式来在 std::vector 中查找满足条件的字符串。

3.1 在自定义数据类型容器中的应用

对于自定义数据类型的容器，自定义比较函数的应用更为常见。例如，有一个包含 Person 类对象的 std::vector，我们想根据 Person 的某个成员变量进行查找。

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

class Person {
public:
    std::string name;
    int age;

    Person(const std::string& n, int a) : name(n), age(a) {}
};

bool compareByAge(const Person& a, int targetAge) {
    return a.age == targetAge;
}

int main() {
    std::vector<Person> people = {
        Person("Alice", 25),
        Person("Bob", 30),
        Person("Charlie", 35)
    };
    int targetAge = 30;

    auto it = std::find_if(people.begin(), people.end(), [targetAge](const Person& p) {
        return compareByAge(p, targetAge);
    });

    if (it != people.end()) {
        std::cout << "找到年龄为 " << targetAge << " 的人，名字是：" << it->name << std::endl;
    } else {
        std::cout << "未找到年龄为 " << targetAge << " 的人" << std::endl;
    }

    return 0;
}

在这个例子中，我们定义了 compareByAge 函数，通过 std::find_if 和 lambda 表达式在 std::vector<Person> 中查找年龄为 targetAge 的人。

4. 查找子序列

std::find 还可以用于查找子序列。std::search 算法可以在一个序列中查找另一个子序列，其原理与 std::find 类似。

假设有两个 std::vector，我们要在一个较大的向量中查找一个较小的向量作为子序列。

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

int main() {
    std::vector<int> bigVec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::vector<int> subVec = {4, 5, 6};

    auto it = std::search(bigVec.begin(), bigVec.end(), subVec.begin(), subVec.end());

    if (it != bigVec.end()) {
        std::cout << "子序列找到，起始位置为：" << std::distance(bigVec.begin(), it) << std::endl;
    } else {
        std::cout << "子序列未找到" << std::endl;
    }

    return 0;
}

在上述代码中，std::search 函数在 bigVec 中查找 subVec 作为子序列。如果找到，通过 std::distance 计算子序列的起始位置。

4.1 自定义子序列比较

与单个元素查找类似，在查找子序列时也可以使用自定义的比较函数。例如，我们有两个包含字符串的 std::vector，想要在一个向量中查找另一个向量作为子序列，并且忽略字符串的大小写。

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

bool ignoreCaseStrCompare(const std::string& a, const std::string& b) {
    if (a.size() != b.size()) return false;
    for (size_t i = 0; i < a.size(); ++i) {
        if (std::tolower(a[i]) != std::tolower(b[i])) {
            return false;
        }
    }
    return true;
}

bool ignoreCaseSubSeqCompare(const std::vector<std::string>& big, const std::vector<std::string>& sub) {
    if (sub.size() > big.size()) return false;
    for (size_t i = 0; i <= big.size() - sub.size(); ++i) {
        bool match = true;
        for (size_t j = 0; j < sub.size(); ++j) {
            if (!ignoreCaseStrCompare(big[i + j], sub[j])) {
                match = false;
                break;
            }
        }
        if (match) return true;
    }
    return false;
}

int main() {
    std::vector<std::string> bigStrVec = {"Hello", "World", "HELLO"};
    std::vector<std::string> subStrVec = {"world", "HELLO"};

    if (ignoreCaseSubSeqCompare(bigStrVec, subStrVec)) {
        std::cout << "子序列找到" << std::endl;
    } else {
        std::cout << "子序列未找到" << std::endl;
    }

    return 0;
}

在这个例子中，我们定义了 ignoreCaseStrCompare 用于忽略大小写的字符串比较，ignoreCaseSubSeqCompare 用于忽略大小写的子序列比较。通过这种方式，我们可以在更复杂的场景下查找子序列。

5. 结合其他算法使用

std::find 可以与其他STL算法结合使用，以实现更复杂的功能。

5.1 与 std::transform 结合

std::transform 算法用于对指定范围内的每个元素应用一个函数，并将结果存储到另一个位置。我们可以先使用 std::transform 对容器中的元素进行某种变换，然后再使用 std::find 查找变换后的元素。

假设有一个包含整数的 std::vector，我们想先将每个元素平方，然后查找某个平方值。

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

int square(int num) {
    return num * num;
}

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::vector<int> squaredVec(vec.size());

    std::transform(vec.begin(), vec.end(), squaredVec.begin(), square);

    int targetSquare = 9;

    auto it = std::find(squaredVec.begin(), squaredVec.end(), targetSquare);

    if (it != squaredVec.end()) {
        std::cout << "平方值 " << targetSquare << " 找到，原位置为：" << std::distance(squaredVec.begin(), it) << std::endl;
    } else {
        std::cout << "平方值 " << targetSquare << " 未找到" << std::endl;
    }

    return 0;
}

在上述代码中，我们先使用 std::transform 将 vec 中的每个元素平方，并存储到 squaredVec 中。然后使用 std::find 在 squaredVec 中查找目标平方值。

5.2 与 std::filter（C++20 引入）结合

C++20 引入了 std::filter 算法，它可以根据给定的谓词对容器中的元素进行过滤。我们可以先使用 std::filter 过滤出符合条件的元素，然后使用 std::find 在过滤后的结果中查找特定元素。

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

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    int target = 3;

    auto filteredRange = vec | std::views::filter([](int num) { return num % 2 != 0; });

    auto it = std::find(filteredRange.begin(), filteredRange.end(), target);

    if (it != filteredRange.end()) {
        std::cout << "元素 " << target << " 在奇数过滤后找到" << std::endl;
    } else {
        std::cout << "元素 " << target << " 在奇数过滤后未找到" << std::endl;
    }

    return 0;
}

在这个例子中，我们使用 std::views::filter 过滤出 vec 中的奇数，然后在过滤后的范围中使用 std::find 查找目标元素 target。

通过以上不同应用场景的介绍，我们可以看到 std::find 及其相关算法在C++ 编程中具有广泛的用途，能够帮助我们高效地处理各种查找需求。无论是简单数组、复杂容器，还是结合其他算法，都能展现出其强大的功能。在实际编程中，我们应根据具体需求选择最合适的方式来使用这些算法，以提高代码的效率和可读性。