突破编程_C++_STL教程（ find 算法）

1 std::find 算法的概念与用途

std::find 是 C++ 标准库 <algorithm> 中的一个非常有用的算法。这个算法用于在一个范围内查找指定的元素，并返回该元素的迭代器。如果元素不存在于该范围内，则返回范围的尾迭代器。

std::find 的基本概念是遍历一个给定的范围（通常是容器，如 vector, list, array 等），并检查每个元素是否等于给定的值。当找到匹配的元素时，它立即停止搜索并返回指向该元素的迭代器。如果遍历完整个范围都没有找到匹配的元素，则返回范围的尾迭代器。

std::find 的用途非常广泛，特别是在处理容器和序列时。以下是一些常见的用途：

• 查找元素是否存在：可以使用 std::find 来检查一个元素是否存在于某个容器中。通过比较返回的迭代器与范围的尾迭代器，可以确定元素是否存在。
• 查找并处理元素：除了简单地检查元素是否存在，还可以使用 std::find 的返回迭代器来访问和操作找到的元素。例如，可以修改它的值或执行其他操作。
• 删除元素：结合其他算法（如 std::remove 和 container.erase），可以使用 std::find 来查找并删除容器中的特定元素。
• 替换元素：找到元素后，可以使用返回的迭代器来替换该元素的值。

2 std::find 算法基础

2.1 std::find 算法的定义与语法

（1）定义：

std::find 是一个模板函数，用于在给定范围内查找一个特定元素。它接受两个迭代器（表示范围的起始和结束）和一个要查找的值作为参数。函数会遍历这个范围，直到找到与给定值相等的元素或到达范围的末尾。

（2）语法：

std::find 的基本语法如下：

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

• InputIt 是一个输入迭代器类型，它表示可以读取容器中元素但可能不支持写入的迭代器类型。这可以是任何符合输入迭代器要求的迭代器类型，如 std::vector::iterator、std::list::iterator 等。
• first 和 last 是输入迭代器，分别指向要搜索的范围的开始和结束。注意，last 不包含在搜索范围内，即范围是 [first, last)。
• value 是要查找的值，它可以是任何可以与范围内元素进行比较的类型。

（3）返回值：

std::find 返回一个迭代器，指向在序列中找到的第一个与 value 相等的元素。如果序列中不存在该元素，则返回 last 迭代器，即范围的结束迭代器。

2.2 std::find 算法的基本使用示例

std::find 算法的基本使用示例非常直观，下面是一个简单的例子：

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

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

	// 使用 std::find 查找元素  
	auto it = std::find(numbers.begin(), numbers.end(), value_to_find);

	// 检查是否找到元素  
	if (it != numbers.end()) {
		std::cout << "Found " << value_to_find << std::endl;
	}
	else {
		std::cout << value_to_find << " not found in the vector." << std::endl;
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

上面代码的输出为：

Found 3 
1

这个例子创建了一个包含整数的 std::vector，并使用 std::find 来查找值为 3 的元素。如果找到该元素，则打印出它的位置；否则，打印出未找到的消息。

2.3 注意事项

• std::find 执行的是线性搜索，因此在大型容器中可能不是最高效的搜索方法。如果容器中的元素已排序，使用其他算法（如 std::lower_bound 或 std::binary_search）可能更为高效。
• std::find 可以用于任何可以通过迭代器访问的容器，如 std::vector、std::list、std::array 等。
• std::find 不会修改容器或其中的元素；它只是查找元素并返回迭代器。
• 如果序列中包含多个与 value 相等的元素，std::find 只返回找到的第一个元素的迭代器。如果需要找到所有匹配的元素，你需要使用循环或其他方法结合 std::find。

3 std::find 算法的高级用法

3.1 结合 std::distance 计算元素位置

std::find 和 std::distance 经常一起使用来查找容器中元素的位置。std::find 用于在序列中查找特定的元素，并返回一个指向该元素的迭代器。而 std::distance 则用于计算两个迭代器之间的距离，即它们之间元素的数量。

当需要知道某个元素在容器中的位置（即它的索引）时，可以结合使用 std::find 和 std::distance。下面是一个简单的示例，展示了如何结合使用这两个算法来计算元素在 std::vector 中的位置：

#include <iostream>  
#include <vector>  
#include <algorithm>  
#include <iterator> // 需要包含这个头文件来使用 std::distance  

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

	// 使用 std::find 查找元素  
	auto it = std::find(numbers.begin(), numbers.end(), value_to_find);

	// 检查是否找到元素  
	if (it != numbers.end()) {
		// 使用 std::distance 计算元素位置（索引）  
		size_t position = std::distance(numbers.begin(), it);
		std::cout << "Found " << value_to_find << " at position: " << position << std::endl;
	}
	else {
		std::cout << value_to_find << " not found in the vector." << std::endl;
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

上面代码的输出为：

Found 3 at position: 2
1

这个例子首先使用 std::find 来查找值为 3 的元素。如果找到了这个元素（即返回的迭代器 it 不等于 numbers.end()），就使用 std::distance 来计算从 numbers.begin() 到 it 的距离，这个距离就是元素在 std::vector 中的位置（索引）。

注意：C++ 容器的迭代器通常支持随机访问迭代器（如 std::vector 的迭代器），这意味着 std::distance 的计算是常数时间的。然而，对于只支持前向迭代器的容器（如 std::list），std::distance 的计算将是线性的，因为它需要逐个遍历元素来计算距离。因此，在使用 std::distance 时，要考虑容器的迭代器类型以及可能的性能影响。

3.2 查找多个相同的元素

std::find 会返回找到的第一个匹配元素的迭代器。如果序列中有多个相同的元素，std::find 不会返回其他匹配项。如果你想找到所有匹配项，你需要使用一个循环来重复调用 std::find，并在每次找到元素后将迭代器移动到找到的元素之后，然后继续搜索。下面是一个找到所有匹配项的示例：

#include <iostream>  
#include <vector>  
#include <algorithm>  
  
int main() {  
    std::vector<int> numbers = {1, 2, 3, 4, 5, 3, 6, 7, 3};  
    int value_to_find = 3;  
  
    // 初始化迭代器指向序列的开始  
    auto it = numbers.begin();  
    while (it != numbers.end()) {  
        // 使用 std::find 从当前位置开始查找元素  
        it = std::find(it, numbers.end(), value_to_find);  
  
        // 检查是否找到元素  
        if (it != numbers.end()) {  
            std::cout << "Found " << value_to_find << " at position: "   
                      << std::distance(numbers.begin(), it) << std::endl;  
            // 移动迭代器到找到的元素之后，以便在下次循环中找到下一个匹配项  
            ++it;  
        } else {  
            // 如果没有找到元素，退出循环  
            break;  
        }  
    }  
  
    return 0;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

上面代码的输出为：

Found 3 at position: 2
Found 3 at position: 5
Found 3 at position: 8
1
2
3

这个例子使用一个 while 循环来重复调用 std::find，并在每次找到元素后移动迭代器。这样，就可以找到序列中所有匹配的值。如果 std::find 返回 numbers.end()，说明没有找到更多的匹配项，就退出循环。

3.3 与算法库中的其他函数结合使用

std::find 经常与其他算法库中的函数结合使用，以实现更复杂的搜索和操作任务。下面是两个简单的示例，展示了如何将 std::find 与其他算法库函数结合使用：

（1）与 std::remove_if 结合使用

可以使用 std::find 来查找特定元素，然后使用 std::remove_if 来移除所有匹配该元素的项。std::remove_if 不会实际从容器中删除元素，而是将所有不匹配的元素移动到容器的开始部分，并返回一个指向新逻辑末尾的迭代器。

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

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

	// 查找值  
	auto it = std::find(numbers.begin(), numbers.end(), value_to_remove);

	// 如果找到值，则使用 remove_if 移除所有匹配项  
	if (it != numbers.end()) {
		numbers.erase(std::remove_if(numbers.begin(), numbers.end(),
			[&value_to_remove](int num) { return num == value_to_remove; }),
			numbers.end());
	}

	// 输出修改后的 vector  
	for (int num : numbers) {
		std::cout << num << ' ';
	}
	std::cout << std::endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

上面代码的输出为：

1 2 4 5
1

（2）与 std::transform 结合使用

可以使用 std::find 来定位元素，然后使用 std::transform 来修改容器中的元素，尤其是当你想要对除了找到的元素之外的所有元素应用某种转换时。

#include <iostream>  
#include <vector>  
#include <algorithm>  
#include <functional> // 用于 std::plus 和 std::bind  

int main() 
{
	std::vector<int> numbers = { 1, 2, 3, 4, 5 };
	int value_to_exclude = 3;
	int add_value = 10;

	// 查找值  
	auto it = std::find(numbers.begin(), numbers.end(), value_to_exclude);

	// 如果没有找到值，则对所有元素应用转换  
	if (it == numbers.end()) {
		std::transform(numbers.begin(), numbers.end(), numbers.begin(),
			std::bind(std::plus<int>(), std::placeholders::_1, add_value));
	}
	else {
		// 如果找到值，则对找到值之前的元素应用转换  
		std::transform(numbers.begin(), it, numbers.begin(),
			std::bind(std::plus<int>(), std::placeholders::_1, add_value));
		// 对找到值之后的元素应用转换，注意跳过已找到的元素  
		std::transform(std::next(it), numbers.end(), std::next(it),
			std::bind(std::plus<int>(), std::placeholders::_1, add_value));
	}

	// 输出修改后的 vector  
	for (int num : numbers) {
		std::cout << num << ' ';
	}
	std::cout << std::endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

上面代码的输出为：

11 12 3 14 15
1

4 自定义类型的使用

std::find 算法不仅可以用于查找基本类型（如 int、char 等）的元素，还可以用于查找自定义类型的元素。为了使用 std::find 查找自定义类型的元素，需要提供一个能够比较自定义类型对象的谓词（predicate），这通常是一个函数或函数对象（例如，lambda 表达式或重载了 operator() 的类的对象）。

下面是一个示例，展示了如何使用 std::find 来查找 std::vector 中自定义类型元素的示例：

首先，定义一个自定义类型：

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

// 自定义类型  
struct Person {
	std::string name;
	int age;

	// 构造函数  
	Person(const std::string& n, int a) : name(n), age(a) {}

	// 重载 operator== 用于比较两个 Person 对象  
	bool operator==(const Person& other) const {
		return name == other.name && age == other.age;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

然后，可以使用 std::find 来查找 std::vector<Person> 中的元素。假设有一个要查找的特定 Person 对象，可以这样使用 std::find：

int main() 
{
	// 创建一个包含 Person 对象的 vector  
	std::vector<Person> people = {
		Person("Alice", 30),
		Person("Bob", 25),
		Person("Charlie", 35),
		Person("Alice", 20) // 注意这里有两个名为 "Alice" 的人，但年龄不同  
	};

	// 要查找的 Person 对象  
	Person personToFind("Alice", 30);

	// 使用 std::find 查找 personToFind  
	auto it = std::find(people.begin(), people.end(), personToFind);

	if (it != people.end()) {
		std::cout << "Found " << it->name << " with age " << it->age << std::endl;
	}
	else {
		std::cout << "Person not found." << std::endl;
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

上面代码的输出为：

Found Alice with age 30
1

这个例子为 Person 类型重载了 operator==，这使得 std::find 能够使用它来比较 vector 中的元素和要查找的 personToFind 对象。如果找到匹配的元素，std::find 返回一个指向该元素的迭代器；否则，它返回 end() 迭代器，表示没有找到。

如果不想或不能重载 operator==，也可以提供一个单独的函数或 lambda 表达式作为谓词：

// 自定义比较函数  
bool comparePersons(const Person& a, const Person& b) {  
    return a.name == b.name && a.age == b.age;  
}  
  
// ...  
  
// 使用自定义比较函数作为谓词  
auto it = std::find_if(people.begin(), people.end(),   
                        [&personToFind](const Person& p) {  
                            return comparePersons(p, personToFind);  
                        });
1
2
3
4
5
6
7
8
9
10
11
12

这里使用了 std::find_if 而不是 std::find，因为 std::find_if 允许提供一个谓词函数（在这里是一个 lambda 表达式），该函数定义了如何比较元素。谓词函数 comparePersons 用于比较 vector 中的每个元素和 personToFind 对象。如果找到匹配的元素，std::find_if 的行为与 std::find 相同。

5 优化查找效率

5.1 使用排序容器

使用排序容器（如 std::set 或 std::map）而不是 std::vector 或 std::list 等无序容器，可以显著提高查找特定元素的性能（使用容器自己的 find 方法），尤其是当数据量很大时。这是因为排序容器内部通过特定的数据结构（如红黑树）维护了元素的排序状态，从而允许在对数时间内完成查找操作。

下面是一个使用 std::set 的示例，展示了如何查找自定义类型元素：

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

// 自定义类型  
struct Person {
	std::string name;
	int age;

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

	// 重载 operator< 用于排序  
	bool operator<(const Person& other) const {
		if (name == other.name) {
			return age < other.age;
		}
		return name < other.name;
	}
};

int main() 
{
	// 创建一个包含 Person 对象的 set 容器  
	std::set<Person> people = {
		Person("Alice", 30),
		Person("Bob", 25),
		Person("Charlie", 35),
		Person("Alice", 20) // 这里的 "Alice" 由于 age 不同，所以可以存储在 set 中  
	};

	// 要查找的 Person 对象  
	Person personToFind("Alice", 30);

	// 使用 set 的 find 方法查找 personToFind  
	auto it = people.find(personToFind);

	if (it != people.end()) {
		std::cout << "Found " << it->name << " with age " << it->age << std::endl;
	}
	else {
		std::cout << "Person not found." << std::endl;
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

上面代码的输出为：

Found Alice with age 30
1

这个例子使用了 std::set 来存储 Person 对象，并重载了 operator< 来定义排序规则。这样，std::set 会根据提供的排序规则对元素进行自动排序。

当需要查找某个元素时，可以使用 std::set 的成员函数 find，它在对数时间内返回指向元素的迭代器（如果找到的话）。这比在无序容器中使用 std::find 进行线性搜索要高效得多。

请注意，为了使用 std::set 的 find 方法，示例中自定义类型必须定义比较运算符（如 operator<），以便容器能够正确地排序和查找元素。如果不想或不能修改自定义类型，可以提供一个比较对象或函数作为 std::set 的模板参数。

使用排序容器的另一个好处是它们提供了额外的功能，如自动去重（对于基于键的容器如 std::set 和 std::map）和范围查询（如查找大于某个值的所有元素）。这些功能在某些应用中可能非常有用。

5.2 使用二分查找

std::find 在无序容器中执行线性搜索，其时间复杂度为 O(n)，其中 n 是容器中元素的数量。然而，如果容器是有序的，你可以使用二分查找算法来优化搜索过程，将时间复杂度降低到 O(log n)。C++ 标准库并没有直接提供一个使用二分查找的 std::find 版本，但可以使用 std::lower_bound 或 std::upper_bound 等算法，这些算法在有序范围上执行二分查找。

下面是一个使用 std::lower_bound 进行二分查找的示例，假设有一个有序的 std::vector<Person>，并且想要查找一个特定的 Person 对象：

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

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

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

	bool operator<(const Person& other) const {
		if (name == other.name) {
			return age < other.age;
		}
		return name < other.name;
	}

	bool operator==(const Person& other) const {
		return name == other.name && age == other.age;
	}
};

// 二分查找函数，使用 std::lower_bound  
std::vector<Person>::iterator binary_find(std::vector<Person>& people, const Person& target) {
	auto it = std::lower_bound(people.begin(), people.end(), target);
	if (it != people.end() && *it == target) {
		return it;
	}
	return people.end();
}

int main() 
{
	// 创建一个有序的 vector 容器  
	std::vector<Person> people = {
		Person("Alice", 20),
		Person("Alice", 30),
		Person("Bob", 25),
		Person("Charlie", 35)
	};

	// 要查找的 Person 对象  
	Person personToFind("Alice", 30);

	// 使用二分查找  
	auto it = binary_find(people, personToFind);

	if (it != people.end()) {
		std::cout << "Found " << it->name << " with age " << it->age << std::endl;
	}
	else {
		std::cout << "Person not found." << std::endl;
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

上面代码的输出为：

Found Alice with age 30
1

这个例子定义了一个 binary_find 函数，它接受一个 std::vector<Person>和一个目标 Person 对象作为参数。它使用 std::lower_bound 来找到第一个不小于目标元素的迭代器。然后，它检查找到的元素是否确实等于目标元素。如果是，它返回该迭代器；否则，它返回 end() 迭代器来表示未找到。

注意：为了使用二分查找，容器必须是已经排序的。如果容器未排序，则二分查找的结果将是错误的。在这个例子中，假设 people 容器在创建时就已经是有序的。如果容器在运行时可能会改变，则需要在每次搜索之前对其进行排序，但这将牺牲插入和删除操作的效率。因此，在决定使用二分查找之前，需要权衡搜索、插入和删除操作的频率和性能要求。