STL 笔记（五）算法 algorithm

2022-10-07 09:39:21

在 STL 中，算法是一系列的函数模版。STL 提供了大概 70 个算法，由头文件 <algorithm>、<numeric>、<functional>组成。

头文件 <algorithm> 是最大的一个，里面经常使用到的功能有：查找、排序、改动、移除、交换、合并等；
头文件 <numeric> 较小，主要包含相关数学运算的函数模版，以及加法和乘法在序列上的一些操作；
头文件 <functional> 中则定义了一些类模版，来声明函数对象；

算法的分类：

算法按事实上现的功能可分为 8 类：查找、排序、数值计算、比較、集合、容器管理、统计、堆操作。
算法按对容器的影响可分为 4 类：非修正、修正、排序、数值计算；

非修正算法

非修正即不正确容器中元素做改动。是仅仅读操作。如：find()、count()、equal()、for_each()、search()等。详细例如以下：

adjacent_find     #查找同样的相邻元素 返回第一个元素的迭代器

find              #查找

find_first_of

find_end

find_last_of

count             #统计同样元素的个数

count_if

mismatch          #返回 pair<第一个序列的迭代器，第二个序列的迭代器> 表明第一处不相符合的位置

equal             #比較容器中的元素是否同样

for_each          #经常使用，遍历序列并对序列中每一个元素採用仿函数中定义的操作

search            #返回迭代器，第一次出现序列二或者某元素的位置

search_n          #前n次连续出现某元素或者符合条件的第一个位置

修正算法

修正算法即对容器中元素做改动，须要写操作。

如：copy()、remove()、reverse()、swap()、unique()等。详细例如以下：

copy                #复制元素到目的容器

copy_backward       #从后往前复制

fill                #用某元素填充容器

fill_n

generate            #把仿函数产生的结果依次拷贝到容器中

generate_n

partition           #以仿函数为标准，把容器分成前后两部分，前半部分是能使仿函数返回真的元素，后半返回假

stable_partition

random_shuffle      #对容器中的元素进行随机排列

remove              #删除某一范围内的元素，注意：移除的元素被放到容器末尾，还是能够用迭代器遍历到，函数返回移除后容器的末尾

remove_if

erase               #擦除区间内全部的元素

replace             #在规定区间内把某值换成新值

replace_if

replace_copy        #把区间内元素拷贝到目的地而且把当中某些元素替换成新值

replace_copy_if

rotate              #把 middle-end 的元素放到 first 的位置上

rotate_copy

swap                #元素的交换

swap_ranges

transform           #把元素依照仿函数中内容转换

unique              #保证相邻元素间没有同样的，能够加仿函数做为推断根据，返回最后一个位置的迭代器

unique_copy

排序算法

排序须要移动元素，所以须要用到随机訪问迭代器 RandomAccessIterator，而且指定 [begin,end) 这个前闭后开区间，且可自定义比較函数做參数传入。

常见容器的排序

vector 和 deque。还有数组，支持随机存取。能够用 algorithm 中的排序。
list 容器是双向链表，不支持随机訪问迭代器，内置了一种稳定排序方法，用的是自底向上的归并排序；
map 和 set 底层是红黑树。本身就是有序存储；

经常使用的排序函数

sort                    #对给定区间全部元素进行排序，用的是快排

stable_sort             #稳定排序，保证值相等的元素排序后相对位置不变。用归并排序实现

partial_sort            #部分排序，保证前n个值有序而且后面的值不在前n个值的范围内，但后面的值不保证有序，堆排序实现

partial_sort_copy       #对给定区间复制并排序

nth_element             #把第n个元素放到第n个位置上去。比它大的都在后。比它小的都在前，但各自都不保证有序

is_sorted               #推断一个区间是否已经排好序

partition               #使得符合某个条件的元素放在前面

stable_partition        #相对稳定的使得符合某个条件的元素放在前面

经常使用的比較函数

less              #小于（缺省比較函数）

greater           #大于

equal_to          #等于

less_equal        #小于等于

greater_equal     #大于等于

自己定义比較大小

使用时不能直接写入仿函数的名字，而是要写其重载的() 函数。如 less<int>()。以下是 stl 中的 less 的部分源代码：

template <class _Tp>

struct less : public binary_function<_Tp,_Tp,bool>

{

  bool operator()(const _Tp& __x, const _Tp& __y) const { return __x < __y; }

};

对于基本数据类型和 string 能够使用 stl 中现成的函数模版，对于自定义的类。能够通过自己写比較函数或重载 < 操作符来实现。当中，重载 < 运算符相当于间接的用到了内置的 less 。

小样例

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

class Test {

public:

    Test(int a):a(a){};

    int a;

    bool operator <(const Test &k) const {

        return a < k.a;

    }

};

int main(){

    vector<Test> a;

    a.push_back(Test(2));

    a.push_back(Test(3));

    a.push_back(Test(1));

    vector<Test>::iterator iter;

    sort(a.begin(), a.end());

    for(iter = a.begin(); iter != a.end(); ++iter){

        cout<< iter->a <<" ";

    }  // 输出排序后：1 2 3

}

数值计算

数值计算函数

数值计算算法主要针对容器中元素的计算，如 accumulate()、inner_product()、partial_sum()、adjacent_difference()和一些推广的数值算法。

详细：

accumulate          #遍历求和，也能够用仿函数求其它数值

inner_product       #内积。对应位置相乘再相加

partial_sum         #部分元素之和，把结果放到后一容器中，后一容器的第n个元素师前一容器的前n个容器元素之和

adjacent_difference #相邻元素之差，把结果放到后一容器中

小样例

#include <iostream>

#include <functional>

#include <numeric>

#include <vector>

using namespace std;

int main() {

    int a[3] = { 2, 2, 3 };

    int re = accumulate(a, a + 3, 0);

    cout << re << endl;    // 7, 累加

    vector<int> b;

    b.push_back(2);

    b.push_back(2);

    b.push_back(3);

    int re1 = accumulate(b.begin(), b.end(), 0, plus<int>());

    cout << re1 << endl;  // 7, 累加

    int re2 = accumulate(b.begin(), b.end(), 1, multiplies<int>());

    cout << re2;          // 12, 累乘

}

有序容器、堆、集合

binary_search    #二分法搜索，在有序容器中提高搜索速度

lower_bound      #返回第一次出现该元素的位置

upper_bound      #返回最后一次出现该元素的后一位置

equal_range      #返回pair<lower_bound,upper_bound>

inplace_merge    #将连贯有序序列合并

merge            #合并两个容器

includes         #推断某区间内全部的元素是否在还有一区间中

#堆操作

push_heap

pop_heap

sort_heap

make_heap

#集合操作

set_intersection

set_difference

set_symmetric_difference

#最值

min                       #最小

max                       #最大

min_element               #最小位置的迭代器

max_element               #最大位置的迭代器

lexicograplical_compare   #范围内的字典序比較。前后序列的比較

next_permutation prev_permutation   #上一个/下一个全排列

【原文地址：http://blog.csdn.net/thisinnocence/article/details/39941603】

码农公寓