STL算法测一遍（二）

注意：这篇文章上次更新于1513天前，文章内容可能已经过时。

This article was last updated1513 days ago, the content may be outdated.

修改序列的算法

copy

将一个容器范围内的元素拷贝到另一个位置。

输入参数：

1. 起始迭代器
2. 终止迭代器
3. 拷贝结果的起始迭代器

函数行为：

template <class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result)
{
    while (first != last)
    {
        *result = *first;
        ++result;
        ++first;
    }
    return result;
}

示例代码：

// copy algorithm example
#include <iostream>  // std::cout
#include <algorithm> // std::copy
#include <vector>    // std::vector

int main()
{
    int myints[] = {10, 20, 30, 40, 50, 60, 70};
    std::vector<int> myvector(7);

    std::copy(myints, myints + 7, myvector.begin());

    std::cout << "myvector contains:";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;

    std::cout << '\n';

    return 0;
}

copy_n

将一个容器内 n 个元素拷贝到另一个位置

参数：

1. 起始迭代器
2. 待拷贝元素个数 n
3. 拷贝结果的起始迭代器

函数行为：

template <class InputIterator, class Size, class OutputIterator>
OutputIterator copy_n(InputIterator first, Size n, OutputIterator result)
{
    while (n > 0)
    {
        *result = *first;
        ++result;
        ++first;
        --n;
    }
    return result;
}

示例代码：

// copy_n algorithm example
#include <iostream>  // std::cout
#include <algorithm> // std::copy
#include <vector>    // std::vector

int main()
{
    int myints[] = {10, 20, 30, 40, 50, 60, 70};
    std::vector<int> myvector;

    myvector.resize(7); // allocate space for 7 elements

    std::copy_n(myints, 7, myvector.begin());

    std::cout << "myvector contains:";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;

    std::cout << '\n';

    return 0;
}

copy_if

拷贝一个范围内满足条件的元素到目标位置

参数：

1. 起始迭代器
2. 终止迭代器
3. 拷贝结果的起始迭代器
4. 返回值是 bool 的一元函数

函数行为：

template <class InputIterator, class OutputIterator, class UnaryPredicate>
OutputIterator copy_if(InputIterator first, InputIterator last,
                       OutputIterator result, UnaryPredicate pred)
{
    while (first != last)
    {
        if (pred(*first))
        {
            *result = *first;
            ++result;
        }
        ++first;
    }
    return result;
}

示例代码：

// copy_if example
#include <iostream>  // std::cout
#include <algorithm> // std::copy_if, std::distance
#include <vector>    // std::vector

int main()
{
    std::vector<int> foo = {25, 15, 5, -5, -15};
    std::vector<int> bar(foo.size());

    // copy only positive numbers:
    auto it = std::copy_if(foo.begin(), foo.end(), bar.begin(), [](int i)
                           { return !(i < 0); });
    bar.resize(std::distance(bar.begin(), it)); // shrink container to new size

    std::cout << "bar contains:";
    for (int &x : bar)
        std::cout << ' ' << x;
    std::cout << '\n';

    return 0;
}

copy_backward

反向拷贝（具体看函数行为）

参数：

1. 起始迭代器
2. 终止迭代器
3. 拷贝结果的起始迭代器

函数行为：

template <class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2 copy_backward(BidirectionalIterator1 first,
                                     BidirectionalIterator1 last,
                                     BidirectionalIterator2 result)
{
    while (last != first)
        *(--result) = *(--last); // 从 last-1 拷贝到 first
    return result;
}

示例代码：

// copy_backward example
#include <iostream>  // std::cout
#include <algorithm> // std::copy_backward
#include <vector>    // std::vector

int main()
{
    std::vector<int> myvector;

    // set some values:
    for (int i = 1; i <= 5; i++)
        myvector.push_back(i * 10); // myvector: 10 20 30 40 50

    myvector.resize(myvector.size() + 3); // allocate space for 3 more elements

    std::copy_backward(myvector.begin(), myvector.begin() + 5, myvector.end());

    std::cout << "myvector contains:";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

move

移动元素，行为可 copy 差不多，只是使用了移动语义。

参数：

1. 起始迭代器
2. 终止迭代器
3. 移动结果的起始迭代器

函数行为：

template <class InputIterator, class OutputIterator>
OutputIterator move(InputIterator first, InputIterator last, OutputIterator result)
{
    while (first != last)
    {
        *result = std::move(*first);
        ++result;
        ++first;
    }
    return result;
}

示例代码：

// move algorithm example
#include <iostream>  // std::cout
#include <algorithm> // std::move (ranges)
#include <utility>   // std::move (objects)
#include <vector>    // std::vector
#include <string>    // std::string

int main()
{
    std::vector<std::string> foo = {"air", "water", "fire", "earth"};
    std::vector<std::string> bar(4);

    // moving ranges:
    std::cout << "Moving ranges...\n";
    std::move(foo.begin(), foo.begin() + 4, bar.begin());

    std::cout << "foo contains " << foo.size() << " elements:";
    std::cout << " (each in an unspecified but valid state)";
    std::cout << '\n';

    std::cout << "bar contains " << bar.size() << " elements:";
    for (std::string &x : bar)
        std::cout << " [" << x << "]";
    std::cout << '\n';

    // moving container:
    std::cout << "Moving container...\n";
    foo = std::move(bar);

    std::cout << "foo contains " << foo.size() << " elements:";
    for (std::string &x : foo)
        std::cout << " [" << x << "]";
    std::cout << '\n';

    std::cout << "bar is in an unspecified but valid state";
    std::cout << '\n';

    return 0;
}

move_backward

反向移动

函数行为：

template <class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2 move_backward(BidirectionalIterator1 first,
                                     BidirectionalIterator1 last,
                                     BidirectionalIterator2 result)
{
    while (last != first)
        *(--result) = std::move(*(--last));
    return result;
}

示例代码：

// move_backward example
#include <iostream>  // std::cout
#include <algorithm> // std::move_backward
#include <string>    // std::string

int main()
{
    std::string elems[10] = {"air", "water", "fire", "earth"};

    // insert new element at the beginning:
    std::move_backward(elems, elems + 4, elems + 5); // 向后移动一格
    elems[0] = "ether";

    std::cout << "elems contains:";
    for (int i = 0; i < 10; ++i)
        std::cout << " [" << elems[i] << "]";
    std::cout << '\n';

    return 0;
}

swap

交换两个元素，或元素数量相同的容器。

C++ 11 版本使用了移动语义。

函数行为：

template <class T>
void swap(T &a, T &b)
{
    T c(std::move(a));
    a = std::move(b);
    b = std::move(c);
}
template <class T, size_t N>
void swap(T (&a)[N], T (&b)[N])
{
    for (size_t i = 0; i < N; ++i)
        swap(a[i], b[i]);
}

示例代码：

// swap algorithm example (C++98)
#include <iostream>  // std::cout
#include <algorithm> // std::swap
#include <vector>    // std::vector

int main()
{

    int x = 10, y = 20; // x:10 y:20
    std::swap(x, y);    // x:20 y:10

    std::vector<int> foo(4, x), bar(6, y); // foo:4x20 bar:6x10
    std::swap(foo, bar);                   // foo:6x10 bar:4x20

    std::cout << "foo contains:";
    for (std::vector<int>::iterator it = foo.begin(); it != foo.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

swap_ranges

范围交换

参数：

1. 起始迭代器
2. 终止迭代器
3. 第二个容器的起始迭代器

函数行为：

template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1,
                             ForwardIterator2 first2)
{
    while (first1 != last1)
    {
        swap(*first1, *first2);
        ++first1;
        ++first2;
    }
    return first2;
}

示例代码：

// swap_ranges example
#include <iostream>  // std::cout
#include <algorithm> // std::swap_ranges
#include <vector>    // std::vector

int main()
{
    std::vector<int> foo(5, 10); // foo: 10 10 10 10 10
    std::vector<int> bar(5, 33); // bar: 33 33 33 33 33

    std::swap_ranges(foo.begin() + 1, foo.end() - 1, bar.begin()); 

    // print out results of swap:
    std::cout << "foo contains:";
    for (std::vector<int>::iterator it = foo.begin(); it != foo.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    std::cout << "bar contains:";
    for (std::vector<int>::iterator it = bar.begin(); it != bar.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

iter_swap

交换两个迭代器所指向的元素。

函数行为：

template <class ForwardIterator1, class ForwardIterator2>
void iter_swap(ForwardIterator1 a, ForwardIterator2 b)
{
    swap(*a, *b);
}

示例代码：

// iter_swap example
#include <iostream>  // std::cout
#include <algorithm> // std::iter_swap
#include <vector>    // std::vector

int main()
{

    int myints[] = {10, 20, 30, 40, 50}; //   myints:  10  20  30  40  50
    std::vector<int> myvector(4, 99);    // myvector:  99  99  99  99

    std::iter_swap(myints, myvector.begin()); //   myints: [99] 20  30  40  50
                                              // myvector: [10] 99  99  99

    std::iter_swap(myints + 3, myvector.begin() + 2); //   myints:  99  20  30 [99] 50
                                                      // myvector:  10  99 [40] 99

    std::cout << "myvector contains:";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

transform 🚩

改变序列元素，根据某个规则。这应该是比较常用的算法了。

参数：

1. 起始迭代器
2. 终止迭代器
3. 结果起始迭代器
4. 一元函数或二元函数（如果是二元函数 还需要传入 first2）

函数行为：

template <class InputIterator, class OutputIterator, class UnaryOperator>
OutputIterator transform(InputIterator first1, InputIterator last1,
                         OutputIterator result, UnaryOperator op)
{
    while (first1 != last1)
    {
        *result = op(*first1); // or: *result=binary_op(*first1,*first2++);
        ++result;
        ++first1;
    }
    return result;
}

示例代码：

// transform algorithm example
#include <iostream>   // std::cout
#include <algorithm>  // std::transform
#include <vector>     // std::vector
#include <functional> // std::plus

int op_increase(int i) { return ++i; }

int main()
{
    std::vector<int> foo;
    std::vector<int> bar;

    // set some values:
    for (int i = 1; i < 6; i++)
        foo.push_back(i * 10); // foo: 10 20 30 40 50

    bar.resize(foo.size()); // allocate space

    std::transform(foo.begin(), foo.end(), bar.begin(), op_increase);
    // bar: 11 21 31 41 51

    // std::plus adds together its two arguments:
    std::transform(foo.begin(), foo.end(), bar.begin(), foo.begin(), std::plus<int>());
    // foo: 21 41 61 81 101

    std::cout << "foo contains:";
    for (std::vector<int>::iterator it = foo.begin(); it != foo.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

replace

替换

参数：

1. 起始迭代器
2. 终止迭代器
3. 旧值
4. 新值

函数行为：

template <class ForwardIterator, class T>
void replace(ForwardIterator first, ForwardIterator last,
             const T &old_value, const T &new_value)
{
    while (first != last)
    {
        if (*first == old_value)
            *first = new_value;
        ++first;
    }
}

示例代码：

// replace algorithm example
#include <iostream>  // std::cout
#include <algorithm> // std::replace
#include <vector>    // std::vector

int main()
{
    int myints[] = {10, 20, 30, 30, 20, 10, 10, 20};
    std::vector<int> myvector(myints, myints + 8); // 10 20 30 30 20 10 10 20

    std::replace(myvector.begin(), myvector.end(), 20, 99); // 10 99 30 30 99 10 10 99

    std::cout << "myvector contains:";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

replace_if

条件替换

参数：

1. 起始迭代器
2. 终止迭代器
3. 一元条件判断函数
4. 新值

函数行为：

template <class ForwardIterator, class UnaryPredicate, class T>
void replace_if(ForwardIterator first, ForwardIterator last,
                UnaryPredicate pred, const T &new_value)
{
    while (first != last)
    {
        if (pred(*first))
            *first = new_value;
        ++first;
    }
}

示例代码：

// replace_if example
#include <iostream>  // std::cout
#include <algorithm> // std::replace_if
#include <vector>    // std::vector

bool IsOdd(int i) { return ((i % 2) == 1); }

int main()
{
    std::vector<int> myvector;

    // set some values:
    for (int i = 1; i < 10; i++)
        myvector.push_back(i); // 1 2 3 4 5 6 7 8 9

    std::replace_if(myvector.begin(), myvector.end(), IsOdd, 0); // 0 2 0 4 0 6 0 8 0

    std::cout << "myvector contains:";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

replace_copy

拷贝并替换（就是把 copy 和 replace 合并了😂）

参数：

1. 起始迭代器
2. 终止迭代器
3. 拷贝结果迭代器
4. 旧值
5. 新值

函数行为：

template <class InputIterator, class OutputIterator, class T>
OutputIterator replace_copy(InputIterator first, InputIterator last,
                            OutputIterator result, const T &old_value, const T &new_value)
{
    while (first != last)
    {
        *result = (*first == old_value) ? new_value : *first;
        ++first;
        ++result;
    }
    return result;
}

示例代码：

// replace_copy example
#include <iostream>  // std::cout
#include <algorithm> // std::replace_copy
#include <vector>    // std::vector

int main()
{
    int myints[] = {10, 20, 30, 30, 20, 10, 10, 20};

    std::vector<int> myvector(8);
    std::replace_copy(myints, myints + 8, myvector.begin(), 20, 99);

    std::cout << "myvector contains:";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

replace_copy_if

上一个函数的 if 版本

参数：

1. 起始迭代器
2. 终止迭代器
3. 拷贝结果的起始迭代器
4. 一元条件判断函数
5. 新值

函数行为：

template <class InputIterator, class OutputIterator, class UnaryPredicate, class T>
OutputIterator replace_copy_if(InputIterator first, InputIterator last,
                               OutputIterator result, UnaryPredicate pred,
                               const T &new_value)
{
    while (first != last)
    {
        *result = (pred(*first)) ? new_value : *first;
        ++first;
        ++result;
    }
    return result;
}

示例代码：

// replace_copy_if example
#include <iostream>  // std::cout
#include <algorithm> // std::replace_copy_if
#include <vector>    // std::vector

bool IsOdd(int i) { return ((i % 2) == 1); }

int main()
{
    std::vector<int> foo, bar;

    // set some values:
    for (int i = 1; i < 10; i++)
        foo.push_back(i); // 1 2 3 4 5 6 7 8 9

    bar.resize(foo.size()); // allocate space
    std::replace_copy_if(foo.begin(), foo.end(), bar.begin(), IsOdd, 0);
    // 0 2 0 4 0 6 0 8 0

    std::cout << "bar contains:";
    for (std::vector<int>::iterator it = bar.begin(); it != bar.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

fill

将范围内的元素设置为指定值

参数：

1. 起始迭代器
2. 终止迭代器
3. 值

函数行为：

template <class ForwardIterator, class T>
void fill(ForwardIterator first, ForwardIterator last, const T &val)
{
    while (first != last)
    {
        *first = val;
        ++first;
    }
}

示例代码：

// fill algorithm example
#include <iostream>  // std::cout
#include <algorithm> // std::fill
#include <vector>    // std::vector

int main()
{
    std::vector<int> myvector(8); // myvector: 0 0 0 0 0 0 0 0

    std::fill(myvector.begin(), myvector.begin() + 4, 5);   // myvector: 5 5 5 5 0 0 0 0
    std::fill(myvector.begin() + 3, myvector.end() - 2, 8); // myvector: 5 5 5 8 8 8 0 0

    std::cout << "myvector contains:";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

fill_n

上一个函数的指定个数版本。

参数：

1. 起始迭代器
2. 个数
3. 值

函数行为：

template <class OutputIterator, class Size, class T>
OutputIterator fill_n(OutputIterator first, Size n, const T &val)
{
    while (n > 0)
    {
        *first = val;
        ++first;
        --n;
    }
    return first; // since C++11
}

示例代码：

// fill_n example
#include <iostream>  // std::cout
#include <algorithm> // std::fill_n
#include <vector>    // std::vector

int main()
{
    std::vector<int> myvector(8, 10); // myvector: 10 10 10 10 10 10 10 10

    std::fill_n(myvector.begin(), 4, 20);     // myvector: 20 20 20 20 10 10 10 10
    std::fill_n(myvector.begin() + 3, 3, 33); // myvector: 20 20 20 33 33 33 10 10

    std::cout << "myvector contains:";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

generate

fill 是填充指定值，这个函数中填充的值可以通过自定义函数获得。

参数：

1. 起始迭代器
2. 终止迭代器
3. 一个返回值是元素值类型的无参函数

函数行为：

template <class ForwardIterator, class Generator>
void generate(ForwardIterator first, ForwardIterator last, Generator gen)
{
    while (first != last)
    {
        *first = gen();
        ++first;
    }
}

示例代码：

// generate algorithm example
#include <iostream>  // std::cout
#include <algorithm> // std::generate
#include <vector>    // std::vector
#include <ctime>     // std::time
#include <cstdlib>   // std::rand, std::srand

// function generator:
int RandomNumber() { return (std::rand() % 100); }

// class generator:
struct c_unique
{
    int current;
    c_unique() { current = 0; }
    int operator()() { return ++current; }
} UniqueNumber;

int main()
{
    std::srand(unsigned(std::time(0)));

    std::vector<int> myvector(8);

    std::generate(myvector.begin(), myvector.end(), RandomNumber);

    std::cout << "myvector contains:";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    std::generate(myvector.begin(), myvector.end(), UniqueNumber);

    std::cout << "myvector contains:";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

generate_n

上一个函数的指定格式版本。

参数：

1. 起始迭代器
2. 个数
3. 一个返回值是元素值类型的无参函数

函数行为：

template <class OutputIterator, class Size, class Generator>
void generate_n(OutputIterator first, Size n, Generator gen)
{
    while (n > 0)
    {
        *first = gen();
        ++first;
        --n;
    }
}

示例代码：

// generate_n example
#include <iostream>  // std::cout
#include <algorithm> // std::generate_n

int current = 0;
int UniqueNumber() { return ++current; }

int main()
{
    int myarray[9];

    std::generate_n(myarray, 9, UniqueNumber);

    std::cout << "myarray contains:";
    for (int i = 0; i < 9; ++i)
        std::cout << ' ' << myarray[i];
    std::cout << '\n';

    return 0;
}

remove🚩

移除容器中指定值的元素（看这源代码 感觉不是很好用啊）

参数：

1. 起始迭代器
2. 终止迭代器
3. 值

函数行为：

template <class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T &val)
{
    ForwardIterator result = first;
    while (first != last)
    {
        if (!(*first == val))
        {
            if (result != first)
                *result = move(*first);
            ++result;
        }
        ++first;
    }
    return result;
}

示例代码：

// remove algorithm example
#include <iostream>  // std::cout
#include <algorithm> // std::remove

int main()
{
    int myints[] = {10, 20, 30, 30, 20, 10, 10, 20}; // 10 20 30 30 20 10 10 20

    // bounds of range:
    int *pbegin = myints;                              // ^
    int *pend = myints + sizeof(myints) / sizeof(int); // ^                       ^

    pend = std::remove(pbegin, pend, 20); // 10 30 30 10 10 ?  ?  ?
                                          // ^              ^
    std::cout << "range contains:";
    for (int *p = pbegin; p != pend; ++p)
        std::cout << ' ' << *p;
    std::cout << '\n';

    return 0;
}

remove_if

上一个函数的 if 版本

参数：

1. 起始迭代器
2. 终止迭代器
3. 谓词函数

函数行为：

template <class ForwardIterator, class UnaryPredicate>
ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,
                          UnaryPredicate pred)
{
    ForwardIterator result = first;
    while (first != last)
    {
        if (!pred(*first))
        {
            if (result != first)
                *result = std::move(*first);
            ++result;
        }
        ++first;
    }
    return result;
}

示例代码：

// remove_if example
#include <iostream>  // std::cout
#include <algorithm> // std::remove_if

bool IsOdd(int i) { return ((i % 2) == 1); }

int main()
{
    int myints[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; // 1 2 3 4 5 6 7 8 9

    // bounds of range:
    int *pbegin = myints;                              // ^
    int *pend = myints + sizeof(myints) / sizeof(int); // ^                 ^

    pend = std::remove_if(pbegin, pend, IsOdd); // 2 4 6 8 ? ? ? ? ?
                                                // ^       ^
    std::cout << "the range contains:";
    for (int *p = pbegin; p != pend; ++p)
        std::cout << ' ' << *p;
    std::cout << '\n';

    return 0;
}

remove_copy

移除并拷贝

参数：

1. 起始迭代器
2. 终止迭代器
3. 拷贝结果迭代器
4. 值

函数行为：

template <class InputIterator, class OutputIterator, class T>
OutputIterator remove_copy(InputIterator first, InputIterator last,
                           OutputIterator result, const T &val)
{
    while (first != last)
    {
        if (!(*first == val))
        {
            *result = *first;
            ++result;
        }
        ++first;
    }
    return result;
}

示例代码：

// remove_copy example
#include <iostream>  // std::cout
#include <algorithm> // std::remove_copy
#include <vector>    // std::vector

int main()
{
    int myints[] = {10, 20, 30, 30, 20, 10, 10, 20}; // 10 20 30 30 20 10 10 20
    std::vector<int> myvector(8);

    std::remove_copy(myints, myints + 8, myvector.begin(), 20); // 10 30 30 10 10 0 0 0

    std::cout << "myvector contains:";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

remove_copy_if

上一个函数的 if 版本

1. 起始迭代器
2. 终止迭代器
3. 拷贝结果迭代器
4. 谓词函数

函数行为：

template <class InputIterator, class OutputIterator, class UnaryPredicate>
OutputIterator remove_copy_if(InputIterator first, InputIterator last,
                              OutputIterator result, UnaryPredicate pred)
{
    while (first != last)
    {
        if (!pred(*first))
        {
            *result = *first;
            ++result;
        }
        ++first;
    }
    return result;
}

示例代码：

// remove_copy_if example
#include <iostream>  // std::cout
#include <algorithm> // std::remove_copy_if
#include <vector>    // std::vector

bool IsOdd(int i) { return ((i % 2) == 1); }

int main()
{
    int myints[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::vector<int> myvector(9);

    std::remove_copy_if(myints, myints + 9, myvector.begin(), IsOdd);

    std::cout << "myvector contains:";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

unique

对容器中连续相等的元素进行去重。其中第三个参数可选，相当于 unique 和 unique_if 合在一起了，不明白为什么不加一个 unique_if 函数。

1. 起始迭代器
2. 终止迭代器
3. 用于相邻元素的比较函数（可选）

函数行为：

template <class ForwardIterator>
ForwardIterator unique(ForwardIterator first, ForwardIterator last)
{
    if (first == last)
        return last;

    ForwardIterator result = first;
    while (++first != last)
    {
        if (!(*result == *first)) // or: if (!pred(*result,*first)) for version (2)
            *(++result) = *first;
    }
    return ++result;
}

示例代码：

// unique algorithm example
#include <iostream>  // std::cout
#include <algorithm> // std::unique, std::distance
#include <vector>    // std::vector

bool myfunction(int i, int j)
{
    return (i == j);
}

int main()
{
    int myints[] = {10, 20, 20, 20, 30, 30, 20, 20, 10}; // 10 20 20 20 30 30 20 20 10
    std::vector<int> myvector(myints, myints + 9);

    // using default comparison:
    std::vector<int>::iterator it;
    it = std::unique(myvector.begin(), myvector.end()); // 10 20 30 20 10 ?  ?  ?  ?
                                                        //                ^

    myvector.resize(std::distance(myvector.begin(), it)); // 10 20 30 20 10

    // using predicate comparison:
    std::unique(myvector.begin(), myvector.end(), myfunction); // (no changes)

    // print out content:
    std::cout << "myvector contains:";
    for (it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

unique_copy

去重并拷贝。也是两个版本。

函数行为：

template <class InputIterator, class OutputIterator>
OutputIterator unique_copy(InputIterator first, InputIterator last,
                           OutputIterator result)
{
    if (first == last)
        return result;

    *result = *first;
    while (++first != last)
    {
        typename iterator_traits<InputIterator>::value_type val = *first;
        if (!(*result == val)) // or: if (!pred(*result,val)) for version (2)
            *(++result) = val;
    }
    return ++result;
}

示例代码：

// unique_copy example
#include <iostream>  // std::cout
#include <algorithm> // std::unique_copy, std::sort, std::distance
#include <vector>    // std::vector

bool myfunction(int i, int j)
{
    return (i == j);
}

int main()
{
    int myints[] = {10, 20, 20, 20, 30, 30, 20, 20, 10};
    std::vector<int> myvector(9); // 0  0  0  0  0  0  0  0  0

    // using default comparison:
    std::vector<int>::iterator it;
    it = std::unique_copy(myints, myints + 9, myvector.begin()); // 10 20 30 20 10 0  0  0  0
                                                                 //                ^

    std::sort(myvector.begin(), it); // 10 10 20 20 30 0  0  0  0
                                     //                ^

    // using predicate comparison:
    it = std::unique_copy(myvector.begin(), it, myvector.begin(), myfunction);
    // 10 20 30 20 30 0  0  0  0
    //          ^

    myvector.resize(std::distance(myvector.begin(), it)); // 10 20 30

    // print out content:
    std::cout << "myvector contains:";
    for (it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

reverse🚩

反转，这个用的也很多。

参数：

1. 起始迭代器
2. 终止迭代器

函数行为：

template <class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last)
{
    while ((first != last) && (first != --last))
    {
        std::iter_swap(first, last);
        ++first;
    }
}

示例代码：

// reverse algorithm example
#include <iostream>  // std::cout
#include <algorithm> // std::reverse
#include <vector>    // std::vector

int main()
{
    std::vector<int> myvector;

    // set some values:
    for (int i = 1; i < 10; ++i)
        myvector.push_back(i); // 1 2 3 4 5 6 7 8 9

    std::reverse(myvector.begin(), myvector.end()); // 9 8 7 6 5 4 3 2 1

    // print out content:
    std::cout << "myvector contains:";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

reverse_copy

上一个函数的 copy 版本。

参数：

1. 起始迭代器
2. 终止迭代器
3. 拷贝结果迭代器

函数行为：

template <class BidirectionalIterator, class OutputIterator>
OutputIterator reverse_copy(BidirectionalIterator first,
                            BidirectionalIterator last, OutputIterator result)
{
    while (first != last)
    {
        --last;
        *result = *last;
        ++result;
    }
    return result;
}

示例代码：

// reverse_copy example
#include <iostream>  // std::cout
#include <algorithm> // std::reverse_copy
#include <vector>    // std::vector

int main()
{
    int myints[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::vector<int> myvector;

    myvector.resize(9); // allocate space

    std::reverse_copy(myints, myints + 9, myvector.begin());

    // print out content:
    std::cout << "myvector contains:";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;

    std::cout << '\n';

    return 0;
}

rotate

向左旋转容器中的元素。

函数行为：

template <class ForwardIterator>
void rotate(ForwardIterator first, ForwardIterator middle,
            ForwardIterator last)
{
    ForwardIterator next = middle;
    while (first != next)
    {
        swap(*first++, *next++);
        if (next == last)
            next = middle;
        else if (first == middle)
            middle = next;
    }
}

示例代码：

// rotate algorithm example
#include <iostream>  // std::cout
#include <algorithm> // std::rotate
#include <vector>    // std::vector

int main()
{
    std::vector<int> myvector;

    // set some values:
    for (int i = 1; i < 10; ++i)
        myvector.push_back(i); // 1 2 3 4 5 6 7 8 9

    std::rotate(myvector.begin(), myvector.begin() + 3, myvector.end());
    // 4 5 6 7 8 9 1 2 3
    // print out content:
    std::cout << "myvector contains:";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

rotate_copy

上一个函数的 copy 版本

直接调用两个 copy ，写的挺优雅的。

函数行为：

template <class ForwardIterator, class OutputIterator>
OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle,
                           ForwardIterator last, OutputIterator result)
{
    result = std::copy(middle, last, result);
    return std::copy(first, middle, result);
}

示例代码：

// rotate_copy algorithm example
#include <iostream>  // std::cout
#include <algorithm> // std::rotate_copy
#include <vector>    // std::vector

int main()
{
    int myints[] = {10, 20, 30, 40, 50, 60, 70};

    std::vector<int> myvector(7);

    std::rotate_copy(myints, myints + 3, myints + 7, myvector.begin());

    // print out content:
    std::cout << "myvector contains:";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

random_shuffle

随机打乱序列。

有两个版本 ，一个是指定随机函数的，一个不指定。

具体用法看示例代码

函数行为：

template <class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
                    RandomNumberGenerator &gen)
{
    iterator_traits<RandomAccessIterator>::difference_type i, n;
    n = (last - first);
    for (i = n - 1; i > 0; --i)
    {
        swap(first[i], first[gen(i + 1)]);
    }
}

示例代码：

// random_shuffle example
#include <iostream>  // std::cout
#include <algorithm> // std::random_shuffle
#include <vector>    // std::vector
#include <ctime>     // std::time
#include <cstdlib>   // std::rand, std::srand

// random generator function:
int myrandom(int i) { return std::rand() % i; }

int main()
{
    std::srand(unsigned(std::time(0)));
    std::vector<int> myvector;

    // set some values:
    for (int i = 1; i < 10; ++i)
        myvector.push_back(i); // 1 2 3 4 5 6 7 8 9

    // using built-in random generator:
    std::random_shuffle(myvector.begin(), myvector.end());

    // using myrandom:
    std::random_shuffle(myvector.begin(), myvector.end(), myrandom);

    // print out content:
    std::cout << "myvector contains:";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;

    std::cout << '\n';

    return 0;
}

shuffle

和上一个差不多吧

函数行为：

template <class RandomAccessIterator, class URNG>
void shuffle(RandomAccessIterator first, RandomAccessIterator last, URNG &&g)
{
    for (auto i = (last - first) - 1; i > 0; --i)
    {
        std::uniform_int_distribution<decltype(i)> d(0, i);
        swap(first[i], first[d(g)]);
    }
}

示例代码：

// shuffle algorithm example
#include <iostream>  // std::cout
#include <algorithm> // std::shuffle
#include <array>     // std::array
#include <random>    // std::default_random_engine
#include <chrono>    // std::chrono::system_clock

int main()
{
    std::array<int, 5> foo{1, 2, 3, 4, 5};

    // obtain a time-based seed:
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();

    shuffle(foo.begin(), foo.end(), std::default_random_engine(seed));

    std::cout << "shuffled elements:";
    for (int &x : foo)
        std::cout << ' ' << x;
    std::cout << '\n';

    return 0;
}