C++高级学习：第十七节-查找算法（上）

Cpp入门到精通 2024-03-17

点击蓝字关注我们

c++高级学习

第十七节查找算法（上）

STL提供了多种查找算法，这些算法可以在各种容器中按照某种特定条件查找元素。

下面我们介绍常用的STL查找算法：

find()：在容器中查找指定值的元素，返回指向该元素的迭代器，如果未找到，则返回容器的end()迭代器。我们之前涉及到该查询函数，在这里我们学习一个新的函数distance 函数。distance函数用来计算两个迭代器之间的距离，包括容器的起始迭代器和结束迭代器。比如如下例子：

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
void print(int x) {
  cout << x << " ";
}
int main() {
  vector<int>v1 = { 60,40,20,30,40,10,60 };
  cout << "vector容器：";
  for_each(v1.begin(), v1.end(), print);
  cout << endl;
  auto it=find(v1.begin(), v1.end(), 40);
  auto index = distance(v1.begin(), it);
  if (it != v1.end()) {
    cout <<"容器中找到元素："<<*it << endl;
    cout << "该元素的位置在：" << index << endl;
  }
  else {
    cout << "未找到该元素！" << endl;
  }
  system("pause");
  return 0;
}

结果如下：

vector容器：60 40 20 30 40 10 60
容器中找到元素：40
该元素的位置在：1

我们使用distance函数计算了迭代器 v1.begin() 和 it 之间的距离，这种方式可以用来表示 it 指向的元素在容器 v1 中的位置。

这里我们使用auto关键字，可能之前涉及到，但是没有讲过为什么在这里这样用。auto 关键字用于声明变量，其作用是根据变量的初始值自动推导出变量的类型。在这种情况下，auto 会让编译器根据 find() 函数的返回类型推导出变量 it 的类型。比如说这里可以自动推导为vector容器的迭代器类型。如果不使用 auto 关键字，你需要显式地指定变量 it 的类型，比如上述例子我们就这样写：

vector<int>::iterator it = find(v1.begin(), v1.end(), 40);

distance函数也使用了auto，它的类型通常是迭代器的 difference_type 类型。

vector<int>::difference_type index = distance(v1.begin(), it);

在以后的学习中，我们一般都会使用auto关键字，可以减少代码中的重复，特别是当你知道变量的类型可以从初始化语句中推导出来时。

find_if()：根据给定的条件，在容器中查找满足条件的元素，返回指向该元素的迭代器，如果未找到，则返回容器的end()迭代器。我们只给出与上面代码不同的地方。

bool compare(int m) {
  return m >50;
}


  auto it = find_if(v1.begin(), v1.end(), compare);
  auto index = distance(v1.begin() , it);
  if (it != v1.end()) {
    cout << "容器中找到大于50的元素：" << *it << endl;
    cout << "该元素的位置在：" << index << endl;
  }
  else {
    cout << "未找到该元素！" << endl;
  }

我们利用上述方式去查找容器中是否有大于50的元素，返回指向该元素的迭代器，如果未找到，则返回容器的end()迭代器，并给出其在容器中的位置。

vector容器：60 40 20 30 40 10 60
容器中找到大于50的元素：60
该元素的位置在：0

adjacent_find：用于在序列中查找相邻的重复元素。这个函数接受两个迭代器作为参数，分别是 first 和 last，表示待查找的序列的起始和结束位置。

auto it = adjacent_find(v1.begin(), v1.end());
  auto index = distance(v1.begin(), it);
  if (it != v1.end()) {
    cout << "容器中找到相邻重复元素：" << *it << endl;
    cout << "相邻元素首次出现的位置在：" << index << endl;
  }
  else {
    cout << "未找到该元素！" << endl;
  }

该函数在整个容器中查找是否有相邻重复元素，找到则返回指向第一个重复元素的迭代器，未找到则返回end()。

vector容器：60 40 20 30 40 40 60
容器中找到相邻重复元素：40
相邻元素首次出现的位置在：4

binary_search 算法来在已排序的序列中执行二分查找，以查找特定的元素。

bool index=binary_search(v1.begin(), v1.end(), 40);
  if (index) {
    cout <<"容器中找到该元素！" << endl;
  }
  else {
    cout << "未找到该元素！" << endl;
  }

binary_search和find都用来查找单个指定元素，他们有什么区别？

binary_search 返回一个布尔值，指示是否找到了目标值。find 返回一个迭代器，指向第一个匹配到的目标值。它假定序列已经排序，并且在一个已排序的序列中查找目标值。因此，它适用于数组或其他有序容器。(当然，其他容器也不是不行)。而find 用于在任意序列中查找目标值，不需要预先排序。它会在序列中线性搜索目标值。

如果你知道序列是有序的，并且你希望在有序序列中进行快速的查找操作，那么应该使用binary_search。如果你只是需要在序列中查找某个特定值，并且序列可能是无序的，那么应该使用find。

查找算法的部分操作的讲解到此结束，感谢观看！欢迎各位的点赞与关注！您的点赞和关注是我学习更新的动力！

END

往期推荐