《重学C++》9. C++进阶编程（一）容器、仿函数、算法

发表于 更新于 阅读次数： 本文字数： 4k 阅读时长 ≈ 4 分钟

STL标准库包括：

  • 容器
  • 适配器
  • 仿函数
  • 算法
  • 迭代器
  • 空间置配器

1. 容器

容器分为两种：

  • 顺序容器（sequence containers）
    顺序容器中的元素都是有一定顺序、可排序的，其顺序依赖于值。顺序容器包括vector、deque、list、forward_list、string、array。
  • 关联容器（associative containers）
    关联容器中的元素不可排序，全部根据键（key）的值按照某种顺序存储。set元素只有键（key），map有还值（value），元素以<key,value>存储在map中。

2. 仿函数

仿函数其实就是普通的类，但是其对运算符()经过重载，使类具有了函数的作用。

1
2
3
4
5
6
struct min
{
	int operator()(int a, int b) {
		return  a < b ? a : b;
	}
};

如，使用min(3,5)即可获得其中更小的数值3。也可以通过泛型，使仿函数支持多种类型。

3. 算法

算法主要在、、头文件中，分为：

  • 可变序列算法：可以修改操作的容器内容的算法；
  • 非可变序列算法：不可以直接修改操作的容器内容的算法；
  • 排序算法：对序列进行排序、合并、搜索，以及在有序序列上的集合操作；
  • 数值算法：对容器内容进行数值计算。

transform函数：

有多种重载形式，对一个或两个范围的元素按顺序应用指定的函数操作，并将结果存储在从result开始的范围内。类似于for_each操作

//接收一个范围的元素（模板的声明已忽略）
OutputIterator transform (InputIterator first1, InputIterator last1, OutputIterator result, UnaryOperation op);
//接收两个范围的元素（模板的声明已忽略）
OutputIterator transform (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperation binary_op);

std::transform
http://www.cplusplus.com/reference/algorithm/transform/?kw=transform

lambda函数（匿名函数）：

格式为：

[函数对象参数] (操作符重载函数参数) mutable 或 exception 声明 -> 返回值类型 {函数体}

其中**[函数对象参数]**中的内容为外部变量， **(操作符重载函数参数) 中内容为该匿名函数的参数，{函数体}**中的内容为函数语句。

示例代码如下：

1
2
3
4
5
6
7
int ones[] = { 1,2,3,4,5 };
int twos[] = { 10,20,30,40,50 };
int result[5];
//transform
transform(ones, ones + 5,twos, results, std::plus<int>());
//lambda函数
for_each(results, results + 5, [](int a)->void {cout << a << " "; });

find函数

template <class InputIterator, class T> 
InputIterator find (InputIterator first, InputIterator last, const T& val);

Returns an iterator to the first element in the range [first,last) that compares equal to val. If no such element is found, the function returns last.
返回范围[first,last]中与val比较的第一个元素的迭代器。如果没有找到这样的元素，则返回last。

std::find
http://www.cplusplus.com/reference/algorithm/find/?kw=find

count函数和count_if函数

count函数：统计某元素出现的个数
count_if函数：统计满足某条件的所有元素个数

1
2
3
4
5
6
7
int arr[] = { 1, 2, 2, 3, 3, 3, 4, 5, 7, 8, 8, 8, 9 };
cout << count(arr, arr + sizeof(arr) / sizeof(arr[0]), 7);//统计等于7的元素个数
cout << endl;
cout << count_if(arr, arr + sizeof(arr) / sizeof(arr[0]), bind2nd(less<int>(), 7)); //统计小于7的元素个数
cout << endl;
cout << count_if(arr, arr + sizeof(arr) / sizeof(arr[0]), bind1st(less<int>(), 7)); //统计小于7的元素个数
cout << endl;

首先count_if前两个参数指定了一个序列，将其中每个元素放入第三个参数指定的条件中判断，如果满足则计数。第三个参数bind2nd(less(), 7)指定了count_if中的条件（如果元素满足条件，该函数返回值为true）。
其次less()是一个仿函数，表明了对序列中所有元素和7进行”<“操作。假设元素为x，为了确定进行x<7还是7<x的操作，需要使用(const _Fn& _Func, const _Ty& _Right)，该函数指定了将第二个参数_Right放在运算符的右边，也就是进行x<7的判断。

std::count
http://www.cplusplus.com/reference/algorithm/count/?kw=count
std::count_if
http://www.cplusplus.com/reference/algorithm/count_if/?kw=count_if

bind1st函数和bind2nd函数

bind1st和bind2nd函数用于将一个二元算子（binary functor，bf）转换成一元算子（unary functor，uf）。为了达到这个目的，它们需要两个参数：要转换的bf和一个值（v）。
可能这么解释以后大家还不是很清楚，那么就说点白话吧。我们在做比较的时候所写的表达式像 x > k ，x < k，这里的k是一个参数表示你程序里面的表达式要和k值去比较。上面这两个表达式对应的应该是bind2nd ，简单的理解就是把k作为比较表达式的第二个参数。如果使用bind1st则对应的表达式是 k > x，k < x，也就是把k作为比较表达式的第一个参数。

bind1st bind2nd的使用
https://blog.csdn.net/simahao/article/details/405455

std::bind1st
http://www.cplusplus.com/reference/functional/bind1st/?kw=bind1st
std::bind2nd
http://www.cplusplus.com/reference/functional/bind2nd/?kw=bind2nd

binary_search函数和search函数

binary_search：如果元素出现在 [first,last) 中，那么返回true，反之返回false。
search：在[first1,last1)范围内搜索[first2,last2)定义的序列的第一个匹配项，并返回其第一个元素的迭代器，如果没有匹配项，则返回last1。

1
2
3
cout << binary_search(arr, arr + sizeof(arr) / sizeof(arr[0]), 8); 
int arr2[] = { 7,8,8,8 };
cout << search(arr, arr + sizeof(arr) / sizeof(arr[0]), arr2,arr2+4);//输出第一个元素的地址

std::binary_search
http://www.cplusplus.com/reference/algorithm/binary_search/?kw=binary_search
std::search
http://www.cplusplus.com/reference/algorithm/search/?kw=search

next_permutation函数和prev_permutation函数

next_permutation：将range [first,last)中的元素重新排列为下一个更大的序列。
prev_permutation：将range [first,last)中的元素重新排列为上一个序列。
（要想输出全排列，需要用循环输出每一个下个序列）
需要注意：next和prev分别要求序列中的元素递增和递减排列。使用STL库一定要学习正确的使用方法。

next_permutation
http://www.cplusplus.com/reference/algorithm/next_permutation/?kw=next_permutation