C++：STL算法

STL中算法大致分为四类：
  非可变序列算法：指不直接修改其所操作的容器内容的算法。
  可变序列算法： 指可以修改它们所操作的容器内容的算法。
  排序算法：   包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作。
  数值算法：   对容器内容进行数值计算。

要使用 STL中的算法函数必须包含头文件algorithm，数值算法须包含numeric，使用模板类须包含functional

一、查找
  1、元素查找 find
    用于查找等于某值的元素。它在迭代器区间 [first, last) 上查找等于value值的元素，如果迭代器i所指的元素满足*i=value，则返回迭代器i，未找到满足条件的元素，返回last。函数原型：find( v.begin(), v.end(), vlaue)

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

using namespace std;

int main(void)
{
    int num = 6;
    vector<int> v;

    for(int i=0; i<10; ++i)
        v.push_back(2*i);

    cout << "vector<int> v: ";
    for(vector<int>::size_type index=0; index!=v.size(); ++index)
        cout << v[index] << " ";

    cout << endl;

    vector<int>::iterator result;
    result = find(v.begin(), v.end(), num);
    if(result != v.end())
        cout << "匹配元素的索引：" << result - v.begin() << endl;
    else
        cout << "没有与元素匹配的索引" << endl;

    return 0;
}

[[email protected] C++]$ ./a.out 
vector<int> v: 0 2 4 6 8 10 12 14 16 18 
匹配元素的索引：3

  2、条件查找 find_if
    利用返回布尔值的谓词判断pred，检查迭代器区间 [first,last) 上的每一个元素，如果迭代器i满足pred（*i）＝true，表示找到元素并返回迭代值i（找到的第一个符合条件的元素），未找到元素，返回末位置last。函数原型：find_if(v.begin(), v.end(), finda)

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

using namespace std;

bool finda(int x)
{
    return x%10?0:1;
}

int main(void)
{
    vector<int> v;

    for(int i=0; i<10; ++i)
        v.push_back((i+1)*(i+2));

    cout << "vector<int> v: ";
    for(vector<int>::size_type index=0; index!=v.size(); ++index)
        cout << v[index] << " ";

    cout << endl;

    vector<int>::iterator result;
    result = find_if(v.begin(), v.end(), finda);
    if(result != v.end())
        cout << "第一个能整除10的元素：" << *result << "，索引： " << result - v.begin() << endl;

    return 0;
}

[[email protected] C++]$ ./a.out 
vector<int> v: 2 6 12 20 30 42 56 72 90 110 
第一个能整除10的元素：20，索引： 3

  2、最后一个子序列查找find_end
    查找子序列v2在v1中最后出现的位置。函数原型：find_end(v1.begin(), v1.end(), v2.begin(), v2.end())

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

using namespace std;

int main(void)
{
    vector<int> v1;
    vector<int> v2;

    for(int i=0; i<10; ++i)
        v1.push_back(i);

    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);

    for(int i=1; i<4; ++i)
        v2.push_back(i);

    cout << "vector<int> v1: ";
    for(vector<int>::size_type index=0; index!=v1.size(); ++index)
        cout << v1[index] << " ";

    cout << endl;

    cout << "vector<int> v2: ";
    for(vector<int>::size_type index=0; index!=v2.size(); ++index)
        cout << v2[index] << " ";

    cout << endl;

    vector<int>::iterator result = find_end(v1.begin(), v1.end(), v2.begin(), v2.end());

    if(result != v1.end())
        cout << "v2在v1的最后位置：v[" << result-v1.begin() << "]" << endl;
    else
        cout << "v2不在v1中" << endl;

    return 0;
}

[[email protected] C++]$ ./a.out     
vector<int> v1: 0 1 2 3 4 5 6 7 8 9 1 2 3 
vector<int> v2: 1 2 3 
v2在v1的最后位置：v[10]

二、统计
  1、元素统计count：统计某个指定的值出现了多少次。函数原型：count(v.begin(), v.end(), value)

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

using namespace std;

int main(void)
{
    vector<int> v;

    for(int i=0; i<10; ++i)
        v.push_back(i);

    cout << "vector<int> v: ";
    for(vector<int>::size_type index=0; index!=v.size(); ++index)
        cout << v[index] << " ";

    cout << endl;

    cout << "与6相等的元素个数：" << count(v.begin(), v.end(), 6) << endl;

    return 0;
}

[[email protected] C++]$ ./a.out 
vector<int> v: 0 1 2 3 4 5 6 7 8 9 
与6相等的元素个数：1

  2、条件统计count_if：统计符合某个指定条件的值出现了多少次。函数原型：count_if(v.begin(), v.end(), greater6)

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

using namespace std;

bool greater6(int x)
{
    return (x>6);
}

int main(void)
{
    vector<int> v;

    for(int i=0; i<10; ++i)
        v.push_back(i);

    cout << "vector<int> v: ";
    for(vector<int>::size_type index=0; index!=v.size(); ++index)
        cout << v[index] << " ";

    cout << endl;

    cout << "大于6的元素个数：" << count_if(v.begin(), v.end(), greater6) << endl;

    return 0;
}

[[email protected] C++]$ ./a.out 
vector<int> v: 0 1 2 3 4 5 6 7 8 9 
大于6的元素个数：3

三、搜索
  1、子序列搜索search
    在一个序列中搜索与另一序列匹配的子序列。参数分别为一个序列的开始位置，结束位置和另一个序列的开始，结束位置。函数原型：search(v1.begin(), v1.end(), v2.begin(), v2.end())

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

using namespace std;

int main(void)
{
    vector<int> v1;
    vector<int> v2;

    for(int i=0; i<10; ++i)
        v1.push_back(i);

    for(int j=0; j<5; ++j)
        v2.push_back(j);

    cout << "vector<int> v1: ";
    for(vector<int>::size_type index=0; index!=v1.size(); ++index)
        cout << v1[index] << " ";

    cout << endl;

    cout << "vector<int> v2: ";
    for(vector<int>::size_type index=0; index!=v2.size(); ++index)
        cout << v2[index] << " ";

    cout << endl;

    vector<int>::iterator result = search(v1.begin(), v1.end(), v2.begin(), v2.end());

    if(result != v1.end())
        cout << "V2的元素包含在v1中，范围：v1[" << result-v1.begin() << "]~v1[" << result+v2.size()-v1.begin()-1 << "]" << endl;
    else
        cout << "v2的元素不包含在v1中" << endl;

    return 0;
}

[[email protected] C++]$ ./a.out 
vector<int> v1: 0 1 2 3 4 5 6 7 8 9 
vector<int> v2: 0 1 2 3 4 
V2的元素包含在v1中，范围：v1[0]~v1[4]

  2、重复子序列搜索search_n
    搜索序列中是否有一系列元素值均为某个给定值的子序列。函数原型：search_n(v.begin(), v.end(), n, value)

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

using namespace std;

int main(void)
{
    vector<int> v;

    for(int i=0; i<10; ++i)
        v.push_back(i);

    v.push_back(10);
    v.push_back(10);
    v.push_back(10);
    v.push_back(10);

    cout << "vector<int> v: ";
    for(vector<int>::size_type index=0; index!=v.size(); ++index)
        cout << v[index] << " ";

    cout << endl;

    vector<int>::iterator result = search_n(v.begin(), v.end(), 4, 10);

    if(result != v.end())
        cout << "v包含4个10" << endl;
    else
        cout << "v中没有4个10" << endl;

    return 0;
}

[[email protected] C++]$ ./a.out     
vector<int> v: 0 1 2 3 4 5 6 7 8 9 10 10 10 10 
v包含4个10

四、复制copy
  将一个容器的元素复制到另一个元素中。函数原型：copy(v1.begin(), v1.end(), v2.begin())

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

using namespace std;

int main(void)
{
    vector<int> v1;
    vector<int> v2;

    for(int i=10; i<15; ++i)
        v1.push_back(i);

    for(int i=0; i<10; ++i)
        v2.push_back(i);

    cout << "vector<int> v1: ";
    for(vector<int>::size_type index=0; index!=v1.size(); ++index)
        cout << v1[index] << " ";

    cout << endl;

    cout << "vector<int> v2: ";
    for(vector<int>::size_type index=0; index!=v2.size(); ++index)
        cout << v2[index] << " ";

    cout << endl;

    copy(v1.begin(), v1.end(), v2.begin());

    cout << "vector<int> v2: ";
    for(vector<int>::size_type index=0; index!=v2.size(); ++index)
        cout << v2[index] << " ";

    cout << endl;

    return 0;
}

[[email protected] C++]$ ./a.out 
vector<int> v1: 10 11 12 13 14 
vector<int> v2: 0 1 2 3 4 5 6 7 8 9 
vector<int> v2: 10 11 12 13 14 5 6 7 8 9

五、元素改变transform
  将一个容器的元素改变之后放到另一个容器中。函数原型：transform(v1.begin(), v1.end(), v2.begin(), op_increase)

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

using namespace std;

int op_increase(int x)  { return (x+2); }

int main(void)
{
    vector<int> v1;
    vector<int> v2;

    for(int i=1; i<11; i++)
        v1.push_back(i);

    cout << "vector<int> v1: ";
    for(vector<int>::size_type i=0; i<v1.size(); ++i)
        cout << v1[i] << " ";

    cout << endl;

    v2.resize(v1.size());

    transform(v1.begin(), v1.end(), v2.begin(), op_increase);

    cout << "Transform vector<int> v2: ";
    for(vector<int>::iterator it=v2.begin(); it!=v2.end(); ++it)
        cout << *it << " ";

    cout << endl;

    return 0;
}

[[email protected] C++]$ ./a.out 
vector<int> v1: 1 2 3 4 5 6 7 8 9 10 
Transform vector<int> v2: 3 4 5 6 7 8 9 10 11 12 

六、替换replace
  将指定元素值替换为新值。函数原型：replace(v.begin(), v.end(), n, m)

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

using namespace std;

int main(void)
{
    vector<int> v;

    for(int i=1; i<11; i++)
        v.push_back(i);

    cout << "vector<int> v: ";
    for(vector<int>::size_type i=0; i<v.size(); ++i)
        cout << v[i] << " ";

    cout << endl;

    replace(v.begin(), v.end(), 10, 100);

    cout << "Replace vector<int> v: ";
    for(vector<int>::iterator it=v.begin(); it!=v.end(); ++it)
        cout << *it << " ";

    cout << endl;

    return 0;
}

[[email protected] C++]$ ./a.out 
vector<int> v1: 1 2 3 4 5 6 7 8 9 10 
Replace vector<int> v1: 1 2 3 4 5 6 7 8 9 100 

七、填充
  1、fill
    填充[a, b)范围。函数原型：fill(a, b, m)

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

using namespace std;

int main(void)
{
    vector<int> v;

    for(int i=1; i<11; i++)
        v.push_back(i);

    cout << "vector<int> v1: ";
    for(vector<int>::size_type i=0; i<v.size(); ++i)
        cout << v[i] << " ";

    cout << endl;

    fill(v.begin(), v.begin()+5, 100);

    cout << "Fill vector<int> v: ";
    for(vector<int>::iterator it=v.begin(); it!=v.end(); ++it)
        cout << *it << " ";

    cout << endl;

    return 0;
}

[[email protected] C++]$ ./a.out 
vector<int> v1: 1 2 3 4 5 6 7 8 9 10 
Fill vector<int> v: 100 100 100 100 100 6 7 8 9 10

  2、fill_n(b,n,v)
    填充[b, b+n)范围。函数原型：fill(b, n, m)

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

using namespace std;

int main(void)
{
    vector<int> v;

    for(int i=1; i<11; i++)
        v.push_back(i);

    cout << "vector<int> v1: ";
    for(vector<int>::size_type i=0; i<v.size(); ++i)
        cout << v[i] << " ";

    cout << endl;

    fill_n(v.begin(), 5, 100);

    cout << "Fill vector<int> v: ";
    for(vector<int>::iterator it=v.begin(); it!=v.end(); ++it)
        cout << *it << " ";

    cout << endl;

    return 0;
}

[[email protected] C++]$ ./a.out 
vector<int> v1: 1 2 3 4 5 6 7 8 9 10 
Fill vector<int> v: 100 100 100 100 100 6 7 8 9 10

  3、generate
    按一定方法填充容器。函数原型：generate(v.begin(), v.end(), increase)

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

using namespace std;

int increase(void)
{
    static int x = 1;

    return x++;
}

int main(void)
{
    vector<int> v(10);

    generate(v.begin(), v.end(), increase);

    cout << "vector<int> v: ";
    for(vector<int>::size_type i=0; i<v.size(); ++i)
        cout << v[i] << " ";

    cout << endl;

    return 0;
}

[[email protected] C++]$ ./a.out 
vector<int> v: 1 2 3 4 5 6 7 8 9 10 

  4、generate_n
    按一定方法填充[a, a+n)容器。函数原型：generate_n(v.begin(), n, increase)

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

using namespace std;

int increase(void)
{
    static int x = 1;

    return x++;
}

int main(void)
{
    vector<int> v(10);

    generate_n(v.begin(), 5, increase);

    cout << "vector<int> v: ";
    for(vector<int>::size_type i=0; i<v.size(); ++i)
        cout << v[i] << " ";

    cout << endl;

    return 0;
}

[[email protected] C++]$ ./a.out 
vector<int> v: 1 2 3 4 5 0 0 0 0 0 

八、移除
  1、remove
    remove并不会真正删除容器中的元素。是把区间内的元素值为指定值的元素的位置腾出，然后后面的元素就会往前移动，但是原来容器的end()并不会改变。函数原型：remove(v.begin(), v.end(), n);

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

using namespace std;

int main(void)
{
    vector<int> v;

    for(int i=1; i<11; i++)
        v.push_back(i);

    cout << "vector<int> v: ";
    for(vector<int>::size_type i=0; i<v.size(); ++i)
        cout << v[i] << " ";

    cout << endl;

    remove(v.begin(), v.end(), 5);

    cout << "Remove vector<int> v: ";
    for(vector<int>::iterator it=v.begin(); it!=v.end(); ++it)
        cout << *it << " ";

    cout << endl;

    return 0;
}

[[email protected] C++]$ ./a.out 
vector<int> v: 1 2 3 4 5 6 7 8 9 10 
Remove vector<int> v: 1 2 3 4 6 7 8 9 10 10 

  2、remove_if
    移除满足条件的元素后，end保持不变。函数原型：remove_if(v.begin(), v.end(), increase)

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

using namespace std;

bool increase(int x)
{
    return (x%2?0:1);
}

int main(void)
{
    vector<int> v;

    for(int i=1; i<11; i++)
        v.push_back(i);

    cout << "vector<int> v: ";
    for(vector<int>::size_type i=0; i<v.size(); ++i)
        cout << v[i] << " ";

    cout << endl;

    remove_if(v.begin(), v.end(), increase);     // 移除偶数

    cout << "Remove vector<int> v: ";
    for(vector<int>::iterator it=v.begin(); it!=v.end(); ++it)
        cout << *it << " ";

    cout << endl;

    return 0;
}

[[email protected] C++]$ ./a.out 
vector<int> v: 1 2 3 4 5 6 7 8 9 10 
Remove vector<int> v: 1 3 5 7 9 6 7 8 9 10

  3、unique
    删除相邻的重复元素，然后重新排列输入范围内的元素。函数原型：unique(v.begin(), v.end())

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

using namespace std;

int main(void)
{
    vector<int> v;

    v.push_back(1);
    v.push_back(1);
    v.push_back(2);
    v.push_back(2);
    v.push_back(3);
    v.push_back(3);
    v.push_back(4);
    v.push_back(4);

    cout << "vector<int> v: ";
    for(vector<int>::size_type i=0; i<v.size(); ++i)
        cout << v[i] << " ";

    cout << endl;

    unique(v.begin(), v.end());

    cout << "Unique vector<int> v: ";
    for(vector<int>::iterator it=v.begin(); it!=v.end(); ++it)
        cout << *it << " ";

    cout << endl;

    return 0;
}

[[email protected] C++]$ ./a.out 
vector<int> v: 1 1 2 2 3 3 4 4 
Unique vector<int> v: 1 2 3 4 3 3 4 4 

九、排序
  1、sort
    函数原型：sort(v.begin(), v.end())

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

using namespace std;

int main(void)
{
    vector<int> v;

    v.push_back(1);
    v.push_back(7);
    v.push_back(8);
    v.push_back(4);
    v.push_back(9);
    v.push_back(3);
    v.push_back(10);
    v.push_back(15);

    cout << "vector<int> v: ";
    for(vector<int>::size_type i=0; i<v.size(); ++i)
        cout << v[i] << " ";

    cout << endl;

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

    cout << "Sort vector<int> v: ";
    for(vector<int>::iterator it=v.begin(); it!=v.end(); ++it)
        cout << *it << " ";

    cout << endl;

    return 0;
}

[[email protected] C++]$ ./a.out 
vector<int> v: 1 7 8 4 9 3 10 15 
Sort vector<int> v: 1 3 4 7 8 9 10 15 

  注：
    也可以自己定义排序的方法，自己编写一个比较函数来实现，然后调用三个参数。函数原型sort(v.begin(), v.end(), function)

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

using namespace std;

bool function(int x, int y)
{
    return (x > y);
}

int main(void)
{
    vector<int> v;

    v.push_back(1);
    v.push_back(7);
    v.push_back(8);
    v.push_back(4);
    v.push_back(9);
    v.push_back(3);
    v.push_back(10);
    v.push_back(15);

    cout << "vector<int> v: ";
    for(vector<int>::size_type i=0; i<v.size(); ++i)
        cout << v[i] << " ";

    cout << endl;

    sort(v.begin(), v.end(), function);

    cout << "Sort vector<int> v: ";
    for(vector<int>::iterator it=v.begin(); it!=v.end(); ++it)
        cout << *it << " ";

    cout << endl;

    return 0;
}

[[email protected] C++]$ ./a.out 
vector<int> v: 1 7 8 4 9 3 10 15 
Sort vector<int> v: 15 10 9 8 7 4 3 1