算法库：C++魔术师STL算法用法示例

2021年3月12日13:07:53 发表评论 945 次浏览

本文概述

对于所有渴望在竞争性编程中表现出色的人来说, 只有不了解STL容器的知识才有用, 直到人们不知道所有STL所提供的内容。

STL有大量的算法, 可用于所有<algorithm>库函数：请参见

这里

.

以下是一些关于向量的最常用算法和《竞争性编程》中最有用的算法：

非操纵算法

  1. 分类(first_iterator, last_iterator)–对给定向量进行排序。
  2. 反向(first_iterator, last_iterator)–反转向量。
  3. * max_element(first_iterator, last_iterator)–查找向量的最大元素。
  4. * min_element(first_iterator, last_iterator)–查找向量的最小元素。
  5. 累积(first_iterator, last_iterator, 总和的初始值)–是否对向量元素求和

CPP

// 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;
}

输出如下

Vector is: 10 20 5 23 42 15 
Vector after sorting is: 5 10 15 20 23 42 
Vector after reversing is: 42 23 20 15 10 5 
Maximum element of vector is: 42
Minimum element of vector is: 5
The summation of vector elements is: 115

6.count(first_iterator, last_iterator, x)–计算向量中x的出现。

7.查找(first_iterator, last_iterator, x)

–如果向量中不存在元素, 则指向向量的最后一个地址((name_of_vector).end())。

CPP

// 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;
}

输出如下

Occurrences of 20 in vector : 2
Element found

8.binary_search(first_iterator, last_iterator, x)–测试x是否存在于排序的向量中。

9. lower_bound(first_iterator, last_iterator, x)–返回一个迭代器, 该迭代器指向[first, last)范围内第一个元素, 该元素的值不小于" x"。

10. upper_bound(first_iterator, last_iterator, x)–返回一个迭代器, 该迭代器指向[first, last)范围内第一个元素, 该元素的值大于" x"。

C ++

// 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;
}

输出如下

The lower bound is at position: 3
The upper bound is at position: 5

一些操纵算法

  1. arr.erase(要删除的位置)–这将擦除矢量中的选定元素, 并相应地移动和调整矢量元素的大小。
  2. arr.erase(唯一(arr.begin(), arr.end()), arr.end())–这会擦除单行中排序向量中的重复出现。

CPP

// 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;
}

输出如下

Vector is :5 10 15 20 20 23 
Vector after erasing the element: 5 15 20 20 23 
Vector before removing duplicate  occurrences: 5 15 20 20 23 
Vector after deleting duplicates: 5 15 20 23 42 45

3. next_permutation(first_iterator, last_iterator)–这将向量修改为其下一个排列。

4. prev_permutation(first_iterator, last_iterator)–这将向量修改为其先前的排列。

CPP

// 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;
}

输出如下

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

5.距离(first_iterator, 期望位置)–它返回到第一个迭代器的期望位置的距离。此功能在查找索引时非常有用。

CPP

// 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;
}

输出如下

Distance between first to max element: 7

更多 -

STL文章

本文作者：

Manjeet Singh。

如果你喜欢lsbin并希望做出贡献, 那么你也可以写一篇文章并将你的文章邮寄到contribution@lsbin.org。查看你的文章出现在lsbin主页上, 并帮助其他Geeks。

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: