C++(22): C++：STL中的部分计算接口（std::accumulate、std::partial_sum等）

1. 简述

        C++ STL库中的算法组件提供了大量用于操作序列的算法函数。这些函数通常以迭代器范围为操作对象，可以非常方便地对容器中的元素进行各种操作，而不需要写循环。下面我会详细介绍几个常用的算法函数，特别是accumulate，并提供相应的例程。

        本文将简单介绍std::accumulate、std::sort、std::find、std::count、std::partial_sum等函数，并给出其使用例程。

2. std::accumulate

        从字面意义上看，std::accumulate是做一个“积累”的操作。但需要注意的是，std::accumulate是对一个序列进行操作，但不仅限于“求和”，可以是序列里数依次相乘等。具体执行哪些操作，可以由函数原型中的“二元操作符”参数来指定，如果不指定，默认为序列求和。

        std::accumulate是一个用于计算给定范围内所有元素累积和的算法。它接受四个参数：起始迭代器、终止迭代器、初始值和一个二元操作符。默认情况下，二元操作符是加法，但可以自定义。

函数原型如下。

template<class InputIterator, class T>

T accumulate(InputIterator first, InputIterator last, T init);

template<class InputIterator, class T, class BinaryOp>

T accumulate(InputIterator first, InputIterator last, T init, BinaryOp op);

其中：

first, last：输入迭代器的范围，表示要操作的序列。

init：累积操作的初始值。

op：二元操作符，默认为加法，但也可以是其他任何有效的二元操作。当设定不同的二元操作符时可以实现不同的“积累”操作。如std::multiplies<int>()实现序列元素的依次相乘.

例程: 序列求乘积：

#include <iostream>  

#include <vector>  

#include <numeric> ///< std::accumulate的库  

 

int main(int argc, char* argv)

{

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

    /** 使用默认的加法操作符计算累积和. */

    int sum = std::accumulate(numbers.begin(), numbers.end(), 0);  

    std::cout << "Sum of numbers: " << sum << std::endl; ///< 输出应为 15  

 

    /** 使用自定义的乘法操作符计算累积积. */

    int product = std::accumulate(numbers.begin(), numbers.end(), 1, std::multiplies<int>());  

    std::cout << "Product of numbers: " << product << std::endl; ///< 输出应为 120  

 

    return 0;  

}

例程：连接字符串

#include <iostream>  

#include <vector>  

#include <numeric> ///< std::accumulate  

#include <string>  

 

int main(int argc, char* argv[])

{

    std::vector<std::string> strings = {"Hello", " ", "World", "!"};  

 

    /** 使用 std::accumulate 连接字符串. */

    std::string result = std::accumulate(strings.begin(), strings.end(), std::string());  

    std::cout << result << std::endl; ///< 输出: Hello World!  

    return 0;  

}

3. std::sort

        std::sort主要用来排序。具体使用可参考已经发过的文章。

C++(15): STL算法：排序（sort）-CSDN博客

4. std::find

        std::find主要用来在特定范围内查找特定元素。如果找到该元素，则返回一个迭代器，指向该元素在范围中的位置。如果没有找到，它将返回范围的“尾后”迭代器（即范围的结束迭代器），表示该元素不存在于范围内。

原型如下。

template<class InputIterator, class T>  

InputIterator find(InputIterator first, InputIterator last, const T& value);

下面是一个在std::vector中使用std::find的例程。

#include <iostream>  

#include <vector>  

#include <algorithm>  

 

int main(int argc, char* argv[])

{

    std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9};  

    int search_value = 5;  

     

    auto it = std::find(vec.begin(), vec.end(), search_value);  

     

    if (it != vec.end()) {  

        std::cout << "Found " << search_value << " at position " << (it - vec.begin()) << std::endl;  

    } else {  

        std::cout << search_value << " not found in the vector." << std::endl;  

    }  

     

    return 0;  

}

        使用std::find的时候，有几点需要注意：

1. std::find 是一个线性搜索算法，其时间复杂度为 O(n)，其中 n 是搜索范围的大小。对于大型数据集，这可能会很慢。
2. 如果你需要对大量数据进行频繁搜索，或者需要更高效的搜索算法，你可能需要考虑使用其他数据结构（如 std::set、std::map 或 std::unordered_map），它们提供了更快的搜索性能。
3. std::find 是一个通用算法，可以用于任何提供随机访问迭代器的容器（如 std::vector、std::deque 等）。它也可以用于不支持随机访问迭代器的容器（如 std::list），但性能可能较差。

5. std::count

        std::count 是 C++ 标准库中的一个算法，用于计算在给定的范围内特定元素出现的次数。这个算法遍历整个范围，并对等于给定值的元素进行计数。其原型如下。

template <class InputIt, class T>

size_t count(InputIt first, InputIt last, const T& value);

first 和 last 是输入迭代器，指定了搜索范围的起始和结束（结束迭代器指向的是范围的最后一个元素之后的位置）。

value 是要计数的值。

返回值是一个表示范围内等于 value 的元素数量的整数。

例程：

#include <iostream>  

#include <vector>  

#include <algorithm>  

 

int main(int argc, char* argv[])

{

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

    int value_to_count = 3;  

     

    size_t count = std::count(numbers.begin(), numbers.end(), value_to_count);  

     

    std::cout << "The number " << value_to_count << " appears " << count << " times." << std::endl;  

     

    return 0;  

}

6. std::partial_sum

        std::partial_sum 是 C++ 标准库 <numeric> 头文件中提供的一个算法，用于计算序列的部分和（partial sums）。这个算法会计算输入序列中元素的部分累积和，并将这些部分和存储在另一个序列中。其原型如下。

template< class InputIt, class OutputIt >

OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first );

template< class InputIt, class OutputIt, class BinaryOperation >

OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first,

                      BinaryOperation op );

例程：

#include <iostream>  

#include <vector>  

#include <numeric>  

 

int main(int argc, char* argv[])

{

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

    std::vector<int> partialSums(numbers.size());  

     

    std::partial_sum(numbers.begin(), numbers.end(), partialSums.begin());  

     

    /** 输出部分和序列. */

    for (int sum : partialSums) {  

        std::cout << sum << " ";  

    }  

    std::cout << std::endl;  

     

    return 0;  

}