c++ stl(1)--algorithms直白总结!精彩不容错过! (2024)

翻译+改编自:

https://www.geeksforgeeks.org/the-c-standard-template-library-stl/https://www.geeksforgeeks.org/stdpartition-in-c-stl/
https://www.geeksforgeeks.org/c-magicians-stl-algorithms/

引言

标准模板库（STL）是一组C ++模板类，用于提供常见的编程数据结构和功能，例如列表，堆栈，数组等。它是容器类，算法和迭代器的库。它是一个通用库，因此其组件已参数化。模板类的知识是使用STL的先决条件。

大纲

STL具有四个组成部分

algorithms
容器
Functions
迭代器

algorithms

The header algorithm定义了一组专门设计用于元素范围的函数集合，它们作用于容器并为容器的内容提供各种操作手段。

算法

排序
搜寻
重要的STL算法
有用的array算法
分区操作

Numeric

valarray类

容器

容器或容器类存储对象和数据。总共有七个标准的“first-class”容器类和三个容器适配器类，并且只有七个头文件可提供对这些容器或容器适配器的访问。

序列容器：实现可以按顺序访问的数据结构。

向量vector
list
双端队列deque
数组arrays
forward_list（在C ++ 11中引入）

容器适配器：为顺序容器提供不同的接口。

队列queue
priority_queue
堆

关联容器：实现可以快速搜索的排序数据结构（O（log n）复杂度）。

set
multiset
map
multimap

无序关联容器：实现可以快速搜索的无序数据结构

unordered_set（在C ++ 11中引入）
unordered_multiset（在C ++ 11中引入）
unordered_map（在C ++ 11中引入）
unordered_multimap（在C ++ 11中引入）

Functions

STL包含使函数调用运算符重载的类。这种类的实例称为函数对象。函数对象允许在要传递的参数的帮助下自定义关联功能的工作。

Functors

迭代器

顾名思义，迭代器用于处理一系列值。它们是允许在STL中通用的主要功能。

迭代器

实用程序库

定义在<utility header>下

pair

正文

一.Algorithms

1.sort

#include <iostream> #include <algorithm> using namespace std; void show(int a[]) { for(int i = 0; i < 10; ++i) cout << a[i] << " "; } int main() { int a[10]= {1, 5, 8, 9, 6, 7, 3, 4, 2, 0}; cout << "\n The array before sorting is : "; show(a); sort(a, a+10); cout << "\n\n The array after sorting is : "; show(a); return 0; } The outut of the above program is :The array before sorting is : 1 5 8 9 6 7 3 4 2 0The array after sorting is : 0 1 2 3 4 5 6 7 8 9

2.search:

binary_search（开始地址，结束地址，值查找）

二进制搜索是一种广泛使用的搜索算法，该算法要求在应用搜索之前对数组进行排序。该算法背后的主要思想是将数组一分为二（分而治之），直到找到元素或所有元素用尽。

它通过将数组的中间项与目标进行比较来工作，如果匹配，则返回true；否则，如果中间项大于目标，则在左侧子数组中执行搜索。
如果中间项小于目标，则在右边的子数组中执行搜索。

#include <algorithm> #include <iostream> using namespace std; void show(int a[], int arraysize) { for (int i = 0; i < arraysize; ++i) cout << a[i] << " "; } int main() { int a[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 }; int asize = sizeof(a) / sizeof(a[0]); cout << "\n The array is : "; show(a, asize); cout << "\n\nLet's say we want to search for 2 in the array"; cout << "\n So, we first sort the array"; sort(a, a + asize); cout << "\n\n The array after sorting is : "; show(a, asize); cout << "\n\nNow, we do the binary search"; if (binary_search(a, a + 10, 2)) cout << "\nElement found in the array"; else cout << "\nElement not found in the array"; cout << "\n\nNow, say we want to search for 10"; if (binary_search(a, a + 10, 10)) cout << "\nElement found in the array"; else cout << "\nElement not found in the array"; return 0; }

The output of the above program is :

The array is : 1 5 8 9 0 6 7 3 4 2 0Let's say we want to search for 2 in the array So, we first sort the arrayThe array after sorting is : 0 1 2 3 4 5 6 7 8 9Now, we do the binary searchElement found in the arrayNow, say we want to search for 10Element not found in the array

3.算法库| C ++ MagiciansSTL算法

Non-Manipulating Algorithms

sort（first_iterator，last_iterator） –对给定向量进行排序。
reverse（first_iterator，last_iterator） –反转向量。
* max_element（first_iterator，last_iterator） –查找向量的最大元素。
* min_element（first_iterator，last_iterator） –查找向量的最小元素。
accumulate（first_iterator，last_iterator，求和的初始值） –对向量元素求和

// A C++ program to demonstrate working of sort(), // reverse() #include <algorithm> #include <iostream> #include <vector> #include <numeric> //For accumulate operation using namespace std; int main() { // Initializing vector with array values int arr[] = {10, 20, 5, 23 ,42 , 15}; int n = sizeof(arr)/sizeof(arr[0]); vector<int> vect(arr, arr+n); cout << "Vector is: "; for (int i=0; i<n; i++) cout << vect[i] << " "; // Sorting the Vector in Ascending order sort(vect.begin(), vect.end()); cout << "\nVector after sorting is: "; for (int i=0; i<n; i++) cout << vect[i] << " "; // Reversing the Vector reverse(vect.begin(), vect.end()); cout << "\nVector after reversing is: "; for (int i=0; i<6; i++) cout << vect[i] << " "; cout << "\nMaximum element of vector is: "; cout << *max_element(vect.begin(), vect.end()); cout << "\nMinimum element of vector is: "; cout << *min_element(vect.begin(), vect.end()); // Starting the summation from 0 cout << "\nThe summation of vector elements is: "; cout << accumulate(vect.begin(), vect.end(), 0); return 0; } Output:Vector before sorting is: 10 20 5 23 42 15 Vector after sorting is: 5 10 15 20 23 42 Vector before reversing is: 5 10 15 20 23 42 Vector after reversing is: 42 23 20 15 10 5 Maximum element of vector is: 42Minimum element of vector is: 5The summation of vector elements is: 115

count（first_iterator，last_iterator，x） –计算向量中x的出现。
find（first_iterator，last_iterator，x） –如果向量中不存在元素，则指向向量（（name_of_vector）.end（））的最后地址。

// C++ program to demonstrate working of count() // and find() #include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { // Initializing vector with array values int arr[] = {10, 20, 5, 23 ,42, 20, 15}; int n = sizeof(arr)/sizeof(arr[0]); vector<int> vect(arr, arr+n); cout << "Occurrences of 20 in vector : "; // Counts the occurrences of 20 from 1st to // last element cout << count(vect.begin(), vect.end(), 20); // find() returns iterator to last address if // element not present find(vect.begin(), vect.end(),5) != vect.end()? cout << "\nElement found": cout << "\nElement not found"; return 0; }Output:Occurrences of 20 in vector: 2Element found

binary_search（first_iterator，last_iterator，x） –测试x是否存在于排序的向量中。
lower_bound（first_iterator，last_iterator，x） –返回一个迭代器，该迭代器指向[first，last）范围内第一个元素，该元素的值不小于'x'。
upper_bound（first_iterator，last_iterator，x） –返回一个迭代器，该迭代器指向[first，last）范围内第一个元素的值大于'x'。

// C++ program to demonstrate working of lower_bound() // and upper_bound(). #include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { // Initializing vector with array values int arr[] = {5, 10, 15, 20, 20, 23, 42, 45}; int n = sizeof(arr)/sizeof(arr[0]); vector<int> vect(arr, arr+n); // Sort the array to make sure that lower_bound() // and upper_bound() work. sort(vect.begin(), vect.end()); // Returns the first occurrence of 20 auto q = lower_bound(vect.begin(), vect.end(), 20); // Returns the last occurrence of 20 auto p = upper_bound(vect.begin(), vect.end(), 20); cout << "The lower bound is at position: "; cout << q-vect.begin() << endl; cout << "The upper bound is at position: "; cout << p-vect.begin() << endl; return 0; } Output:The lower bound is at position: 3The upper bound is at position: 5

一些Manipulating算法

arr.erase（要删除的位置） –删除矢量中的选定元素，并相应地移动和调整矢量元素的大小。
arr.erase（unique（arr.begin（），arr.end（）），arr.end（）） –删除单行中排序向量中的重复项。

// C++ program to demonstrate working of erase() #include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { // Initializing vector with array values int arr[] = {5, 10, 15, 20, 20, 23, 42, 45}; int n = sizeof(arr)/sizeof(arr[0]); vector<int> vect(arr, arr+n); cout << "Vector is :"; for (int i=0; i<6; i++) cout << vect[i]<<" "; // Delete second element of vector vect.erase(vect.begin()+1); cout << "\nVector after erasing the element: "; for (int i=0; i<5; i++) cout << vect[i] << " "; // sorting to enable use of unique() sort(vect.begin(), vect.end()); cout << "\nVector before removing duplicate "" occurrences: "; for (int i=0; i<5; i++) cout << vect[i] << " "; // Deletes the duplicate occurrences vect.erase(unique(vect.begin(),vect.end()),vect.end()); cout << "\nVector after deleting duplicates: "; for (int i=0; i< vect.size(); i++) cout << vect[i] << " "; return 0; }Output:Vector before erasing the element:5 20 5 23 20 20 Vector after erasing the element: 5 5 23 20 20 Vector before removing duplicate occurrences: 5 5 20 20 23 Vector after deleting duplicates: 5 20 23

next_permutation（first_iterator，last_iterator） –这将向量修改为其下一个排列。
prev_permutation（first_iterator，last_iterator） –将向量修改为其先前的排列。

// C++ program to demonstrate working of next_permutation() // and prev_permutation() #include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { // Initializing vector with array values int arr[] = {5, 10, 15, 20, 20, 23, 42, 45}; int n = sizeof(arr)/sizeof(arr[0]); vector<int> vect(arr, arr+n); cout << "Given Vector is:\n"; for (int i=0; i<n; i++) cout << vect[i] << " "; // modifies vector to its next permutation order next_permutation(vect.begin(), vect.end()); cout << "\nVector after performing next permutation:\n"; for (int i=0; i<n; i++) cout << vect[i] << " "; prev_permutation(vect.begin(), vect.end()); cout << "\nVector after performing prev permutation:\n"; for (int i=0; i<n; i++) cout << vect[i] << " "; return 0; } Output: Given Vector is:5 10 15 20 20 23 42 45 Vector after performing next permutation:5 10 15 20 20 23 45 42 Vector after performing prev permutation:5 10 15 20 20 23 42 45

distance（first_iterator，desired_position）–返回到第一个迭代器的期望位置的距离。此函数在查找索引时非常有用。

// C++ program to demonstrate working of distance() #include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { // Initializing vector with array values int arr[] = {5, 10, 15, 20, 20, 23, 42, 45}; int n = sizeof(arr)/sizeof(arr[0]); vector<int> vect(arr, arr+n); // Return distance of first to maximum element cout << "Distance between first to max element: "; cout << distance(vect.begin(), max_element(vect.begin(), vect.end())); return 0; } Output:Distance between first to max element: 7

4.C ++ STL中的数组array算法（all_of，any_of，none_of，copy_n和iota）

从C ++ 11开始，在C ++的STL中添加了一些有趣的新算法。这些算法在数组上运行，可用于节省编码期间的时间，因此也可用于竞争性编程。

all_of（）

5.C ++ STL中的std :: partition

C ++在其STL算法库中有一个类，该类允许我们使用某些内置函数轻松进行分区算法。分区是指根据给定条件划分容器元素的动作。

分区操作 ：

1.partition(beg, end, condition)： -该函数根据条件进行分区。

2. is_partitioned（beg，end，condition）：根据条件判断是否分区- 如果容器已分区，则此函数返回布尔值true，否则返回false。

// C++ code to demonstrate the working of // partition() and is_partitioned() #include<iostream> #include<algorithm> // for partition algorithm #include<vector> // for vector using namespace std; int main() { // Initializing vector vector<int> vect = { 2, 1, 5, 6, 8, 7 }; // Checking if vector is partitioned // using is_partitioned() is_partitioned(vect.begin(), vect.end(), [](int x) { return x%2==0; })? cout << "Vector is partitioned": cout << "Vector is not partitioned"; cout << endl; // partitioning vector using partition() partition(vect.begin(), vect.end(), [](int x) { return x%2==0; }); // Checking if vector is partitioned // using is_partitioned() is_partitioned(vect.begin(), vect.end(), [](int x) { return x%2==0; })? cout << "Now, vector is partitioned after partition operation": cout << "Vector is still not partitioned after partition operation"; cout << endl; // Displaying partitioned Vector cout << "The partitioned vector is : "; for (int &x : vect) cout << x << " "; return 0; } Output:Vector is not partitionedNow, vector is partitioned after partition operationThe partitioned vector is : 2 8 6 5 1 7

3. stable_partition(beg, end, condition):-根据条件进行分区,元素的相对顺序被保留。

4. partition_point（beg，end，condition）：此函数返回一个迭代器，该迭代器指向容器的分区点，即条件不成立的分区范围[beg，end）中的第一个元素。只有在容器已经分区时，此函数才能正常工作。

// C++ code to demonstrate the working of // stable_partition() and partition_point() #include<iostream> #include<algorithm> // for partition algorithm #include<vector> // for vector using namespace std; int main() { // Initializing vector vector<int> vect = { 2, 1, 5, 6, 8, 7 }; // partitioning vector using stable_partition() // in sorted order stable_partition(vect.begin(), vect.end(), [](int x) { return x%2 == 0; }); // Displaying partitioned Vector cout << "The partitioned vector is : "; for (int &x : vect) cout << x << " "; cout << endl; // Declaring iterator vector<int>::iterator it1; // using partition_point() to get ending position of partition auto it = partition_point(vect.begin(), vect.end(), [](int x) { return x%2==0; }); // Displaying partitioned Vector cout << "The vector elements returning true for condition are : "; for ( it1= vect.begin(); it1!=it; it1++) cout << *it1 << " "; cout << endl; return 0; } Output:The partitioned vector is : 2 6 8 1 5 7 The vector elements returning true for condition are : 2 6 8

5. partition_copy（beg，end，beg1，beg2，condition）：-此函数copies the partitioned elementsin the differenet containers mentioned in its arguments。它需要5个参数。原容器的开始和结束位置，新容器的开始位置1（elements returning true for condition），新容器的开始位置2（elements returning false for condition）和condition。调整新容器的大小是必需的。

// C++ code to demonstrate the working of // partition_copy() #include<iostream> #include<algorithm> // for partition algorithm #include<vector> // for vector using namespace std; int main() { // Initializing vector vector<int> vect = { 2, 1, 5, 6, 8, 7 }; // Declaring vector1 vector<int> vect1; // Declaring vector1 vector<int> vect2; // Resizing vectors to suitable size using count_if() and resize() int n = count_if (vect.begin(), vect.end(), [](int x) { return x%2==0; } ); vect1.resize(n); vect2.resize(vect.size()-n); // Using partition_copy() to copy partitions partition_copy(vect.begin(), vect.end(), vect1.begin(), vect2.begin(), [](int x) { return x%2==0; }); // Displaying partitioned Vector cout << "The elements that return true for condition are : "; for (int &x : vect1) cout << x << " "; cout << endl; // Displaying partitioned Vector cout << "The elements that return false for condition are : "; for (int &x : vect2) cout << x << " "; cout << endl; return 0; } Output:The elements that return true for condition are : 2 6 8 The elements that return false for condition are : 1 5 7

7.std :: C ++中的valarray类

C ++ 98引入了一个名为valarray的特殊容器，可以有效地保存并提供对数组的数学运算。

它支持按元素进行数学运算以及各种形式的广义下标运算符，切片和间接访问。
与向量相比，valarray在某些数学运算中比向量更有效。

valarray类中的公共成员函数：

1. apply（）：-该函数立即将其参数中给出的操作应用于所有 valarray元素，并返回带有操作值的新valarray。

2. sum（）：-此函数一次返回 valarrays所有元素的总和。

// C++ code to demonstrate the working of // apply() and sum() #include<iostream> #include<valarray> // for valarray functions using namespace std; int main() { // Initializing valarray valarray<int> varr = { 10, 2, 20, 1, 30 }; // Declaring new valarray valarray<int> varr1 ; // Using apply() to increment all elements by 5 varr1 = varr.apply([](int x){return x=x+5;}); // Displaying new elements value cout << "The new valarray with manipulated values is : "; for (int &x: varr1) cout << x << " "; cout << endl; // Displaying sum of both old and new valarray cout << "The sum of old valarray is : "; cout << varr.sum() << endl; cout << "The sum of new valarray is : "; cout << varr1.sum() << endl; return 0; } Output:The new valarray with manipulated values is : 15 7 25 6 35 The sum of old valarray is : 63The sum of new valarray is : 88

3. min（）：-此函数返回valarray 的最小元素。

4. max（）：-此函数返回valarray 的最大元素。

// C++ code to demonstrate the working of // max() and min() #include<iostream> #include<valarray> // for valarray functions using namespace std; int main() { // Initializing valarray valarray<int> varr = { 10, 2, 20, 1, 30 }; // Displaying largest element of valarray cout << "The largest element of valarray is : "; cout << varr.max() << endl; // Displaying smallest element of valarray cout << "The smallest element of valarray is : "; cout << varr.min() << endl; return 0; } Output:The largest element of valarray is : 30The smallest element of valarray is : 1

5.shift（） ：-该函数返回之后的新的valarray 切换元件通过的数目在其参数提及。如果数字为正，则应用左移；如果数字为负，则应用右移。

6.cshift（） ：-后该函数返回新的valarray 循环移位（旋转）元件通过的数目在其参数提及。如果数字为正， 则应用左圆周移位；如果数字为负，则应用右圆周移位。

// C++ code to demonstrate the working of // shift() and cshift() #include<iostream> #include<valarray> // for valarray functions using namespace std; int main() { // Initializing valarray valarray<int> varr = { 10, 2, 20, 1, 30 }; // Declaring new valarray valarray<int> varr1; // using shift() to shift elements to left // shifts valarray by 2 position varr1 = varr.shift(2); // Displaying elements of valarray after shifting cout << "The new valarray after shifting is : "; for ( int&x : varr1) cout << x << " "; cout << endl; // using cshift() to circulary shift elements to right // rotates valarray by 3 position varr1 = varr.cshift(-3); // Displaying elements of valarray after circular shifting cout << "The new valarray after circular shifting is : "; for ( int&x : varr1) cout << x << " "; cout << endl; return 0; } Output:The new valarray after shifting is : 20 1 30 0 0 The new valarray after circular shifting is : 20 1 30 10 2

7. swap（）：-此函数将一个valarray与另一个valarray交换。

// C++ code to demonstrate the working of // swap() #include<iostream> #include<valarray> // for valarray functions using namespace std; int main() { // Initializing 1st valarray valarray<int> varr1 = {1, 2, 3, 4}; // Initializing 2nd valarray valarray<int> varr2 = {2, 4, 6, 8}; // Displaying valarrays before swapping cout << "The contents of 1st valarray ""before swapping are : "; for (int &x : varr1) cout << x << " "; cout << endl; cout << "The contents of 2nd valarray ""before swapping are : "; for (int &x : varr2) cout << x << " "; cout << endl; // Use of swap() to swap the valarrays varr1.swap(varr2); // Displaying valarrays after swapping cout << "The contents of 1st valarray ""after swapping are : "; for (int &x : varr1) cout << x << " "; cout << endl; cout << "The contents of 2nd valarray ""after swapping are : "; for (int &x : varr2) cout << x << " "; cout << endl; return 0; } Output:The contents of 1st valarray before swapping are : 1 2 3 4 The contents of 2nd valarray before swapping are : 2 4 6 8 The contents of 1st valarray after swapping are : 2 4 6 8 The contents of 2nd valarray after swapping are : 1 2 3 4