C++ STL 中的非變易演算法（Non-modifying Algorithms）是指那些不會修改容器內容的演算法，是C++提供的一組模板函數，該系列函數不會修改原序列中的數據，而是對數據進行處理、查找、計算等操作，並通過迭代器實現了對序列元素的遍歷與訪問。由於迭代器與演算法是解耦的，因此非變易演算法可以... ...
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);
其中，first、last是迭代器，表示待查找的序列的範圍；value是需要查找的元素的值。調用find函數後，將會在[first, last]區間中查找第一個等於value的元素，並將該元素的迭代器作為函數返回值返回。如果未找到等於value的元素，則函數將返回last。
該演算法不僅可以查詢普通數據結構，還可以查詢結構與類中數據，如下則是一段演示案例；
#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);
其中，first、last是迭代器，表示待查找的序列的範圍；pred是一個一元謂詞函數，用於指定查找條件。調用find_if函數後，將會在[first, last]區間中查找第一個謂詞pred返回true的元素，並將該元素的迭代器作為函數返回值返回。如果未找到滿足條件的元素，則函數將返回last。
如下一個案例中，實現了查詢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;
}
本文作者： 王瑞
本文鏈接： https://www.lyshark.com/post/4d3e4328.html
版權聲明： 本博客所有文章除特別聲明外，均採用 BY-NC-SA 許可協議。轉載請註明出處！
