容器算法

<algorithm> 是 c++ 自带的容器算法，提供一系列实用的算法。在谈到容器算法，我们大概率会用到谓词 predicate ，谓词返回的类型是布尔类型 (bool) 可以是 lambda 表达式、函数对象以及其它可调用的对象。

查找

1. find() 查找元素

   find 接受三个参数，第三个参数是值类型， set 、 map 自带 count 函数也能实现这样的功能，返回值 0 表示不存在。为了方便本次连带 find_if 、 find_if_not 、 find_first_of 、 find_end 和 adjacent_find 一起举例。

   vector<int> a{1, 1, 2, 3, 4, 4, 5};
   vector<int> b{5, 6, 6};
   find(a.begin(), a.end(), 3); // 返回的是迭代器，未查找到返回a.end()
   find_if(a.begin(), a.end(), [](auto x){return x != 3;}); //接受一个一元谓词，找到第一个满足条件的元素
   find_if_not(a.begin(), a.end(), [](auto x){return x != 3;}); //接受一个一元谓词，找到第一个不满足条件的元素
   
   // find_first_of找到存在于第一个范围的第二个范围中的第一个元素（可能并不是第二个范围第一个元素）返回迭代器，也支持一个二元谓词。
   vector<int> a{1, 1, 2, 3, 4, 4, 5};
   vector<int> b{6, 5, 6};
   auto it = find_first_of(a.begin(), a.end(), b.begin(), b.end());
   cout << *it << endl; // 返回5
   
   // find_end找到最后一个匹配子序列的位置，返回最后一个子序列开始的迭代器，也支持一个二元谓词
   vector<int> a{1, 1, 2, 3, 1, 4, 1, 2};
   vector<int> b{1, 2};
   auto it = find_end(a.begin(), a.end(), b.begin(), b.end());
   cout << distance(a.begin(), it) << endl; // 6指向第7个元素
   
   // adjcent_find找到两个值邻近的元素，返回指向找到的第一个元素的迭代器，接受一个二元谓词
   vector<int> a{1, 1, 2, 3, 4, 1, 2};
   vector<int> b{1, 2};
   auto it = adjacent_find(a.begin(), a.end());
   auto it = adjacent_find(a.begin(), a.end(), 
       [](auto a, auto b)->bool{return  a + b = 10;});
   cout << *it << endl;
   

去重

1. unique(nums.begin(), nums.end()) 除掉连续相同的值

   unique 函数的作用是删除掉的连续的相同的值,unique还支持传入二元谓词（可以理解为一个参数的函数），会返回一个迭代器 it ，但是并不是 end() ，中间是未指定的值(访问可能会产生未定义行为)。注意不要用 set 和 map ，返回的都是常量迭代器是无法改变的，即其指向的元素无法改变。

   // 无谓词写法
   vector<int> a{1, 1, 2, 3, 4, 4, 5};
   auto it = unique(a.begin(), a.end()); // 此时a为{1, 2, 3, 4, 5}
   for_each(a.begin(), a.end(), [](auto it){cout << it << endl;}); // 输出为{1, 2, 3, 4, 5, 4, 5}
   for_each(a.begin(), it, [](auto it){cout << it << endl;}); // 输出为{1, 2, 3, 4, 5}
   // 有二元谓词
   vector<int> a{1, 1, 2, 3, 4, 4, 5};
   auto it = unique(a.begin(), 
       a.end(), [](auto a, auto b) -> bool{return  a != b;}); // 此时a为{1, 2, 3, 4, 5}，lambda表达式作为一个二元谓词，每次从数组中取两个严肃进行判断，然后删除不相等的元素。
   for_each(a.begin(), a.end(), [](auto it) -> int{cout << it << endl;}); // Error，这是因为unique将返回的迭代器到之后的end()迭代器指向的值删除了，但是空间还在。此时访问，会发生未定义行为。
   for_each(a.begin(), it, [](auto xs){cout << xs << endl;}); // 1，1
   cout << distance(a.begin(), a.end()) << endl; // 7，distance求算距离是7
   

2. unique_copy() 除掉连续相同的值并复制到目标容器

   注意，使用此函数之前先分配空间，再使用 unique_copy 并不进行内存分配，只是赋值给另一个容器，如果访问未赋值部分的容器区域，那么会产生未定义行为。同样，也支持二元谓词，通过二元谓词判定移除连续值。

   vector<int> a{1, 1, 2, 3, 4, 4, 5};
   vector<int> b(7, 0);
   auto it = unique_copy(a.begin(), a.end(), b.begin());
   for_each(b.begin(), it, [](auto xs){cout << xs << endl;}); // out: 1 2 3 4 5
   
   // 二元谓词, 一般不要使用二元谓词与数字直接进行比较，可以使用remove实现
   auto it = unique_copy(a.begin(),
       a.end(), b.begin(), [x](auto a, auto b)
       -> bool{return a == 3;});
   for_each(b.begin(), it, [](auto xs){cout << xs << endl;}); // out: 1 1 2 3，解释值等于3才会进行unique_copy
   
   auto it = unique_copy(a.begin(),
       a.end(), b.begin(), [x](auto a, auto b)
       -> bool{return a == b;});
   for_each(b.begin(), it, [](auto xs){cout << xs << endl;}); // out: 1 2 3 4 5，解释a = b，才会进行复制
   

排序

1. sort() 对容器进行排序

   sort 用于实现容器元素的排序，sort也同样接受二元谓词

   sort(a.begin(), a.end());
   sort(a.begin(), a.end(), greater<>()); // 使用库中自带的greater\less对象
   

迭代器差值

1. distance() 求迭代之间距离

   distance 用于求算两个迭代器之间的差值，只用于同一容器, set ， map ， vector 都可以用。

   distance(c.begin(), c.end());
   

遍历容器

1. for_each() 和 for_each_n 遍历容器每个元素并执行函数规定的操作，第三个参数是一个函数。如果要对迭代器指向的元素修改，那么 set 就是不可以的，因为 set 返回的是常量迭代器。

   array<int, 5> a{1, 2, 3, 4, 5};
   for_each(a.begin(), a.end(), [](int& x){cout<< x; x *= 2;}); // 此时元素值会发生改变，因为捕获的是引用。
   for_each(a.begin(), a.end(), [](auto x) -> void{x *= 2; cout << x;}); // 此时元素值不会发生改变，捕获的是值，会变为副本。
   for_each_n(a.begin, 5, [](auto x) -> void{x *= 2; cout << x;}); // 第二个参数指定操作的数量n, 对n个元素进行操作。
   

复制元素

1. copy() 能够将容器中的元素复制到输出迭代器之后 out iterator

   vector<vector<int>> sx(1);
   // 建议复制前先分配多个空间，避免不必要的扩容
   copy(sx.begin(), sx.end() , sx.begin()); // 可以将[begin, end)之间的元素复制到从begin()开始的位置。这种操作会将原先的元素覆盖一次
   
   // 一个有意思的做法是使用back_inserter指明要进行尾插法，某些支持双向插入的容器也可以转变未尾插容器，省去了一些需要选择插入函数的麻烦。
   // set、map类红黑树容器不存在后插方法，无法进行此类调用，注意
   copy(sx.begin(), sx.end() , back_inserter(sx)); // 负值时会在末尾插入元素
   
   vector<int> a{1, 2, 3};
   set<int> s;
   copy(a.begin(), a.end() , back_inserter(s)); // Error
   
   // 接下来我们考虑一个向vector<vector<int>>复制的问题
   vector<vector<int>> v(1)； // 此时外部vector容量为1，size也是1。说明内部存在一个vector容器元素，但是此时vector[0]的size和capacity都是0，是一个空容器。
   copy(v.begin(), v.end(), back_inserter(v)); // 此时内部空容器是2个
   

2. copy_backward() 能够将容器中元素复制到输出迭代器之前。

   map、set 类也不支持。这个容器算法会覆盖掉输出迭代器之前的元素

   vector<int> a{1, 2, 3, 4, 5, 6};
   set<int> s;
   copy_backward(a.begin(), a.end() , s); // Error
   copy_backward(a.begin(), a.begin() + 3, a.end()); // OK a{1, 2, 3, 1, 2, 3}
   copy_backward(a.begin(), a.begin() + 3, a.begin()); // OK，但是数组不会发生任何改变，相当于复制到begin()迭代器之前没有意义。
   

全排列

next_permutation 提供返回容器的一个全排列，也支持一个二元谓词。

next_permutation(a.begin(), a.end());

取集合

set_intersection 取交集、 set_union 取并集、 set_difference 取单侧差集， set_symmetric_difference 取两侧差集，值得注意的是 set_difference 在输出到结果容器中只会输出第一个容器中的元素（不管第一个容器的元素是否少于第二个容器的元素）。这四个函数都接受一个二元谓词。注意： map 和 set 都无法使用，因为这三个函数底层实现都需要用到自增运算符，而map和set只有常量迭代器不支持这样的操作。应用场景： vector 等容器。

vector<int> a{1, 2, 2, 6, 7, 9};
vector<int> b{1, 2, 5, 8, 10};
vector<int> interResult;
vector<int> unionResult;
vector<int> differenceResult;
vector<int> symmetricResult;
set_intersection(a.begin(), a.end(),b.begin(), b.end(), back_inserter(interResult));
set_union(a.begin(), a.end(),b.begin(), b.end(), back_inserter(unionResult));
set_difference(a.begin(), a.end(),b.begin(), b.end(), back_inserter(differenceResult));
set_symmetric_difference(a.begin(), a.end(),b.begin(), b.end(), back_inserter(symmetricResult));

cout << "intersection:" <<endl;
for_each(interResult.begin(), interResult.end(), [](auto& item){cout << item << ":";});
cout << endl;
cout << "differencesection:" <<endl;
for_each(differenceResult.begin(), differenceResult.end(), [](auto& item){cout << item << ":";});
cout << endl;
cout << "unionsection:" <<endl;
for_each(unionResult.begin(), unionResult.end(), [](auto& item){cout << item << ":";});
cout << endl;
cout << "symmetric_diff_section:" <<endl;
for_each(symmetricDifferenceResult.begin(), symmetricDifferenceResult.end(), [](auto& item){cout << item << ":";});
/* output
* intersection:
* 1:2:
* differencesection:
* 2:6:7:9:
* unionsection:
* 1:2:2:5:6:7:8:9:10:
* symmetric_diff_section: 
* 2:6:7:9:5:8:10 */

搜索

search 搜索串中的子序列， search_n 搜索串中固定数量的连续重复值。 search_n 接受一个二元谓词，两个函数都能够使用 set 和 map 。 search 接受一个 searcher 可调用对象，但是 search_n 对于 set 是没有意义的，因为 set 中不存在重复值

vector<int> a{1,1,1,4};
vector<int> b{1,2};
auto it = search(a.begin(), a.end(),b.begin(), b.end());
auto xs = search_n(a.begin(), a.end(), 3, 1);
int ret = it == a.end()? -1 : 1;
int res = xs == a.end()? -1 : 1;
cout << ret <<endl; // -1; 未找到
cout << res << endl; // 1; 找到了{1，1，1}