Stl算法

发表于 2022/06/04

作者 klizzz

20 分钟阅读

Stl算法

[TOC]

1. STL函数介绍

C++标准库中的泛型算法可以操作多种容器类型，包括标准库类型和内置数组。

这些 STL 算法主要定义在 <algorithm> 中，有些还会在 <numeric> 、 <functional> 等头文件中。

2. 常见函数简介

STL常见算法：¹

排序算法，如 sort, reverse, nth_element。
查找与统计算法，如 find, binary_search, count。
可变序列算法，如 copy, replace, fill, unique, remove。
排列算法，如 next_permutation, prev_permutation。
前缀和与差分算法，如 partial_sum, adjacent_difference。
数学算法，如：pow（指数运算）

        
      
#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;
int main()
{
// 使用STL容器时将数组指针改为迭代器即可
int a[5] = { 1, 2, 3, 4, 5 };
int b[5] = { 0 };

// 排序算法：
sort(a, a + 5);               // 将区间[0, 5)内元素按字典序从小到大排序（默认）
sort(a, a + 5, greater<int>()); // 从大到小排序，第三个参数也可以通过lamda或仿函数自定义排序方法
reverse(a, a + 5);            // 将区间[0, 5)内元素翻转
nth_element(a, a + 3, a + 5); // 将区间[0, 5)中第a+3个数归位，即将第3大的元素放到正确的位置上，该元素前后的元素不一定有序

// 查找与统计算法：
find(a, a + 5, 3);          // 在区间[0, 5)内查找等于3的元素，返回迭代器，若不存在则返回end()
binary_search(a, a + 5, 2); // 二分查找区间[0, 5)内是否存在元素2，存在返回true否则返回false
count(a, a + 5, 3);         // 返回区间[0, 5)内元素3的个数

// 可变序列算法：
copy(a, a + 2, a + 3);   // 将区间[0, 2)的元素复制到以a+3开始的区间，即[3, 5)
replace(a, a + 5, 3, 4); // 将区间[0, 5)内等于3的元素替换为4
fill(a, a + 5, 1);       // 将1写入区间[0, 5)中(初始化数组函数)
unique(a, a + 5);        // 将相邻元素间的重复元素全部移动至末端，返回去重之后数组最后一个元素之后的地址
remove(a, a + 5, 3);     // 将区间[0, 5)中的元素3移至末端，返回新数组最后一个元素之后的地址

// 排列算法：
next_permutation(a, a + 5); // 产生下一个排列{ 1, 2, 3, 5, 4 }
prev_permutation(a, a + 5); // 产生上一个排列{ 1, 2, 3, 4, 5 }

// 前缀和算法：
partial_sum(a, a + 5, b); // 计算数组a在区间[0,5)内的前缀和并将结果保存至数组b中，b = { 1, 3, 6, 10, 15 }

// 差分算法：
adjacent_difference(a, a + 5, b);// 计算数组a区间[0,5)内的差分并将结果保存至数组b中，b = { 1, 1, 1, 1, 1 }
adjacent_difference(a, a + 5, b, plus<int>()); // 计算相邻两元素的和，b = { 1, 3, 5, 7, 9 }
adjacent_difference(a, a + 5, b, multiplies<int>()); // 计算相邻两元素的乘积，b = { 1, 2, 6, 12, 20 }

return 0;

}

std::remove

std::remove的签名：² ³

        
template< class ForwardIt, class T >
constexpr ForwardIt remove( ForwardIt first, ForwardIt last, const T& value );

first和last为两个迭代器，表示待移除元素的范围。
value为要移除的容器中的值。
函数最后返回一个迭代器，指向被移除元素的开始位置。

std::remove并不会改变容器的大小，而是将符合条件的元素移到容器的末尾，也不会直接删除元素。

使用 erase–remove 惯用法，可以删除从该位置到容器的末尾的元素：

        
      
std::vector<int> vec = {1, 2, 3, 4, 5};
// 删掉vec中的元素“3”：
std::vector<T>::iterator it = std::remove(vec.begin(), vec.end(), 3);
vec.erase(it, vec.end());
// 也可以将上面的两个函数结合在一起写：
numbers.erase(std::remove(vec.begin(), vec.end(), 3), vec.end());

std::remove_if

std::remove_if 的函数签名：²

        
template< class ForwardIt, class UnaryPredicate >
ForwardIt remove_if( ForwardIt first, ForwardIt last, UnaryPredicate p );

first和last为两个迭代器，表示待移除元素的范围。
p是一个谓词函数⁴ ，该谓词函数需要返回一个bool值，用于判断元素是否符合特定条件。
函数最后返回一个迭代器，指向被移除元素的开始位置。

remove_if算法并不会改变容器的大小，也不会直接删除元素，而是将符合条件的元素移到容器的末尾。因此，常常需要结合erase函数来删除这些被移到末尾的元素：²

        
      
std::vector<int> numbers = {1, 2, 3, 4, 5};
// 移除numbers中的偶数：
numbers.erase(std::remove_if(numbers.begin(), 
                             numbers.end(), 
                             [](int num)->bool{ return num % 2 == 0; }), 
              numbers.end());

std::erase

C++20后，有了std::erase函数，用来代替 erase–remove 惯用法，它的函数签名如下：³

        
      
#include <vector>
template< class T, class Alloc, class U >
constexpr typename std::vector<T, Alloc>::size_type
    erase( std::vector<T, Alloc>& c, const U& value );

实现起来非常简单：

        
      
std::vector<int> nums = {1, 2, 3, 4, 5};
// 移除nums中为2的元素：
std::erase(nums, 2);

std::erase_if

在 C++20 标准中，引入了一个名为 std::erase_if 的函数，用于从容器中移除满足指定条件的元素。

std::erase_if 的定义类似于：²

        
template< class Container, class UnaryPredicate >
Container& erase_if( Container& c, UnaryPredicate p );

它接受一个容器和一个一元谓词⁵，并返回一个引用指向被修改后的容器。

以下是 std::erase_if 的使用示例：

        
      
// 全局函数作为“一元谓词”，也可以是lamda函数
bool is_even(int num) {
    return num % 2 == 0;
}

void main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
	// 从 numbers 中移除偶数：
    std::erase_if(numbers, is_even);
}

std::format

std::format 是 C++20 引入的一个新特性，它提供了一种更现代、更安全的方式来格式化字符串。这个函数类似于 Python 中的 str.format() 方法或者 C语言中的 printf，但它更安全，因为它避免了许多 printf 风格的格式化函数中常见的类型不匹配和缓冲区溢出问题。⁶

下面是一些使用 std::format 的例子：²

        
      
#include <format>
#include <iostream>
#include <string>

int main() {
    // 基本用法
    std::string s = std::format("Hello, {}!", "World");
    std::cout << s << std::endl; // 输出: Hello, World!

    // 使用位置参数
    s = std::format("{1} is prior to {0}", "Second", "First");
    std::cout << s << std::endl; // 输出: First is prior to Second

    // 格式化数字
    s = std::format("The number is: {0:.2f}", 3.14159);
    std::cout << s << std::endl; // 输出: The number is: 3.14

    // 定义宽度和填充
    s = std::format("{:*>10}", "right");
    std::cout << s << std::endl; // 输出: *****right

    // 组合使用
    int year = 2020, month = 5, day = 20;
    s = std::format("The date is: {0}-{1:02}-{2:02}", year, month, day);
    std::cout << s << std::endl;  // 输出: The date is: 2020-05-20

    return 0;
}

在上面的例子中，我们可以看到：

{} 用于标识需要插入参数的位置。
{1} 和 {0} 这样的数字表示参数的位置索引。
:.2f 用于指定浮点数的格式，其中 .2 表示显示两位小数，f 表示固定点表示法。
:*>10 表示用 * 填充，直到字符串宽度为 10，> 表示右对齐。
{1:02} 表示取第二个参数，且参数格式化为至少两位数，如果数值小于两位数，则在前面填充0。

std::find 和 std::find_if

std::find 是C++标准库中的一个模板函数，定义在头文件 <algorithm> 中。它用于在给定范围内查找等于特定值的第一个元素。如果找到这样的元素，它会返回一个迭代器指向该元素；如果没有找到，则返回指向范围末尾的迭代器。²

std::find 可以用于任何类型的容器，如数组、链表、向量等，只要容器的元素类型支持相等比较即可。

std::find是基于线性查找实现，因此其性能为 O(n)，其中 n 是序列中元素的数量。如果你的容器已经排序，可以使用更高效的 std::binary_search、std::lower_bound 或 std::upper_bound 来进行查找。

(1) 函数原型

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

其中 first 和 last 分别是定义查找范围的起始和结束迭代器，val 是要查找的值。

(2) find 使用实例

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

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    int val = 3;
	// 查找元素val：
    auto it = std::find(vec.begin(), vec.end(), val);

    if (it != vec.end()) 
    {// 查找到了，输出位置：
        std::cout << "Value " << val << " found at position:" << std::endl;
        std::cout << std::distance(vec.begin(), it) << std::endl;
    } 
    else 
    {// 没找到：
        std::cout << "Value " << val << " not found" << std::endl;
    }

    return 0;
}

(2) find_if 使用实例

        
      
int main() {
    std::vector<int> vec{1,3,5,7,9,9,9};
    // 查找是否有9的元素
    auto result = std::find_if(vec.begin(),vec.end(),[](const int val){
        return val == 9;
    });
    return 0;
}

std::lower_bound

std::lower_bound 是 C++ 标准库中定义于 <algorithm> 头文件的一个算法，它用于在已排序的范围内查找第一个不小于（即大于或等于）给定值的元素。它返回指向找到的元素的迭代器；如果所有元素都小于给定的值，则返回指向范围末尾的迭代器。这个函数利用二分查找算法，因此要求范围已经按非降序排序。²

std::lower_bound 函数的原型如下：

        
template <class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& val);

参数 first 和 last 是定义查找范围的迭代器，val 是要查找的值。

使用示例：

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

int main() {
    std::vector<int> vec = {1, 2, 4, 4, 5, 6, 7};
    int val = 4;

    auto it = std::lower_bound(vec.begin(), vec.end(), val);

    if (it != vec.end()) {
        std::cout << "The first element not less than " << val << " is at position: " << std::distance(vec.begin(), it) << std::endl;
    } else {
        std::cout << "No element not less than " << val << " found in the vector." << std::endl;
    }

    return 0;
}

在这个例子中，向量 vec 被假定为已排序。std::lower_bound 用于查找第一个不小于 4 的元素。由于序列中有两个 4，它将返回第一个 4 的迭代器。

由于 std::lower_bound 使用二分查找，它的时间复杂度是对数 O(log n)，其中 n 是序列中元素的数量。这使得它比线性时间的查找算法（如 std::find）在大序列上更高效。但是，请记住，std::lower_bound 要求序列在执行查找之前已经按照非降序排序。

std::for_each

std::begin 和 std::end

std::merge

在 C++ 标准库中，std::merge 是一个函数模板，用于合并两个已排序的序列，并保持元素的排序顺序。结果被存储在另一个序列中。std::merge 可用于数组、std::vector、std::list 和其他容器，只要这些容器中的元素是已经排序的。²

std::merge 的典型用法如下：

        
      
#include <algorithm>
#include <vector>
#include <iterator>

// ...

std::vector<int> v1 = {1, 3, 5, 7};
std::vector<int> v2 = {2, 4, 6, 8};
std::vector<int> v_merged(v1.size() + v2.size());

std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v_merged.begin());

在上述代码中，v1 和 v2 是两个已经排序的整数向量，v_merged 是另一个向量，其大小等于 v1 和 v2 大小之和。调用 std::merge 后，v_merged 包含合并后的、排序的元素序列。

std::merge 函数模板的声明如下：

        
      
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
                     InputIterator2 first2, InputIterator2 last2,
                     OutputIterator result);

这里 InputIterator1 和 InputIterator2 类型的参数 first1, last1, first2, 和 last2 分别定义了两个输入序列的开始和结束。OutputIterator 类型的参数 result 定义了存储结果的序列的起始位置。

std::merge 也有一个版本接受额外的比较函数对象，允许用户指定不同于默认的 < 操作符的排序准则：

        
      
template <class InputIterator1, class InputIterator2,
          class OutputIterator, class Compare>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
                     InputIterator2 first2, InputIterator2 last2,
                     OutputIterator result, Compare comp);

这个版本允许用户自定义比较逻辑，例如，按照降序合并两个列表：

        
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(),
           v_merged.begin(), std::greater<int>());

std::merge 不会改变原来的两个序列，而是将合并结果存放在第三个序列中。务必确保目标序列有足够的空间来存放两个输入序列中的所有元素，否则会导致未定义行为。

std::accumulate

C++11标准支持std::accumulate函数，它是定义于<numeric>头文件中的算法。std::accumulate可以用于任何标准容器，如std::vector、std::deque、std::list等，只要它们提供了有效的迭代器。

以下是一个使用 C++11 标准特性的例子，演示如何计算一个std::vector的元素和：

        
      
#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    // C++11 中可以使用 auto 关键字自动推导变量类型
    auto sum = std::accumulate(numbers.begin(), numbers.end(), 0);

    std::cout << "The sum is: " << sum << std::endl;

    return 0;
}

在这个例子中，auto关键字允许编译器自动推断sum的类型，它将基于std::accumulate函数调用的结果类型来确定。这样可以使代码更简洁，并且减少因类型错误而导致的编译问题。

参考文章⁷⁸⁹¹⁰¹¹

STL常用算法 ↩︎
来源：ChatGPT-4 ↩︎ ↩︎² ↩︎³ ↩︎⁴ ↩︎⁵ ↩︎⁶ ↩︎⁷ ↩︎⁸
C++20告别迷惑的std::remove ↩︎ ↩︎²
谓词函数（Predicate Function）是一个用于判断某个条件是否成立的函数。在C++中，谓词函数通常作为参数传递给算法函数（例如 remove_if、find_if 等），用于对元素进行条件判断。谓词函数可以是函数指针、函数对象（Functor）或者 Lambda 表达式，它们都必须满足特定的签名（函数参数和返回值类型）。 ↩︎
一元谓词：接受一个参数的函数或函数对象，其返回类型为 bool。一元谓词通常用于对容器元素进行条件判断或筛选。 ↩︎
C++20 format ↩︎
std::bind学习笔记 ↩︎
第二十节 C++数组常用函数 ↩︎
C++ STL由哪部分组成？ ↩︎
C++STL之常见算法 ↩︎
C++ STL 算法：掌握这些，你的代码效率提升 10 倍！ ↩︎

技术, 代码基础知识

技术代码基础知识 C++

本文由作者按照 CC BY 4.0 进行授权