关于algorithm头文件(2)

前言
算法部分主要由头文件<algorithm>，<numeric>和<functional>组成。

一、查找
find、find_if、find_first_of、adjacent_find、search、binary_search、lower_bound、upper_bound、equal_range

// find() 函数，返回迭代器（指针|位置），其指向的是在 [first, last) 区域内查找到的第一个目标元素；如果查找失败，则该迭代器的指向和 last 相同。
int* it = find(a, a+5, 30);    //从普通数组a中查找第一个30的位置。【"it-a"可得下标】
vector<int>::iterator it = find(v.begin(), v.end(), 30);    //从容器v中查找第一个30的位置
 
// find_if()、find_if_not() 函数，根据指定的【查找规则】进行查找，在指定区域内查找第一个符合该函数要求（使函数返回 true）的元素。mycomp()可自定义。
it = find_if(myvector.begin(), myvector.end(), mycomp());
it = find_if_not(myvector.begin(), myvector.end(), mycomp());
 
 
// find_end() 函数，查找范围A中与范围B等价的子范围最后一个子串出现的位置
it = find_end(a.begin(), a.end(), b, b+5, mycomp());
 
// find_first_of() 函数，查找范围A中第一个与范围B中【任一元素】等价的元素的位置
it =find_first_of(a.begin(), a.end(), b, b+5, mycomp2());
vector<char>::reverse_iterator rit;    //逆向迭代器
rit = find_first_of (myvector.rbegin(), myvector.rend(), match, match+3);    //配合逆向迭代器，实现反向查找
 
// adjacent_find() 函数，查找两个相邻（adjacent）的等价（identical）元素
vector<int>::iterator it = adjacent_find(v.begin(), v.end(), mycomp2());
 
// mismatch() 函数，返回两个范围中第一个元素不等价的位置。返回pair对。
p1 = mismatch(l1.begin(), l1.end(), l2.begin(), less_equal<int>());
 
// search() 函数，在范围A中查找第一个与范围B等价的子范围的位置。功能恰好和 find_end() 函数相反，用于在序列 A 中【查找序列 B】 第一次出现的位置。search_n 在给定范围中查找第一个【连续n个元素都等价于给定值】的子范围的位置。
it = search (a.begin(), a.end(), b, b+3, mycomp);
 
// binary_search() 函数，二分查找，判断某个元素是否存在，若元素存在则返回值为1，不存在则返回值为0。
int a[]={1,2,3,5,6,8,9};    //输入一个排好序的数组
cout<<binary_search(a, a+7, 6);    //对数组中的6进行查找。也可以自定义比较规则。
 
/* 默认比较规则是：comp(element, val)：element < val，即所有成立的元素都位于不成立元素的前面。
lower_bound() 函数，用于在指定区域内查找不小于【>=】目标值的第一个元素。
upper_bound() 函数，用于在指定区域内查找  大于【>】目标值的第一个元素。*/
inta[5]={1,2,3,4,5};
int*p =lower_bound(a, a+5, 3, mycomp());    //从 a 数组中找到第一个>=3 的元素
 
// equal_range() 函数，功能完全可以看做是 lower_bound() 和 upper_bound() 函数的合体。
用pair返回一个等于目标值的区间迭代器。
vector<int> v = {3, 1, 4, 2, 5};
sort(v.begin(), v.end());
auto result = equal_range(v.begin(), v.end(), 3);
cout << "Lower Bound of 3 is:"<<*result.first << endl;    //3
cout << "Upper Bound of 3 is:"<<*result.second << endl;    //4
二、排序
sort、stable_sort、partial_sort、is_sorted

// sort()、stable_sort() 函数，使用快速排序算法对普通数组或容器中 [first, last) 范围内的元素进行排序，默认进行【升序】排序。容器类中，sort() 只对 array、vector、deque 这 3 个容器提供支持。
sort(v.begin(), v.begin()+4, greater<int>());
 
// nth_element() 函数，将第n小的数放在第n个位置上，使得其前面的数都比它小，其后面的数都比它大。
nth_element(v.begin(), v.begin()+2, v.end());    //处理第3个数
 
// partial_sort() 函数，部分排序——改变原数据
//以默认的升序排序作为排序规则，将 myvector 中最小的 4 个元素移动到开头位置并排好序
partial_sort(v.begin(), v.begin()+4, v.end());
 
// partial_sort_copy() 函数，部分排序——【不改变】原数据
//以默认的升序排序作为排序规则，将 myvector 中最小的 4 个元素移动到开头位置并排好序
partial_sort_copy(v.begin(), v.end(), b, b+4);
三、替换
replace、replace_if、replace_copy、replace_copy_if

// replace() 函数，指定范围内，用新的值来替换和给定值相匹配的元素。
replace(begin(data), end(data), 10, 99);    //将data中的【全部】10，替换成99
 
// replace_if() 函数，指定范围内，将【满足条件】的元素替换为新的值。
replace_if(begin(password), end(password), [](char ch){return isspace(ch);}, '_');
 
// replace_copy() 函数，和 replace() 做的事是一样的，但它的结果会被保存到另一个序列中，而不会改变原始序列。
replace_copy (begin(a), end(a), back_inserter(b), string{"none"}, string{"0"});
replace_copy (a.begin(), a.end(), b.begin(), "none", "0");
 
四、删除
remove、remove_if、remove_copy、remove_copy_if

// remove() 函数作用：删除具有给定值的元素。是通过将与val相等的元素替换为下一个不相等的元素来完成移除的。remove【不会改变】被“移除”元素的序列的元素个数。函数以迭代器的形式返回最后一个要保留的数据的下一个位置iter。iter!=end()
it = remove(v.begin(), v.end(), 3);
v.erase(it, v.end());    //用于彻底删除元素。
 
int a[]={9,9,7,6,5,4,3,2,10};
auto it = remove(begin(a), end(a), 9);
for(auto i = a; i < it; i++)  cout << *i <<" ";
 
// remove_if() 函数，有条件删除
 
// remove_copy()、remove_copy_if() 函数，将a中的数据复制到b中，但不复制指定的元素。
it = remove_copy(begin(a), end(a), back_inserter(b), 3);
五、复制和合并
copy、copy_n、copy_if、copy_backward、reverse_copy、merge、inplace_merge

// copy() 函数，从源容器复制指定个数的元素到目的容器中。
copy(v1.begin(), v1.end(), back_inserter(l1));
copy(v1.begin(), v1.end(), b.begin());
copy_n(v1.begin(), 5, b.begin());    //指定复制个数
 
// copy_backward() 函数，复制的时候，【从后往前】放，最后一个数据先放入最后一个位置
copy_backward(v1.begin() + 2, v1.begin() + 7, l2.end());
 
// merge() 函数，将 2 个有序序列合并为 1 个有序序列，前提是这 2 个有序序列的排序规则相同。
merge(a, a+5, b, b+6, c.begin(), mycomp2);
 
 
// inplace_merge() 原地合并函数，结果存在同一个数组或容器。
inplace_merge(first, first +5, first +11);    //第2个参数两边的序列都是有序的。
 
// ostream_iterator 打印输出
copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, ", "));    //#include <iterator>
六、交换、反转、移动、旋转
算法部分主要由头文件<algorithm>，<numeric>和<functional>组成。

// swap() 函数，交换两个元素，swap()函数不仅仅支持最简单的(int、double、char)基本数据类型，还支持stl中的所有容器。
string s1 = "abcde";
string s2 = "fghjk";
swap(s1, s2);    //交换字符串s1,s2
swap(s1[0], s1[4]);
 
// swap_ranges() 函数将范围 [first1, last2) 中的元素与存在于从 first2 开始的范围中的元素进行交换。简而言之，我们可以说，swap_ranges() 交换了两个序列的元素，即第一个序列中某个位置的每个元素都被第二个序列中相同位置的元素替换，反之亦然。
swap_ranges(v1.begin(), v1.end(), v2.begin());    //v1、v2的等长度元素互换
 
// reverse() 函数用于反转在[first,last)范围内的顺序，reverse函数没有返回值
reverse(s1.begin(), s1.end());    //反转字符串s1
reverse(&s1[0], &s1[4]);     //真实反转的是s1[0]-s1[3],因为前开后闭
 
reverse(a, a+n);    //反转数组a
 
// 翻转字符数组！！！
char s[] = "abc";
int N = sizeof(s) / sizeof(s[0]);    //数组长度是4不是3，对字符串常量，编译器在最后加’\0’。
reverse(s, s + N - 1);    
 
// rotate() 旋转序列，让指定位置的数据成为第一个数据，其他轮转。返回原第一个数据的新位置
iter = rotate(begin(words), begin(words)+3, end(words));
rotate(v1.begin(), v1.begin() + 4, v1.end());    //v1左移4位
rotate_copy(v2.begin(), v2.begin() + 3, v2.end(), ostream_iterator<int>(cout, ", "));
 
// move() 函数，移动指定区间的数据到新的地址，返回新的【结束地址】
move ( a.begin(), a.begin()+4, b.begin() );
move_backward ( a.begin(), a.begin()+4, b.end() );    //向后移动
 
// unique() 相邻去重函数，可以通过数组的初始地址和结束地址对【已经排序好】的数组元素进行相【邻去重】。
int nums[] = { 1,2,2,3,3,4,4,4,5 };
int* end0 = unique(nums, nums + 9);  //和remove一样，并为真正删除重复元素，而只是放到了末尾
int* p= nums;
while(p!=end0) {
	cout << *p << ' ';
	p++;
}
七、填充、遍历
for_each、fill、fill_n、generate、generate_n、transform

// for_each() 函数，将函数 func 应用于从 ['first', 'last'] 范围内的所有元素。
void func(char c)
{
    cout<<char(c-'a'+'A');
}
int main()
{
    char s[] = "abcdefg";
    for_each (s , end(s)-1, func);
    return 0;
}
 
// fill() 函数，为整个序列填入给定的值。fill_n() 函数为指定个数的元素设置值。
fill(arr.begin(), arr.end(), 65)；
memset(arr, 0, sizeof(arr));    //<cstring>，主要对数组进行赋值，且对int型数组，只能赋值为0和-1
 
// generate() 函数，用于为容器的各个元素赋值，其用法类似于for_each。只不过它的第三个参数必须是lambda函数或者函数，或者函数对象，即均有重载operator()()的类对象。generate_n() 函数对指定个数的元素操作。
generate(arr1.begin(), arr1.begin() + 5, []() {return 5; });
 
// transform() 函数，将函数应用到序列的元素上，并将这个函数返回的值保存到另一个序列中。
transform() 的二元函数必须返回一个值，并且也能够将应用函数后得到的结果保存到另一个序列中。输出序列中的元素类型可以和输入序列中的元素类型不同。
vector<char> v1 = { 'a','b','c' };
vector<int> v2 = { 3,1,4 };
vector<string> result;
 
transform(v1.begin(), v1.end(), v2.begin(), back_inserter(result), [](char a, int b) { return string(b, a); });
// 输出3个a，1个b，4个c
for_each(result.begin(), result.end(), [](const string& s) { cout << s << endl; });
// 二元函数
transform (input1.begin(), input1.end(), input2.begin(), result.begin(), plus<int>());  //#include <functional>   // plus
八、计数、比较、求和、数学
count、cout_if、all_of、any_of、none_of、

max、min、max_element、min_element、abs、accumulate

/* count()、count_if() 函数，在前两个参数指定的范围内，有多少满足指定的第三个参数条件的元素。
   count_if() 会返回可以使作为第三个参数的谓词返回【 true 】的元素个数。
   可用匿名函数作为第三个参数[max_age](int age) { return age > max_age; }    */
count(a, a+8, 10);
count_if( v.begin() ,  v.end(),  func );
 
/* all_of() 算法会返回 true，前提是序列中的【所有元素】都可以使谓词返回 true。
   any_of() 算法会返回 true，前提是序列中的【任意一个元素】都可以使谓词返回 true。
   none_of() 算法会返回 true，前提是序列中【没有元素】可以使谓词返回 true。*/
vector<int> ages{ 22, 19, 46, 75, 54, 19, 27, 66, 61, 33, 22, 19 };
int good_age{ 100 };
cout << (all_of(begin(ages), end(ages), [good_age](int age) { return age < good_age; }) ? "None  " : "Some  ") << good_age <<std::endl; 
 
// 求最大值、最小值
//需导入算法文件头<cmath>
#include<cmath>
//两个数比较
min(a, b, comp);    //取最小值，comp为指定的比较规则，可缺省
max(a, b, comp);
 
//多个数比较，需加 { } 
min({a,b,c,d}, comp);
max({a,b,c,d}, comp);
 
/*用max_element（）及min_element（）函数，求数组最大值、最小值的下标，
二者返回的都是迭代器或指针。
需导入算法文件头<algorithm>*/
#include<algorithm>
 
//取普通数组最小值、最大值的下标——无"*"返回的是指针/迭代器
int a[] = {1,2,3,4,5};
int len = sizeof(a)/sizeof(a[0]);    //求数组中元素的个数
int len = end(a) - begin(a);
 
min_element(a, a+len, comp) - a;  //数组取最小值对应的下标
max_element(a, a+len, comp) - a;
min_element(begin(a), end(a), comp) - a;  //数组取最小值对应的下标
max_element(begin(a), end(a), comp) - a;
 
//取普通数组最小值、最大值（min_element返回的是指针/迭代器，用 '*' 取值）
*min_element(a, a+5, comp);  //数组取最小值
*max_element(a, a+5, comp);
 
//STL容器取最小值、最大值对应的位置下标
min_element(v.begin(), v.end(), comp) - v.begin();  //数组取最小值对应的位置下标
max_element(v.begin(), v.end(), comp) - v.begin();
 
//STL容器取最小值、最大值
*min_element(v.begin(), v.end(), comp);  //数组取最小值
*max_element(v.begin(), v.end(), comp);
 
//__gcd(x,y) 最大公约数(__为两个下划线“_”)
p = __gcd(6, 9);    //如要求最小公倍数，则 q=a*b/p
 
// abs() 绝对值函数，只针对整形。浮点型的绝对值请用<cmath>头文件下的fabs()。
 
int abs(x);    //整数型的绝对值
double fabs(double x);    //浮点型的绝对值<cmath>
 
// accumulate() 累加求和，#include <numeric>
accumulate(iterator beg, iterator end, value0, mycomp);
 
vector<int> arr{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int sum = accumulate(arr.begin(), arr.end(), 1, multiplies<int>());    //初值1 * (1 * 2 * 3 * 4 *... * 10)
//multiplies<int>()为仿函数，必须包含头文件<functional>
 
// equal() 比较函数，如果两个序列的长度相同，并且对应元素都相等，equal() 算法会返回 true。
bool eq2 = equal(v1.begin(), v1.end(), v2.begin(), relationship);
 
// lexicographical_compare() 函数，两个序列按字典序排序。默认小于<
lexicographical_compare(c1.begin(), c1.end(), c2.begin(),  c2.end(), less<int>());
九、分组、排列
partition、is_partitioned、stable_partition、partition_point、partition_copy、next_permutation、prev_permutation、is_permutation

// partition() 函数，根据条件进行分区。
partition(beg, end, condition);    //分区
 
is_partitioned(beg，end，condition);    //判断是否已分区
 
stable_partition(beg, end, condition);    //元素的相对顺序被保留
 
partition_point(beg，end，condition);    //此函数返回一个迭代器，该迭代器指向容器的分区点，即条件不成立的分区范围 [beg，end) 中的第一个元素。只有在容器已经分区时，此函数才能正常工作。
 
partition_copy(beg，end，beg1，beg2，condition); //分区结果分别存到 beg1，beg2
 
/*
next_permutation() 排列函数，得到当前数组范围内的排序的下一个排序；【如果要获得全排列，那么就需要先对数组进行升序排序。】
prev_permutation() 得到当前数组范围内的排序的上一个排序；
is_permutation() 检查一个序列是不是另一个序列的排列，如果是，会返回 true。*/
next_permutation(start, end);
十、仿函数<functional>
//(1)算术仿函数
plus<type>();    //计算两数之和 +
minus<type>();    //两数相减 -
multiplies<type>();    //两数相乘 *
divides<type>();    //两数相除 /
modulus<type>();    //取模运算 %
negate<type>();    //相反数 -
 
//(2)关系仿函数
equal_to<type>();    //是否相等 =
not_equal_to<type>();    //是否不相等 !=
greater<type>();    //大于 >
less<type>();    //小于 <
greater_equal<type>();    //大于等于 >=
less_equal<type>();    //小于等于 <=
 
//(3)逻辑仿函数
logical_and<type>();    //逻辑与 &
logical_or<type>();    //逻辑或 |
logical_not<type>();    //逻辑非 !
十一、数值算法<numeric>
// accumulate() 累加函数，以init为初值，对迭代器给出的值序列做累加，返回累加结果值
int fun(int acc, int num) {
    return acc + num * 3;     // 计算数组中每个元素乘以3
}
accumulate(numbers, numbers + 3, init, fun);
accumulate(numbers, numbers + 3, 100, minus<int>());    //默认为+，可以改为其他函数
 
// adjacent_difference() 相邻差值，对输入序列，计算相邻两项的差值(后一个减前一个元素)，写入到输出序列(result)中。
adjacent_difference(val, val + 7, result, multiplies<int>());    //改为乘法，默认减法
 
//inner_product() 内积函数，计算两个输入序列的内积（点乘、数量积）
int init = 100, series1[] = {10, 20, 30}, series2[] = {1, 2, 3};
inner_product(series1, series1 + 3, series2, init, minus<int>(), divides<int>());
// 100-10/1-20/2-30/3，先op2，再op1
 
// partial_sum() 计算局部累加和(每次都加上前面的所有元素)，计算结果放入result中。
int val[] = {1, 2, 3, 4, 5}, result[5];
partial_sum(val, val + 5, result, myop2);    //每次加入前面所有的元素放入result中，1 3 6 10 15，前缀和
 
// iota(), 向序列中写入以val为初值的连续值序列。
int numbers[10];
iota(numbers, numbers + 10, 100);    //以100为初值， 100 101 102 103 104 105 106 107 108 109