ACM/ICPC竞赛之STL--algorithm

ACM模版

algorithm

<algorithm>无疑是STL中最大的一个头文件,它是由一大堆模板函数组成的。

以下列举出<algorithm>中的模版函数：
A

adjacent_find

B

binary_search

C

copy / copy_backward / count / count_if

E

equal / equal_range

F

fill / fill_n / find / find_end / find_first_of / find_if / for_each

G

generate / generate_n

I

includes / inplace_merge / iter_swap

L

lexicographical_compare / lower_bound

M

make_heap / max / max_element / merge / min / min_element / mismatch

N

next_permutation / nth_element

P

partial_sort / partial_sort_copy / partition / pop_heap / prev_permutation / push_heap

R

random_shuffle / remove / remove_copy / remove_copy_if / remove_if / replace / replace_copy / replace_copy_if / replace_if / reverse / reverse_copy / rotate / rotate_copy

S

search / search_n / set_difference / set_intersection / set_symmetric_difference / set_union / sort / sort_heap / stable_partition / stable_sort / swap / swap_ranges

T

transform

U

unique / unique_copy / upper_bound

Example:

1、for_each遍历容器

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

using namespace std;

int visit(int v)    // 遍历算子函数
{
    cout << v << " ";
    return 1;
}

class multInt       // 定义遍历算子类
{
private:
    int factor;
public:
    multInt(int f) : factor(f) {}

    void operator() (int &elem) const
    {
        elem *= factor;
    }
};

int main()
{
    vector<int> L;
    for (int i = 0; i < 10; i++)
    {
        L.push_back(i);
    }
    for_each(L.begin(), L.end(), visit);
    cout << '\n';
    for_each(L.begin(), L.end(), multInt(2));
    for_each(L.begin(), L.end(), visit);
    cout << '\n';

    return 0;
}

程序输出结果为：
0 1 2 3 4 5 6 7 8 9
0 2 4 6 8 10 12 14 16 18

2、min_element/max_element找出容器中的最小/最大值

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

using namespace std;

int main()
{
    vector<int> L;
    for (int i=0; i<10; i++) 
    {
        L.push_back(i);
    }
    vector<int>::iterator min_it = min_element(L.begin(), L.end());
    vector<int>::iterator max_it = max_element(L.begin(), L.end());
    cout << "Min is " << *min_it << endl;
    cout << "Max is " << *max_it << endl;

    return 0;
}

程序的输出结果：
Min is 0
Max is 9

3、sort对容器进行排序

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

using namespace std;

void Print(vector<int> &L)
{
    for (vector<int>::iterator it = L.begin(); it != L.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
    return ;
}

int main()
{
    vector<int> L;
    for (int i = 0; i < 5; i++) 
    {
        L.push_back(i);
    }
    for (int i = 9; i >= 5; i--) 
    {
        L.push_back(i);
    }
    Print(L);
    sort(L.begin(), L.end());
    Print(L);
    sort(L.begin(), L.end(), greater<int> ());  // 按降序排序
    Print(L);

    return 0;
}

程序的输出结果：
0 1 2 3 4 9 8 7 6 5
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0

4、copy在容器间复制元素

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

using namespace std;

int main()
{
    // 先初始化两个向量vOne和vTwo
    vector<int> vOne, vTwo;
    for (int i = 0; i <= 5; i++)
    {
        vOne.push_back(10 * i);
    }
    for (int i = 0; i <= 10; i++)
    {
        vTwo.push_back(3 * i);
    }

    cout << "vOne = ( ";
    for (vector<int>::iterator it = vOne.begin(); it != vOne.end(); it++)
    {
        cout << *it << " ";
    }
    cout << ")" << '\n';

    cout << "vTwo = ( ";
    for (vector<int>::iterator it = vTwo.begin(); it != vTwo.end(); it++)
    {
        cout << *it << " ";
    }
    cout << ")" << '\n';

    // 将vOne的前三个元素复制到vTwo的中间（覆盖掉原来数据）
    copy(vOne.begin(), vOne.begin() + 3, vTwo.begin() + 4);

    cout << "vTwo with vOne insert = ( " ;
    for (vector <int>::iterator it = vTwo.begin(); it != vTwo.end(); it++)
    {
        cout << *it << " ";
    }
    cout << ")" << '\n';

    // 在vTwo内部进行复制，注意参数2表示结束位置，结束位置不参与复制
    copy(vTwo.begin() + 4, vTwo.begin() + 7, vTwo.begin() + 2);

    cout << "vTwo with shifted insert = ( " ;
    for (vector <int>::iterator it = vTwo.begin(); it != vTwo.end(); it++)
    {
        cout << *it << " ";
    }
    cout << ")" << '\n';

    return 0;
}

程序的输出结果：
vOne = ( 0 10 20 30 40 50 )
vTwo = ( 0 3 6 9 12 15 18 21 24 27 30 )
vTwo with vOne insert = ( 0 3 6 9 0 10 20 21 24 27 30 )
vTwo with shifted insert = ( 0 3 0 10 20 10 20 21 24 27 30 )