STL常用算法

遍历每个元素 for_each

for_each(vi.begin(), vi.end(), Print());

查找某个元素 find/find_if

auto it = find(vi.begin(), vi.end(), 5);

struct IsMultiple {
    int Divisor;
    IsMultiple(int x = 0) : Divisor(x) {}
    bool operator () (const int& input) {return !(input % Divisor);}
};

int main(int argc, char const *argv[])
{
    vector<int> vi;
    for (size_t i = 23; i < 32; i++) {
        vi.push_back(i);
    }
    int Divisor = 7;
    auto iElement = find_if(vi.begin(), vi.end(), IsMultiple(Divisor));
    if (iElement != vi.end()) {
        cout << "First element divisible by " << Divisor;
        cout << ": " << *iElement << endl;
    }
    return 0;
}
First element divisible by 7: 28

使用了find_if方法
对vi里的每个元素调用一元谓词IsMultiple(Divisor)函数对象，找到第一个整除Divisor的数

转换 transform

字符串大小写转换

string str = "hello";
string copy;
copy.resize(str.size());
transform(str.begin(), str.end(), copy.begin(), ::toupper);

从一个vector转换到另一个vector，进行一些变换

template<typename T>
class Add {
public:
    T operator () (const T& val) {return (val + 100);}
};
transform(vi.begin(), vi.end(), target.begin(), Add<int>());

计数 count/count_if

count(vi.begin(), vi.end(), 6)  返回等于6的数量
count_if(vi.begin(), vi.end(), Greater())   返回满足条件的数量

复制 copy/copy_if

vector<int> copyVec(vi.size() * 2);
auto it2 = copy(vi.begin(), vi.end(), copyVec.begin());
for_each(copyVec.begin(), copyVec.end(), [](const int& val) {cout << val << " ";});
cout << endl;

copy_if(vi.begin(), vi.end(), it2, [](int& val) {return (val % 2);});
for_each(copyVec.begin(), copyVec.end(), [](const int& val) {cout << val << " ";});
cout << endl;
0 1 2 3 4 5 6 7 8 9                         // vi
0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 0     // 复制了vi的全部元素
0 1 2 3 4 5 6 7 8 9 1 3 5 7 9 0 0 0 0 0     // 从返回的迭代器位置开始复制vi的奇数元素

搜索 binary_search

二分查找只能用于已排序的容器，返回true/false

删除 remove/remove_if

remove_if要配合erase使用，因为返回的是无用的部分的迭代器

vector<int> vi;
for (size_t i = 0; i < 10; i++) {
    vi.push_back(i);
}
info(vi);

int x = 5;
auto it = remove_if(vi.begin(), vi.end(), [x](int& val) {return val < x;});
info(vi);
cout << *it << endl;

vi.erase(it, vi.end());
info(vi);

0 1 2 3 4 5 6 7 8 9 
5 6 7 8 9 5 6 7 8 9     // 把 5~9替换掉前面的0~4
5   // 返回指向无用部分的第一个元素
5 6 7 8 9   // 再用erase把后面那些没用的删掉

删除重复元素 unique

auto it = unique(vi.begin(), vi.end());
vi.erase(it, vi.end());
info(vi);
-1 -1 -1 -1 8 8 8 8
-1 8

替换 replace/replace_if

vector<int> vi(8);
fill(vi.begin(), vi.begin() + 4, 5);
fill_n(vi.begin() + 4, 4, 8);
info(vi);

replace(vi.begin(), vi.end(), 5, 1);
info(vi);

replace_if(vi.begin(), vi.end(), [](int& val) {return (val % 2);}, -1);
info(vi);
5 5 5 5 8 8 8 8         // 填充前4格为5，后4歌为8
1 1 1 1 8 8 8 8         // 把5替换成1
-1 -1 -1 -1 8 8 8 8     // 把奇数替换成-1

分区 partition/stable_partition

partition是乱序的
stable_partition保持原来的顺序

// partition(vi.begin(), vi.end(), [](int& val) {return (val % 2);});
info(vi);
stable_partition(vi.begin(), vi.end(), [](int& val) {return (val % 2);});
info(vi);
0 1 2 3 4 5 6 7 8 9 
1 3 5 7 9 0 2 4 6 8 

lower_bound/upper_bound

auto it = lower_bound(vi.begin(), vi.end(), 5);
cout << *it << endl;

it = upper_bound(vi.begin(), vi.end(), 5);
cout << *it << endl;
0 1 2 3 4 5 6 7 8 9 
5   // 小于等于5的最大数是5
6   // 大于5的最小数是6

代码示例：基本数据类型

// 这种叫函数对象
class Print
{
public:
    void operator () (const int& val) {cout << val << " ";}
};

class Add
{
public:
    int operator () (const int& val) {return (val + 100);}
};

class Greater
{
public:
    bool operator () (const int& val) {return (val > 5);}
};

int main(int argc, char const *argv[])
{
    vector<int> vi;
    for (int i = 0; i < 10; i++) {
        vi.push_back(i);
    }
    for_each(vi.begin(), vi.end(), Print());
    cout << endl;

    auto it = find(vi.begin(), vi.end(), 5);
    if (it != vi.end()) {
        cout << *it << endl;
    }

    cout << binary_search(vi.begin(), vi.end(), 8) << endl;

    it = find_if(vi.begin(), vi.end(), Greater());
    if (it != vi.end()) {
        cout << "Found greater than five: " << *it << endl;
    }

    vi.push_back(6);
    cout << "number of six: " << count(vi.begin(), vi.end(), 6) << endl;
    cout << "num of greater than five: " << count_if(vi.begin(), vi.end(), Greater()) << endl;

    vector<int> target;
    target.resize(vi.size());
    transform(vi.begin(), vi.end(), target.begin(), Add());
    for_each(target.begin(), target.end(), Print());
    cout << endl;
    return 0;
}
0 1 2 3 4 5 6 7 8 9 
5
1   // binary_search的返回值是true/false，表示是否找到该元素
Found greater than five: 6
number of six: 2
num of greater than five: 5
100 101 102 103 104 105 106 107 108 109 106 

代码示例：自定义数据类型Person

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

class Person
{
public:
    string name;
    int age;
    Person(string _name, int _age): name(_name), age(_age) {}
    bool operator == (const Person& input) {
        if (this->age == input.age) {
            return true;
        }
        else {
            return false;
        }
    }
};

class Add
{
public:
    int operator () (const int& val) {return (val + 100);}
};

class GreaterAge
{
public:
    bool operator () (const Person& input) {
        return (input.age > 20);
    }
};

int main(int argc, char const *argv[])
{
    printf(">>>>>自定义数据类型<<<<<<\n");
    vector<Person> person;
    Person p1("kavin", 23);
    Person p2("jack", 12);
    Person p3("lisa", 12);

    person.push_back(p1);
    person.push_back(p2);
    person.push_back(p3);

    Person test("kavin", 23);
    auto it2 = find(person.begin(), person.end(), test);
    if (it2 != person.end()) {
        cout << "Found test: " << it2->name << ", " << it2->age << endl;
    }

    auto it3 = find_if(person.begin(), person.end(), GreaterAge());
    if (it3 != person.end()) {
        cout << "Found age > 20: " << it3->name << ", " << it3->age << endl;
    }


    Person p("test", 12);
    cout << "same age: " << count(person.begin(), person.end(), p) << endl;

    cout << "num of age > 20: " << count_if(person.begin(), person.end(), GreaterAge()) << endl;
    return 0;
}
Found test: kavin, 23
Found age > 20: kavin, 23
same age: 2
num of age > 20: 1

一元谓词

template<typename T>
struct Count
{
    int count;
    Count(int x = 0) : count(x) {}
    void operator () (const T& input) {
        ++count;
        cout << input << " ";
    }
};

int main(int argc, char const *argv[])
{
    vector<int> vi;
    for (size_t i  = 0; i < 10; i++) {
        vi.push_back(i);
    }
    Count<int> res;
    // Count<int>() 是函数对象
    res = for_each(vi.begin(), vi.end(), Count<int>());
    cout << endl;
    cout << res.count << endl;
    return 0;
}
0 1 2 3 4 5 6 7 8 9
10

对vi里的每个元素调用了Count<int>()函数，所以在res内部count++执行了10次，所以最后count = 10