常用算法 - C语言学习教程_C语言程序_ c语言编程

1、for_each()算法

for_each()属于非可变序列算法，此算法非常灵活，可以同时处理修改每一个元素，其函数定义如下所示：

template<typename InputIterator, typename Function>
for_each(InputIterator begin, InputIterator end, Function func);

for_each()算法对[begin, end)区间中的每个元素都调用func函数（对象）进行操作，它不会对区间中的元素做任何修改，也不会改变原来序列的元素次序。

2、find()算法

find()也属于非可变序列算法，用于在指定区间查找某一元素是否存在，其函数原型如下所示：

template<typename InputIterator, typename T>
InputIterator find(InputeIterator first, InputIterator last, const T& value);

find()算法用于在[begin, last)区间查找value元素是否存在，如果存在，就返回指向这个元素的迭代器，如果不存在，就返回end。

3、copy()算法

对于copy()函数，我们并不陌生，在讲解迭代器几次都用到了copy()函数，它的功能是完成元素的复制，其函数原型如下所示：

template<typename InputIterator, typename OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last, 
OutputIterator DestBeg);

copy()函数实现将[first, last)区间的元素复制到另一个地方，这个地方的起始位置为DestBeg。由于在讲解迭代器时，已经多次调用copy()函数将元素复制到cout流对象中输出到屏幕，因此这里就不再举例演示copy()函数的用法。

4、sort()算法

sort()属于可变序列算法，它支持对容器中的所有元素进行排序，函数的原型有如下两种形式：

template<typename RanIt>              //第一种形式
void sort(RanIt first, RanIt last);       
template<typename RanIt, typename Pred>     //第二种形式
void sort(RanIt first, RanIt last, Pred op);

● 第一种形式是默认的按从小到大的顺序排列；

● 第二种形式比第一种形式更加通用，它可以指定排序规则。

sort()算法所使用的迭代区间必须是随机迭代器，因此只能适用于vector与deque容器，list容器不支持随机迭代器，不能使用该算法，但list容器提供了sort()成员函数，用于自身的元素排序。

5、accumulate()算法

accumulate()算法属于数值算法，它的原型如下所示：

template<typename InputIterator, typename T>          //第一种形式
T accumulate(InputIterator first, InputIterator last, T t);
template<typename InputIterator, typename T,typename Pred> //第一种形式
T accumulate(InputIterator first, InputIterator last, T t, Pred op);

该函数的功能是将[first, last)区间内的数值累加，累加的初始值为t，它的返回值是元素累加结果。第二种形式可以按照指定的规则将元素相加。

注意：初始值类型必须与容器中元素的类型相匹配。

接下来，我们通过一个案例调用这几个算法函数，来演示其用法，具体如例1所示。

例1

 1    #include <iostream>
 2    #include <vector>
 3    #include <algorithm>
 4    #include <functional>
 5    #include <iterator>
 6    #include <numeric>
 7    using namespace std;
 8    template<typename T>
 9    class Multi  //类模板
 10    {
 11    private:
 12            T value;
 13    public:
 14            Multi(const T& v) :value(v){}  //构造函数
 15            void operator()(T& elem) const{ elem *= value; } //重载()运算符
 16    };
 17    void print(int elem) //打印元素
 18    {
 19        cout << elem << " ";
 20    }
 21    int main()
 22    {
 23        int arr[] = { 21, 4, 55, 22, 46, 79, 9, 5, 78, 34, 100 };
 24        vector<int> v;
 25        v.assign(arr, arr + sizeof(arr) / sizeof(int)); //用数组给v容器赋值
 26        
 27        //调用for_each()函数将容器中每个元素都乘以2
 28        for_each(v.begin(), v.end(), Multi<int>(2));
 29       
 30        //调用copy()构造函数将容器中元素输出
 31        copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));    cout << endl;
 32        
 33         //调用find()算法查找容器中是否存在值为200的元素
 34        vector<int>::iterator it = find(v.begin(), v.end(), 200); 
 35        if (*it == 200)
 36            cout << "容器中有值为200的元素" << endl;
 37        else
 38            cout << "容器中不存在值为200的元素" << endl;
 39    
 40        sort(v.begin(), v.end()); //调用sort()算法将容器中元素从小到大排列
 41        cout << "排序之后：" << endl;
 42        copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
 43        cout << endl;
 44        int sum = accumulate(v.begin(), v.end(), 0); //累加容器中元素
 45        cout << "sum = " << sum << endl;
 46        system("pause");
 47        return 0;
 48    }

运行结果如图1所示。

图1 例1运行结果

在例1中，代码第13-34行分别创建了一个int类型的数组和一个vector<int>类型的容器v，第25行代码调用assign()函数将数组中的元素赋值给容器v。第28行代码调用for_each()算法将容器中每个元素都乘以2，Multi<int>()是一个函数对象，其代码定义在9-16行，代码31行调用copy()算法将容器中元素输出，由图1可知，容器中每个元素都被乘以了2。代码34-38行调用find()算法查找容器中是否有值为200的元素，由图1的输出结果可知，容器中存在值为200的元素。代码第40行调用sort()算法将容器中元素按从小到大的顺序排列，由图1可知，元素排序成功。最后代码44行调用accumulate()算法将容器中元素累加，由图1输出结果可知，容器中元素累加结果为906。

至此，STL中的算法，读者已经领略，这几个常用算法要好好掌握，其他更多算法需要读者在实践中多多学习并应用，才能透彻理解掌握。