7.1 C++ STL 非变易查找算法

发表于 2023-07-20 分类于《灰帽黑客：攻守道》

C++ STL 中的非变易算法（Non-modifying Algorithms）是指那些不会修改容器内容的算法，是C++提供的一组模板函数，该系列函数不会修改原序列中的数据，而是对数据进行处理、查找、计算等操作，并通过迭代器实现了对序列元素的遍历与访问。由于迭代器与算法是解耦的，因此非变易算法可以广泛地应用于各种容器上，提供了极高的通用性和灵活性。

这些算法都是在头文件 <algorithm> 中定义的，其主要包括以下几类非变易算法：

查找算法：
- find()：在容器中查找指定值的元素，并返回第一个匹配的位置。
- find_if()：根据给定的条件（函数对象或谓词）查找容器中满足条件的元素，并返回第一个匹配的位置。
- count()：计算容器中等于指定值的元素个数。
遍历算法：
- for_each()：对容器中的每个元素应用指定的函数。
- accumulate()：计算容器中元素的累加和。
- count_if()：计算满足给定条件的元素个数。
排序算法（不属于查找和遍历，但不会修改元素内容）：
- sort()：对容器中的元素进行排序，默认是按升序排列。
- partial_sort()：对容器中的部分元素进行排序。
- stable_sort()：稳定地对容器中的元素进行排序。

通过它们可以高效地操作容器中的元素，这为C++开发者提供了更方便和安全的方式来处理数据，减少了代码的复杂性和错误的可能性。通过合理地运用这些算法，可以极大地提高程序的执行效率和代码的可读性。

7.1 遍历容器元素

For_each 算法函数，用于对序列中的每个元素执行指定操作。for_each的用法如下：

template<class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f);

其中，first、last是迭代器，表示待执行操作的序列的范围；f是一个函数对象，用于指定要执行的操作。调用for_each函数后，将会对[first, last]区间内的每个元素调用一次f函数，并将该元素作为f函数的参数。for_each函数返回一个函数对象f。

该函数用于对容器的元素进行循环操作，常用于元素遍历。

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

using namespace std;

struct MyPrint{
  int count;                   // 设置元素计数
  MyPrint(){ count = 0; }      // 初始化元素
  void operator()(int x)       // 重载小括号
  {
    cout << x << endl;
    count++;
  }
};

int main(int argc, char* argv[])
{
  list<int> ls {1,2,3,4,5,6,7,8,9};

  MyPrint p = for_each(ls.begin(), ls.end(), MyPrint());
  cout << "Link Count: " << p.count << endl;
  system("pause");
  return 0;
}

7.2 普通查找容器元素

Find 算法函数，用于查找序列中指定值的第一个元素，并返回该元素的迭代器。find的用法如下：

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

其中，first、last是迭代器，表示待查找的序列的范围；value是需要查找的元素的值。调用find函数后，将会在[first, last]区间中查找第一个等于value的元素，并将该元素的迭代器作为函数返回值返回。如果未找到等于value的元素，则函数将返回last。

该算法用于查找某个值等于某值得元素，它在迭代区间是(frist,last)之间寻找value值。

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

using namespace std;

int main(int argc, char* argv[])
{
  list<int> ls{ 1, 2, 3, 4, 5, 6, 7, 8, 9 };

  list<int>::iterator it = find(ls.begin(), ls.end(),6);
  if (it != ls.end())
  {
    cout << "找到了元素" << endl;
    cout << "前一个元素: " << *(--it) << endl;
  }

  system("pause");
  return 0;
}

7.3 类查找容器元素

Find 算法函数，用于查找序列中指定值的第一个元素，并返回该元素的迭代器。find的用法如下：

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

该算法不仅可以查询普通数据结构，还可以查询结构与类中数据，如下则是一段演示案例；

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

using namespace std;

class Person
{
public:
  string m_name;
  int m_age;
public:Person(string name, int age){
    this->m_name = name;
    this->m_age = age;
  }
public: bool operator==(const Person &p){
  // 重载 == 实现遍历数据
    if (this->m_name == p.m_name && this->m_age == p.m_age)
      return true;
    return false;
  }
};

int main(int argc, char* argv[])
{
  vector<Person> var;

  Person p1("aaa", 10);
  Person p2("bbb", 20);
  Person p3("ccc", 30);
  var.push_back(p1);
  var.push_back(p2);
  var.push_back(p3);

  vector<Person>::iterator pos = find(var.begin(), var.end(), p1);
  if (pos != var.end())
    cout << "找到姓名: " << (*pos).m_name << endl;
  system("pause");
  return 0;
}

7.4 条件查找容器元素

Find_if 算法函数，用于查找序列中满足指定条件的第一个元素，并返回该元素的迭代器。find_if的用法如下：

template<class InputIterator, class UnaryPredicate>
InputIterator find_if(InputIterator first, InputIterator last, UnaryPredicate pred);

其中，first、last是迭代器，表示待查找的序列的范围；pred是一个一元谓词函数，用于指定查找条件。调用find_if函数后，将会在[first, last]区间中查找第一个谓词pred返回true的元素，并将该元素的迭代器作为函数返回值返回。如果未找到满足条件的元素，则函数将返回last。

与上方的普通查找相比，该查找可以添加回调函数，用于对查到的数据进行筛选和过滤操作，如下所示案例中寻找第一个被5整除的元素。

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

using namespace std;

bool MyFunction(int x) { return x % 5 ? 0 : 1; }

int main(int argc, char* argv[])
{
  vector<int> var(20);

  // 循环生成数据
  for (unsigned int x = 0; x < var.size(); x++)
    var[x] = (x + 1) * (x + 3);

  // 循环遍历,并判断是否符合条件
  vector<int>::iterator it = find_if(var.begin(),var.end(),MyFunction);
  if (it != var.end())
  {
    // 寻找第一个被5整除的元素
    cout << *it << endl;
    cout << "元素索引: " << it - var.begin() << endl;
  }
  system("pause");
  return 0;
}

7.5 条件查找类容器元素

Find_if 算法函数，用于查找序列中满足指定条件的第一个元素，并返回该元素的迭代器。find_if的用法如下：

template<class InputIterator, class UnaryPredicate>
InputIterator find_if(InputIterator first, InputIterator last, UnaryPredicate pred);

如下一个案例中，实现了查询Person类中的特定数据，查找ptr中的数据是否存在于我们的结构中。

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

using namespace std;

class Person
{
public:
  string m_name;
  int m_age;
public:Person(string name, int age){
       this->m_name = name;
       this->m_age = age;
}
public: bool operator==(const Person &p){
    // 重载 == 实现遍历数据
    if (this->m_name == p.m_name && this->m_age == p.m_age)
      return true;
    return false;
  }
};

// 使用binary_function适配函数实现传递两个Person数据
class MyCompare:public binary_function<Person *,Person *,bool>
{
public: bool operator()(Person *p1,Person *p2) const {
    // 对比函数,重载() 用于实现指针元素的对比
    if (p1->m_name == p2->m_name && p1->m_age == p2->m_age)
      return true;
    return false;
  }
};

int main(int argc, char* argv[])
{
  vector<Person *> var;

  Person p1("aaa", 10);
  Person p2("bbb", 20);
  Person p3("ccc", 30);
  var.push_back(&p1);
  var.push_back(&p2);
  var.push_back(&p3);

  // 查找这个属性的类成员
  Person *ptr = new Person("bbb", 20);

  // 通过使用bind2nd绑定事件,将ptr传递给MyCompare() 即可实现两个类属性的对比查找
  vector<Person *>::iterator pos = find_if(var.begin(), var.end(), bind2nd(MyCompare(),ptr));
  if (pos != var.end())
    cout << "找到姓名: " << (*pos)->m_name << endl;
  system("pause");
  return 0;
}

7.6 邻近查找容器元素

Adjacent_find 算法函数，用于查找相邻元素的第一个出现位置。adjacent_find的用法如下：

template<class InputIterator>
InputIterator adjacent_find(InputIterator first, InputIterator last);

其中，first、last是迭代器，表示待查找的序列的范围。调用adjacent_find函数后，将会在[first, last]区间中查找相邻元素的第一个出现位置，并将找到的元素的迭代器作为函数返回值返回。如果未找到相邻元素，则函数将返回last。

该函数用于查找相等或满足条件的相邻的重复的元素，找到了返回第一个出现位置的迭代器，如下则是一段演示案例；

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

using namespace std;

bool MyFunction(int x,int y) { return (x - y) % 2 == 0 ? 1 : 0; }

int main(int argc, char* argv[])
{
  list<int> ls {1,2,3,4,5,6,6,7,8,9,10};

  // 查找链表中邻接相等的元素
  list<int>::iterator it = adjacent_find(ls.begin(), ls.end());
  if (it != ls.end())
    cout << *it << endl;

  // 查找基偶性相同的邻接元素
  it = adjacent_find(ls.begin(), ls.end(), MyFunction);
  if (it != ls.end())
  {
    cout << *it << endl;
    it++;
    cout << *it << endl;
  }
  system("pause");
  return 0;
}

7.7 范围查找容器元素

Find_first_of 算法函数，用于查找第一个出现于另一个序列中的指定元素。find_first_of的用法如下：

template<class InputIterator, class ForwardIterator>
InputIterator find_first_of(InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2);

其中，first1、last1是迭代器，表示待查找的序列的范围；first2、last2是迭代器，表示要查找的元素序列的范围。调用find_first_of函数后，将会在[first1, last1]区间中查找第一个与[first2, last2]中任意一个元素相等的元素，并将找到的元素的迭代器作为函数返回值返回。如果未找到满足条件的元素，则函数将返回last1。

该算法可用于查找位于某个范围之内的元素，如下则是一段演示案例；

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

using namespace std;

int main(int argc, char* argv[])
{
  char * str1 = "hello";
  char * str2 = "lyshark This is a test case. Thank you for using it lyshark.";

  char * result = find_first_of(str1, str1 + strlen(str1), str2, str2 + strlen(str2));

  // 字符串str1的第一个字符,第一次出现在str2中的字符为.
  cout << *result << endl;
  system("pause");
  return 0;
}

7.8 普通元素计数统计

Count 算法函数，用于统计序列中指定值的元素个数。count函数的用法如下：

template<class InputIterator, class T>
typename iterator_traits<InputIterator>::difference_type count(InputIterator first, InputIterator last, const T& value);

其中，first、last是迭代器，表示待计数的序列的范围；value是需要计数的元素的值。调用count函数后，将会在[first, last]区间中统计等于value的元素个数，并将结果作为函数返回值返回。

该算法用于计算容器中某个给定值得出现次数，如下则是一段演示案例；

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

using namespace std;

int main(int argc, char* argv[])
{
  list<int> ls;
  
  // 批量插入测试数据
  for (int x = 0; x < 100; x++)
  {
    ls.push_back(x % 20);
  }

  // 统计元素value出现次数,将次数放入num中.
  int num = 0; int value = 9;
  num = count(ls.begin(), ls.end(), value);
  cout << "这个值出现过(次): " << num << endl;

  system("pause");
  return 0;
}

7.9 条件元素计数统计

Count_if 算法函数，用于统计满足给定条件的元素个数。count_if函数的用法如下：

template<class InputIterator, class UnaryPredicate>
typename iterator_traits<InputIterator>::difference_type count_if(InputIterator first, InputIterator last, UnaryPredicate pred);

其中，first、last是迭代器，表示待计数的序列的范围；pred是一个一元谓词函数，用于指定计数条件。调用count_if函数后，将会在[first, last]区间中统计满足谓词pred的元素个数，并将结果作为函数返回值返回。

该算法与Count算法非常类似，区别在于Count_if可以在统计前增加判断条件，如下则是一段演示案例；

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

using namespace std;

struct Student{
  struct Info{
    char *name; // 学生姓名
    int year;   // 学生年龄
  };
  int id;    // 学号
  Info stu;  // 学生Info数据

  Student(int _id, char *_name, int _year)
  {
    id = _id;
    stu.name = _name;
    stu.year = _year;
  }
};

// 获取学生年龄大于20岁并且小于30岁的人
bool GetRange(pair<int, Student::Info> s)
{
  if (s.second.year > 20 && s.second.year < 30)
    return 1;
  return 0;
}

int main(int argc, char* argv[])
{
  // 初始化学生数据
  Student stu1 = Student(1, "admin", 10);
  Student stu2 = Student(2, "guest", 21);
  Student stu3 = Student(3, "lyshark", 35);

  // 映射Map结构数据,并将上方的数据插入到Map中
  map<int, Student::Info> mp;
  pair<int, Student::Info> pairSt1(stu1.id, stu1.stu);
  mp.insert(pairSt1);
  pair<int, Student::Info> pairSt2(stu2.id, stu2.stu);
  mp.insert(pairSt2);
  pair<int, Student::Info> pairSt3(stu3.id, stu3.stu);
  mp.insert(pairSt3);

  // 条件统计,统计出年龄大于20岁并且小于30岁的人有多少个= num
  int num = 0;
  num = count_if(mp.begin(), mp.end(), GetRange);
  cout << num << endl;
  system("pause");
  return 0;
}

7.10 数组查找算法

Binary_search 算法函数，用于在有序序列中查找某个元素。binary_search的用法如下：

template<class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value);

其中，first、last是前向迭代器，表示待查找的有序序列的范围；value是需要查找的元素的值。调用binary_search函数后，将会在[first, last]区间中使用二分查找算法查找value。如果value存在于区间[first, last]中，则函数返回true；否则函数返回false。

该算法就是折半查找法，查找的元素集合必须是一个有序的序列，如下则是一段演示案例；

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

using namespace std;

int main(int argc, char* argv[])
{
  vector<int> var{ 1, 2, 3, 4, 5, 6, 6, 7, 8, 9, 10 };

  bool ret = binary_search(var.begin(), var.end(), 4);
  if (ret)
    cout << "found ok" << endl;
  else
    cout << "not found" << endl;

  system("pause");
  return 0;
}

7.11 元素不匹配查找

Mismatch 算法函数，用于查找两个序列中第一个不匹配的元素。mismatch函数的用法如下：

template<class InputIterator1, class InputIterator2>
pair<InputIterator1,InputIterator2> mismatch (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);

其中，first1、last1是迭代器，表示第一个序列的范围；first2是迭代器，表示第二个序列的起始位置。调用mismatch函数后，将会在[first1, last1]区间和以first2为起始位置的序列进行元素值的逐一比较，若两个序列中对应元素值都相等，则继续比较下一个元素。一旦出现对应元素不相等时，函数返回一个pair对，pair对的第一个元素是距离[first1, last1]开头最近不匹配的元素的迭代器，pair对的第二个元素是距离first2开头最近不匹配的元素的迭代器。

该算法函数比较两个序列，并从中找出首个不匹配元素的位置，如下则是一段演示案例；

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

using namespace std;

bool StrEqual(const char* x, const char* y)
{
  return strcmp(x, y) == 0 ? 1 : 0;
}

int main(int argc, char* argv[])
{
  vector<int> var1{ 2, 0, 0, 6 };
  vector<int> var2{ 2, 0, 0, 7 };

  // 检测var1与var2中不匹配元素数,并输出
  pair<vector<int>::iterator, vector<int>::iterator> result;
  result = mismatch(var1.begin(), var1.end(), var2.begin());
  if (result.first == var1.end() && result.second == var1.end())
    cout << "var1 与var2完全一致" << endl;
  else
    // var1 和var2不相同,不匹配的数是
    cout << "var1 = " << *result.first << " --> var2= " << *result.second << endl;

  // ---------------------------------------------------------------------------------
  // 针对字符串的不匹配检测
  char * str1[] = { "apple", "pear", "banana", "grape" };
  char * str2[] = { "apple", "pear", "banana", "zoops" };

  pair<char **, char **> result2 = mismatch(str1, str1 + 4, str2, StrEqual);
  if (result2.first != str1 + 4 && result2.second != str2 + 4)
  {
    // 成立则说明两个str子串有不同的地方,并输出他们之间的不同点
    cout << "str1 = > " << str1[result2.first - str1] << endl << endl;
    cout << "str2 = > " << str2[result2.second - str2] << endl;
  }
  system("pause");
  return 0;
}

7.12 元素相等的判断

Equal 算法函数，用于判断两个序列是否在元素值上相等。equal函数的用法如下：

template<class InputIterator1, class InputIterator2>
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);

其中，first1、last1是迭代器，表示第一个序列的范围；first2是迭代器，表示第二个序列的起始位置。调用equal函数后，将会在[first1, last1]区间和以first2为起始位置的序列进行元素值的逐一比较，若两个序列中对应元素的值都相等，则函数返回true，否则函数返回false。

该算法实现逐一比较两个序列的元素是否相等，该函数不返回迭代器，如下则是一段演示案例；

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

using namespace std;

bool absEqual(const int x,const int y)
{
  return (x == abs(y) || abs(x) == y) ? 1 : 0;
}

int main(int argc, char* argv[])
{
  vector<int> var1;
  vector<int> var2;

  // 初始化向量
  for (unsigned int x = 0; x < var1.size(); x++)
  {
    var1[x] = x;
    var2[x] = -1 * x;
  }

  // 判断v1和v2元素的绝对值是否完全相等
  if (equal(var1.begin(), var1.end(), var2.begin(), absEqual))
  {
    cout << "完全相等" << endl;
  }
  system("pause");
  return 0;
}

7.13 子序列搜索算法

Search 算法函数，用于在一个序列中查找另一个子序列。search函数的用法如下：

template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);

其中，first1、last1是迭代器，表示待查找的序列的范围；first2、last2是迭代器，表示要查找的子序列的范围。调用search函数后，将会在[first1, last1]区间中查找第一个与[first2, last2]相匹配的子序列，并返回距离区间开始点最近的元素的迭代器，如果没有找到匹配的子序列，将返回last1。

该算法实现了在一个序列中搜索与另一个序列匹配的子序列，如下则是一段演示案例；

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

using namespace std;

int main(int argc, char* argv[])
{
  vector<int> var1 = { 5, 6, 7, 8, 9 };
  vector<int> var2 = { 7, 8 };

  // 检查var2是否构成var1的子序列
  vector<int>::iterator it;
  it = search(var1.begin(), var1.end(), var2.begin(),var2.end());
  if (it != var1.end())
  {

    // 输出var2元素包含在var1中,的起始元素为
    cout << "Offset = " << it - var1.begin() << endl;
  }

  system("pause");
  return 0;
}

7.14 重复元素子序列搜索

Search_n 算法函数，用于在一个序列中查找连续n个符合条件的元素。search_n函数的用法如下：

template<class ForwardIterator, class Size, class T, class BinaryPredicate>
ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value, BinaryPredicate pred);

其中，first、last是迭代器，表示待查找的序列的范围；count表示需要匹配的元素个数；value表示需要匹配的元素值；pred为一个谓词函数，用于指定匹配方式。调用search_n函数后，将会在[first, last]区间中查找是否有count个连续的value元素，并返回指向第一个符合条件的元素位置的迭代器。如果没有找到符合条件的元素，将返回last。

该算法搜索序列中是否有一系列元素值均为某个给定值得子序列，如下则是一段演示案例；

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

using namespace std;

int main(int argc, char* argv[])
{
  vector<int> var1 = { 5, 6, 7, 8,8,8,9 };

  // 查找var1中存在三个连续是8的数据
  vector<int>::iterator it;
  it = search_n(var1.begin(), var1.end(), 3, 8);
  if (it != var1.end())
  {
    cout << "var1中存在三连8" << endl;
  }

  system("pause");
  return 0;
}

7.15 最后一个子序列搜索

Find_end 算法函数，用于在一个序列中查找另一个序列中的最后一次出现位置。find_end函数的用法如下：

template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);

其中，first1、last1是迭代器，表示待查找的序列的范围；first2、last2是迭代器，表示要查找的子序列的范围。调用find_end函数后，将会在[first1, last1]区间中查找最后一个与[first2, last2]相匹配的子序列，并返回距离区间结束点的最后一个元素的迭代器，如果没有找到匹配的子序列，将返回last1。

简单来讲，该算法实现了在一个序列中搜索出最后一个与另一个序列匹配的子序列，如下是一段应用案例。

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

using namespace std;

int main(int argc, char* argv[])
{
  vector<int> var1 = { -5,1,2,-6,-8,1,2,-11 };
  vector<int> var2 = { 1, 2 };

  // var1中查找最后一个子序列var2
  vector<int>::iterator it;

  it = find_end(var1.begin(), var1.end(), var2.begin(), var2.end());

  // 打印子序列在var1的起始位置,输出起offset
  if (it != var1.end())
    cout << "offset = [" << it - var1.begin() << "]" << endl;

  system("pause");
  return 0;
}