STL算法测一遍（二）Testing All STL Algorithms (Part 2)

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

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

修改序列的算法

copy

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

输入参数：

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

函数行为：

Algorithms That Modify Sequences

copy

Copies elements in a container range to another location.

Input parameters:

1. Begin iterator
2. End iterator
3. Begin iterator of the copy destination

Function behavior:

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

示例代码：

Example code:

// 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. 拷贝结果的起始迭代器

函数行为：

copy_n

Copies n elements from a container to another location

Parameters:

1. Begin iterator
2. Number of elements to copy, n
3. Begin iterator of the copy destination

Function behavior:

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;
}

示例代码：

Example code:

// 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 的一元函数

函数行为：

copy_if

Copies elements in a range that satisfy the condition to the destination

Parameters:

1. Begin iterator
2. End iterator
3. Begin iterator of the copy destination
4. A unary function returning bool

Function behavior:

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;
}

示例代码：

Example code:

// 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. 拷贝结果的起始迭代器

函数行为：

copy_backward

Reverse copy (see the function behavior for details)

Parameters:

1. Begin iterator
2. End iterator
3. Begin iterator of the copy destination

Function behavior:

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

示例代码：

Example code:

// 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. 移动结果的起始迭代器

函数行为：

move

Moves elements; the behavior is similar to copy, except it uses move semantics.

Parameters:

1. Begin iterator
2. End iterator
3. Begin iterator of the move destination

Function behavior:

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

示例代码：

Example code:

// 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

反向移动

函数行为：

move_backward

Reverse move

Function behavior:

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

示例代码：

Example code:

// 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 版本使用了移动语义。

函数行为：

swap

Swaps two elements, or two containers with the same number of elements.

The C++ 11 version uses move semantics.

Function behavior:

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]);
}

示例代码：

Example code:

// 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. 第二个容器的起始迭代器

函数行为：

swap_ranges

Range swap

Parameters:

1. Begin iterator
2. End iterator
3. Begin iterator of the second container

Function behavior:

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

示例代码：

Example code:

// 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

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

函数行为：

iter_swap

Swaps the elements pointed to by two iterators.

Function behavior:

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

示例代码：

Example code:

// 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）

函数行为：

transform 🚩

Changes sequence elements according to some rule. This should be one of the more commonly used algorithms.

Parameters:

1. Begin iterator
2. End iterator
3. Begin iterator of the result
4. A unary or binary function (if it’s a binary function, you also need to pass first2)

Function behavior:

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;
}

示例代码：

Example code:

// 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. 新值

函数行为：

replace

Replace

Parameters:

1. Begin iterator
2. End iterator
3. Old value
4. New value

Function behavior:

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;
    }
}

示例代码：

Example code:

// 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. 新值

函数行为：

replace_if

Conditional replace

Parameters:

1. Begin iterator
2. End iterator
3. Unary condition function
4. New value

Function behavior:

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;
    }
}

示例代码：

Example code:

// 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. 新值

函数行为：

replace_copy

Copy and replace (basically copy and replace merged together 😂)

Parameters:

1. Begin iterator
2. End iterator
3. Copy destination iterator
4. Old value
5. New value

Function behavior:

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;
}

示例代码：

Example code:

// 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. 新值

函数行为：

replace_copy_if

The if version of the previous function

Parameters:

1. Begin iterator
2. End iterator
3. Begin iterator of the copy destination
4. Unary condition function
5. New value

Function behavior:

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;
}

示例代码：

Example code:

// 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. 值

函数行为：

fill

Sets elements in the range to a specified value

Parameters:

1. Begin iterator
2. End iterator
3. Value

Function behavior:

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

示例代码：

Example code:

// 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. 值

函数行为：

fill_n

The specified-count version of the previous function.

Parameters:

1. Begin iterator
2. Count
3. Value

Function behavior:

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
}

示例代码：

Example code:

// 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. 一个返回值是元素值类型的无参函数

函数行为：

generate

fill fills a specified value, while the values filled by this function can be obtained from a custom function.

Parameters:

1. Begin iterator
2. End iterator
3. A no-argument function whose return value type is the element value type

Function behavior:

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

示例代码：

Example code:

// 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. 一个返回值是元素值类型的无参函数

函数行为：

generate_n

The specified-count version of the previous function.

Parameters:

1. Begin iterator
2. Count
3. A no-argument function whose return value type is the element value type

Function behavior:

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

示例代码：

Example code:

// 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. 值

函数行为：

remove🚩

Removes elements with a specified value from the container (looking at this source code, it doesn’t seem very easy to use)

Parameters:

1. Begin iterator
2. End iterator
3. Value

Function behavior:

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;
}

示例代码：

Example code:

// 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. 谓词函数

函数行为：

remove_if

The if version of the previous function

Parameters:

1. Begin iterator
2. End iterator
3. Predicate function

Function behavior:

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;
}

示例代码：

Example code:

// 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. 值

函数行为：

remove_copy

Remove and copy

Parameters:

1. Begin iterator
2. End iterator
3. Copy destination iterator
4. Value

Function behavior:

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;
}

示例代码：

Example code:

// 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. 谓词函数

函数行为：

remove_copy_if

The if version of the previous function

1. Begin iterator
2. End iterator
3. Copy destination iterator
4. Predicate function

Function behavior:

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;
}

示例代码：

Example code:

// 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. 用于相邻元素的比较函数（可选）

函数行为：

unique

Removes consecutive equal elements in the container. The third parameter is optional, which is equivalent to merging unique and unique_if together — I don’t understand why they didn’t just add a unique_if function.

1. Begin iterator
2. End iterator
3. Comparison function for adjacent elements (optional)

Function behavior:

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;
}

示例代码：

Example code:

// 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

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

函数行为：

unique_copy

Deduplicate and copy. Also has two versions.

Function behavior:

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;
}

示例代码：

Example code:

// 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. 终止迭代器

函数行为：

reverse🚩

Reverse — this one is also used a lot.

Parameters:

1. Begin iterator
2. End iterator

Function behavior:

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

示例代码：

Example code:

// 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. 拷贝结果迭代器

函数行为：

reverse_copy

The copy version of the previous function.

Parameters:

1. Begin iterator
2. End iterator
3. Copy destination iterator

Function behavior:

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

示例代码：

Example code:

// 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

向左旋转容器中的元素。

函数行为：

rotate

Rotates the elements in the container to the left.

Function behavior:

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;
    }
}

示例代码：

Example code:

// 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 ，写的挺优雅的。

函数行为：

rotate_copy

The copy version of the previous function

It directly calls copy twice — quite elegant.

Function behavior:

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);
}

示例代码：

Example code:

// 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

随机打乱序列。

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

具体用法看示例代码

函数行为：

random_shuffle

Randomly shuffles the sequence.

There are two versions — one with a specified random function, one without.

See the example code for details

Function behavior:

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)]);
    }
}

示例代码：

Example code:

// 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

和上一个差不多吧

函数行为：

shuffle

Pretty much the same as the previous one.

Function behavior:

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)]);
    }
}

示例代码：

Example code:

// 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;
}