C++ 11 STL算法
STL算法部分主要由头文件,,组成.要使用 STL中的算法函数必须包含头文件,对于数值算法须包含,中则定义了一些模板类,用来声明函数对象.
STL中算法大致分为四类:
1、非可变序列算法:指不直接修改其所操作的容器内容的算法.
2、可变序列算法:指可以修改它们所操作的容器内容的算法.
3、排序算法:包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作.
4、数值算法:对容器内容进行数值计算.
<一>查找算法(13个)：判断容器中是否包含某个值
**adjacent_find **:在 iterator 对标志的元素范围内,查找一对相邻的重复元素,如果找到返回一个 ForwardIterator,指向这对元素的第一个元素.否则返回 last .重载版本使用输入的二元操作符代替相等的判断.
>参数:first
>
> :last
>
>返回:forwardItr
>
>template
>
>forwardItr adjacent_find(forwardItr first, forwardItr last);
>
>参数:first
>
> :last
>
> :op
>
>返回:forwardItr
>
>template<class forwardItr, class binaryPredicate>
>
>forwardItr adjacent_find(forwardItr first, forwardItr last, binaryPredicate op);
```c++
#include
#include
#include
#include
#include
using namespace std;
//x,y为依次相邻的两个元素
bool isequal(int x,int y)
{
return x/2==y;
}
int main()
{
vector vec ={12,22,11,33,33,43};
auto pos1 = adjacent_find(vec.begin(),vec.end());
cout<<*pos1<<endl; // 输出33
auto pos2 = adjacent_find(vec.begin(),vec.end(),isequal);
cout<<*pos2<<endl; // 输出22
return 0;
}
```
**search **:在一个序列中搜索与另一序列匹配的子序列,找到则返回第一次出现子序列的位置,否则返回last1.重载版本使用自定义的比较操作.
//search是在一个集合中搜索另一个子集，find只搜索单个元素
参数:first1
:last1
:first2
:last2
返回：forwardItr1
template <class forwardItr1, class forwardItr2>
forwardItr1 search(forwardItr1 first1, forwardItr1 last1,forwardItr2 first2,forwardItr2 last2);
参数:first1
:last1
:first2
:last2
:op
返回：forwardItr1
template <class forwardItr1, class forwardItr2,class binaryPredicate>
forwardItr1 search(forwardItr1 first1, forwardItr1 last1,forwardItr2 first2,forwardItr2 last2,binaryPredicate op);
**search_n **:在指定范围内查找 value 出现 n 次的子序列.找到则返回第一次出现的位置，找不到则返回last,重载版本使用自定义的比较操作.
参数:first
:last
:count
:value
返回：forwardItr
template <class forwardItr, class size,class Type>
forwardItr search_n(forwardItr first, forwardItr last,size count,const Type& value);
参数:first
:last
:count
:value
:op
返回：forwardItr
template <class forwardItr, class size,class Type,class binaryPredicate>
forwardItr search_n(forwardItr first, forwardItr last,size count,const Type& value,binaryPredicate op);
```c++
vector vec ={12,22,33,33,11,33,18,34,43};
vector vec2={22,33,33};
//按严格匹配vec2是否是vec子集，是则返回vec2在vec中的首个位置，find函数只能找一个
auto it = search(vec.begin(),vec.end(),vec2.begin(),vec2.end());
cout<<*it<<endl; //输出22
//寻找首次连续出现2次33的位置
auto it2 = search_n(vec.begin(),vec.end(),2,33);
cout<<*it2<<endl; //输出33，index==2
//寻找首次连续出现2次大于33的位置
auto it3=search_n(vec.begin(),vec.end(),2,33,[](int i,int j){return i>j;});
cout<<*it3<<endl; //输出34
return 0;
```
**binary_search **:在有序序列中查找 value ,如果找到返回 true .重载的版本使用指定的比较函数对象或者函数指针来判断相等.
参数:first
:last
:searchValue
返回：bool
template<class forwardItr,class Type>
bool binary_search(forwardItr first,forwardItr last,const Type& searchValue);
参数:first
:last
:searchValue
:op
返回：bool
template<class forwardItr,class Type,class compare>
bool binary_search(forwardItr first, forwardItr last, const Type& searchValue,compare op);
```c++
#include "stdafx.h"
#include
#include
#include
#include
#include
#include
#include
bool equal(std::string str1, std::string str2)
{
//将字符串转换为大写
transform(str1.begin(), str1.end(), str1.begin(), ::toupper);
transform(str2.begin(), str2.end(), str2.begin(), ::toupper);
return str1 == str2 ? true : false;
}
/* C++ 源码
template<class ForwardIt, class T, class Compare>
bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
first = std::lower_bound(first, last, value, comp);
return (!(first == last) && !(comp(value, *first)));
}
*/
bool compare(int num1, int num2) //num1对应value
{
return num1>num2;
}
int main()
{
{
std::vector<std::string> vec1 = { "123", "789", "789", "Abc", "abc" };
std::vector<std::string> vec2 = { "789", "Abc" };
auto result1 = search(vec1.begin(), vec1.end(), vec2.begin(), vec2.end());
if (result1 != vec1.end())
{
std::cout << *result1 << std::endl; //输出:789
} else {
std::cout << "no found" << std::endl;
}
//调用自定义的equal函数将字符串转换为大写在比较
auto result2 = search(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), equal);
if (result2 != vec1.end())
{
std::cout << *result2 << std::endl; //输出:789
} else {
std::cout << "no found" << std::endl;
}
auto result3 = search_n(vec1.begin(), vec1.end(), 2, "789");
if (result3 != vec1.end())
{
std::cout << *result3 << std::endl; //输出:789
} else {
std::cout << "no found" << std::endl;
}
auto result4 = search_n(vec1.begin(), vec1.end(), 2, "abc", equal);
if (result4 != vec1.end())
{
std::cout << *result4 << std::endl; //输出:Abc
} else {
std::cout << "no found" << std::endl;
}
auto result5 = binary_search(vec1.begin(), vec1.end(), "432");
if (result5)
{
std::cout << "found" << std::endl;
} else {
std::cout << "no found" << std::endl; //输出no found
}
//等效写法：
// auto predicate = [](int a, int b)
// {
// return a > b;
// };
//auto result6 = binary_search(vec3.begin(), vec3.end(), 43, predicate);
std::vector vec3 = { 12, 44, 45, 64, 66 };
auto result6 = binary_search(vec3.begin(), vec3.end(), 44, compare); //在数组中以二分法检索的方式查找，在数组中查找到indx元素并且比较该元素数组前面是否拥有小于该元素的值如果有则为假，无则为真。若在数组中查不到indx元素则返回值也为假。
std::cout << "查询元素之前是否有小于44的值:" << result6<<std::endl;
getchar();
return 0;
}
}
```
**find **:find算法用于查找等于某值的元素.它在迭代器区间[first , last)上查找等于value值的元素,如果迭代器iter所指的元素满足 *iter == value ,则返回迭代器iter,未找则返回last
参数:first
:last
:searchValue
返回:inputItr 如果迭代器iter所指的元素满足 *iter == value ,则返回迭代器iter,未找则返回last
template <class inputItr,class size,class Type>
inputItr find(inputItr first, inputItr last, const Type& searchValue);
**find_if **:利用返回布尔值的谓词判断pred,检查迭代器区间[first, last)上的每一个元素,如果迭代器iter满足pred(*iter) == true,表示找到元素并返回迭代器值iter；未找到元素,则返回last
参数:first
:last
:op
返回:inputItr 迭代器iter满足pred(*iter) == true,表示找到元素并返回迭代器值iter；未找到元素,则返回last
template <class inputItr, class unaryPredicate>
inputItr find_if(inputItr first, inputItr last, UnaryPredicate op);
**find_end **:返回区间 [_First, _Last)中和区间[_First2, _Last2)完全匹配的最后一个子区间内的第一元素位置，子区间的元素必须完全等于[_First2, _Last2)的元素
在一个序列中搜索出最后一个与另一序列匹配的子序列.有如下两个函数原型,在迭代器区间[first1, last1)中搜索出与迭代器区间[first2, last2)元素匹配的子序列,返回首元素的迭代器或last1
//[first2,last2)被看做一个原子,在first1中必须满足元素数量和first2相同并且连续出现才表示找到，而search被搜索的元素在first1中可以不连续**(目前发现search也要连续)**
参数:first1
:last1
:first2
:last2
返回:forwardItr1 在迭代器区间[first1, last1)中搜索出与迭代器区间[first2, last2)元素匹配的子序列,找到则返回首元素的迭代器未找到则返回last1
template <class forwardItr1,class forwardItr2>
forwardItr1 find_end(forwardItr1 first1, forwardItr1 last1,forwardItr2 first2,forwardItr2 last2);
参数:first1
:last1
:first2
:last2
:op
返回:forwardItr1 在迭代器区间[first1, last1)中搜索出与迭代器区间[first2, last2)元素匹配的子序列,返回首元素的迭代器或last1
template <class forwardItr1,class forwardItr2,class binaryPredicate>
forwardItr1 find_end(forwardItr1 first1, forwardItr1 last1,forwardItr2 first2,forwardItr2 last2,binaryPredicate op);
**find_first_of **:用于查找位于某个范围之内的元素.它有两个使用原型,均在迭代器区间[first1, last1)上查找元素*i,使得迭代器区间[first2, last2)有某个元素*j,满足*i ==*j或满足二元谓词函数comp(*i, *j)==true的条件.元素找到则返回迭代器i,否则返回last1
//这里和find_end不一样，[first2,last2)被看作可以拆开的集合，和search有点像
参数:first1
:last1
:first2
:last2
返回:forwardItr1 元素找到则返回迭代器i,否则返回last1
template <class forwardItr1,class forwardItr2>
forwardItr1 find_first_of(forwardItr1 first1, forwardItr1 last1,forwardItr2 first2,forwardItr2 last2);
参数:first1
:last1
:first2
:last2
:op
返回:forwardItr1 元素找到则返回迭代器i,否则返回last1
template <class forwardItr1,class forwardItr2,class binaryPredicate>
forwardItr1 find_first_of(forwardItr1 first1, forwardItr1 last1,forwardItr2 first2,forwardItr2 last2,binaryPredicate op)
```c++
#include
#include
#include
#include
#include
#include
#include
bool find_func (int i) {
return ((i%2)==1);
}
int main()
{
std::vector vec1 = { 82, 32, 11, 33, 32，11，33, 43 };
std::vector vec2 = { 32, 11 };
std::vector vec3 = { 32, 33 };
auto result1 = find(vec1.begin(), vec1.end(), 33);
std::cout << *result1 << " " << result1 - vec1.begin() << std::endl;//输出 33 3
auto resutl2 = find_if(vec1.begin(), vec1.end(), find_func);
std::cout << *resutl2 << " " << resutl2 - vec1.begin() << std::endl;//输出 11 2
auto result3 = find_end(vec1.begin(), vec1.end(), vec2.begin(), vec2.end());
if (result3 != vec1.end())
{
std::cout << *result3 << " " << result3 - vec1.begin() << std::endl;//输出 32 4
}
auto result4 = find_first_of(vec1.begin(), vec1.end(), vec3.begin(), vec3.end());
if (result4 != vec1.end())
{
std::cout << *result4 << " " << result4 - vec1.begin() << std::endl;//输出 32 1
}
getchar();
return 0;
}
```
**count **:利用等于操作符,把[first,last)范围内的元素与value进行比较,并返回相等元素的个数.
参数:first
:last
:value
返回:满足条件元素的个数
template <class inputItr,class Type>
iterator_traits::difference_type count(inputItr first,inputItr last,const Type& value);
**count_if **:统计容器指定范围[first,last)内满足op条件元素的个数.
参数:first
:last
:op
返回:满足条件元素的个数
template<class InputIterator, class Predicate>
typename iterator_traits::difference_type count_if( InputIterator _First, InputIterator _Last, Predicate _Pred );
```c++
#include
#include
#include
#include
#include
#include
#include
bool greater10(int num)
{
return num % 2 ? true : false;
}
int main()
{
{
std::vector arr = { 12, 43, 23, 65, 34, 23, 55, 56 ,3, 34 };
auto num1 = count(arr.begin(), arr.end(), 34);
std::cout << num1 << std::endl; //2
std::cout << "arr.begin() + 8:" << *(arr.begin() + 8) << std::endl; //3
auto num2 = count_if(arr.begin(), arr.end(), greater10);
std::cout << num2 << std::endl; //6
getchar();
return 0;
}
}
```
**equal_range **:equal_range是C++ STL中的一种二分查找的算法,试图在已排序的[first,last)中寻找value,它返回一对迭代器i和j,其中i是在不破坏次序的前提下,value可插入的第一个位置(亦即lower_bound),j则是在不破坏次序的前提下,value可插入的最后一个位置(亦即upper_bound),因此,[i,j)内的每个元素都等同于value,而且[i,j)是[first,last)之中符合此一性质的最大子区间
参数:first
:last
:val
返回:返回一个pair的键值对,内容为：first:value可插入的第一个位置(亦即lower_bound)second:value可插入的最后一个位置(亦即upper_bound)
template<class ForwardIterator, class Type>
pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first,ForwardIterator last, const Type& val);
参数:first
:last
:val
:comp
返回:返回一个pair的键值对,内容为：first:value可插入的第一个位置(亦即lower_bound)second:value可插入的最后一个位置(亦即upper_bound)
template<class ForwardIterator, class Type, class Predicate>
pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first,ForwardIterator last, const Type& val, Predicate comp);
```c++
#include
#include
#include
#include
#include
#include
#include
//x为value,y为元素
bool isGreater(int x, int y)
{
return x < y ? true : false;
}
int main()
{
std::vector vec = {6, 21, 32, 44, 54};
//返回的值要添加判断，否则使用指向last的指针会引起程序中断
//使用pair1.first - first.begin()即可获得指向元素的索引
auto pair1 = equal_range(vec.begin(), vec.end(), 21);
std::cout << *pair1.first << " " << pair1.first - vec.begin() << std::endl; //输出:21 1
std::cout << *pair1.second << " " << pair1.second - vec.begin() << std::endl; //输出:22 2
auto pair2 = equal_range(vec.begin(), vec.end(), 66, isGreater);
if (pair2.first == vec.end() || pair2.second == vec.end())
{
return 0;
}
std::cout << *pair2.first << std::endl; //输出:21
std::cout << *pair2.second << std::endl; //输出:22
getchar();
return 0;
}
```
equal_range另一种解读： 首先，这个函数只能做用于已经排序的容器，经在下试验，必须按照从小到大进行排序
该函数返回的是一对迭代器，第一个迭代器指向所查找元素的第一次出现的位置，第二个迭代器指向所查找元素最后一次出现位置的后一个位置. equal_range根据键值，返回一对迭代器的pair对象。如果该键值在容器中存在，则pair对象中的第一个迭代器指向该键关联的第一个实例，第二个迭代器指向该键关联的最后一个实例的下一位置。**如果找不到匹配的元素，则pair对象中的两个迭代器都将指向此键应该插入的位置**。总之，equal_range返回迭代器位置区间 [ lower_bound, upper_bound )
代码如下
```c++
int main()
{
vector vecInt;
pair<vector::iterator,vector::iterator> iter;
vecInt.push_back(1);
vecInt.push_back(2);
vecInt.push_back(3);
vecInt.push_back(3);
vecInt.push_back(4);
vecInt.push_back(5);
iter = equal_range(vecInt.begin(),vecInt.end(),3);
cout<<*iter.first<<endl;
cout<<*iter.second<<endl;
return 1;
}
```
第一次输出3，第二次输出4
那么，如果容器里面没有3呢
```c++
int main()
{
vector vecInt;
pair<vector::iterator,vector::iterator> iter;
vecInt.push_back(1);
vecInt.push_back(2);
//vecInt.push_back(3);
//vecInt.push_back(3);
vecInt.push_back(4);
vecInt.push_back(5);
iter = equal_range(vecInt.begin(),vecInt.end(),3);
cout<<*iter.first<<endl;
cout<<*iter.second<<endl;
return 1;
}
```
第一次输出4，第二次输出还是4
那么如果查找的元素是5呢，上面的代码就会崩溃，因为第二个迭代器会指向容器的end,所以，代码需做修改
```c++
int main()
{
vector vecInt;
pair<vector::iterator,vector::iterator> iter;
vecInt.push_back(1);
vecInt.push_back(2);
//vecInt.push_back(3);
//vecInt.push_back(3);
vecInt.push_back(4);
vecInt.push_back(5);
iter = equal_range(vecInt.begin(),vecInt.end(),5);
if(iter.first!=vecInt.end())
{
cout<<*iter.first<<endl;
}
if(iter.second!=vecInt.end())
{
cout<<*iter.second<<endl;
}
return 1;
}
```
在使用之前，应该先判断迭代器是否有效
**lower_bound：**
功能：查找**非递减序列[first,last) **内第一个大于或等于某个元素的位置。
返回值：如果找到返回找到元素的地址否则返回last的地址。（这样不注意的话会越界，小心）
用法：int t=lower_bound(a+l,a+r,key)-a；(a是数组)。
**upper_bound:**
功能：查找**非递减序列[first,last) **内第一个大于某个元素的位置。
返回值：如果找到返回找到元素的地址否则返回last的地址。（同样这样不注意的话会越界，小心）
用法：int t=upper_bound(a+l,a+r,key)-a；(a是数组，若是容器，则用对应的begin和end替换即可)
```c++
#include
#include
using namespace std;
int board[5] = {1,2,3,4,5};
int main(){
sort(board,board+5);
int t1 = lower_bound(board,board+5,3)-board;
int t2 = upper_bound(board,board+5,3)-board;
cout<<t1<<' '<<t2<<endl; //输出 2 3
return 0;
}
```
加了比较函数后:
```c++
#include
#include
using namespace std;
int board[5] = {1,2,3,4,5};
bool cmp(int a,int b){//比较函数 1
return a < b;
}
int main(){
sort(board,board+5);
int t1 = lower_bound(board,board+5,3,cmp)-board;
int t2 = upper_bound(board,board+5,3,cmp)-board;
cout<<t1<<' '<<t2<<endl; //输出 2 3
return 0;
}
```
可见结果没变由此可以得出一个结论，**cmp里函数应该写的是小于运算的比较。**
如果加上了等号，lower_bound和upper_bound两个函数功能就刚好反过来了：
```c++
#include
#include
using namespace std;
int board[5] = {1,2,3,4,5};
bool cmp(int a,int b){//比较函数 2
return a <= b;
}
int main(){
sort(board,board+5);
int t1 = lower_bound(board,board+5,3,cmp)-board;
int t2 = upper_bound(board,board+5,3,cmp)-board;
cout<<t1<<' '<<t2<<endl; //输出3 2
return 0;
}
```
## <二>排序和通用算法(14个)：提供元素排序策略,会改变原始数据顺序
**random_shuffle **:对指定范围内的元素随机调整次序.重载版本输入一个随机数产生操作.
参数:first
:last
返回：无
template
void random_shuffle(randomAccessItr first, randomAccessItr last);
参数:first
:last
:rand
返回：无
template <class randomAccessItr, class randomAccessGenerator>
void random_shuffle(randomAccessItr first,randomAccessItr last,randomAccessGenerator rand);
```c++
#include
#include
#include
#include
#include
#include
#include
#include
#include
int myrandom(int i)
{
return std::rand() % i;
}
int main()
{
std::vector vec1 = { 2, 32, 11, 33, 33, 43 };
sort(vec1.begin(), vec1.end());
for (int i = 0; i < vec1.size(); i++)
{
std::cout << vec1[i] << " "; //输出:2 11 32 33 33 43
}
std::cout << std::endl;
default_random_engine defaultEngine(time(0));
shuffle(vec1.begin(), vec1.end(), defaultEngine);
for (int i = 0; i < vec1.size(); i++)
{
std::cout << vec1[i] << " "; //输出:每次都不一样
}
std::cout << std::endl;
random_shuffle(vec1.begin(), vec1.end());
for (int i = 0; i < vec1.size(); i++)
{
std::cout << vec1[i] << " "; //输出:每次都一样
}
std::cout << std::endl;
std::srand(unsigned(std::time(0)));
random_shuffle(vec1.begin(), vec1.end(), myrandom);
for (int i = 0; i < vec1.size(); i++)
{
std::cout << vec1[i] << " "; //输出:每次都不一样
}
std::cout << std::endl;
getchar();
return 0;
}
```
**reverse **:将范围内元素重新按反序排列. 会改变原始数据在容器中的顺序
参数:first
:last
返回：无
template
void reverse(biDirectionalItr first, biDirectionalItr last);
**reverse_copy **:类似与 reverse ,不改变原始数据在容器中的顺序，不过将内容倒置写入另外一个容器.
参数:first
:last
:destFirst
返回：outputItr
template <class biDirectionalItr, class outputItr>
outputItr reverse_copy(biDirectionalItr first, biDirectionalItr last,outputItr destFirst);
```c++
#include "stdafx.h"
#include
#include
#include
#include
#include
#include
#include
int main()
{
{
std::vector vec1 = { 2, 32, 11, 33, 33, 43 };
reverse(vec1.begin(), vec1.end());
for (int i = 0; i < vec1.size(); i++)
{
std::cout << vec1[i] << " "; //输出:43 33 33 11 32 2
}
std::cout << std::endl;
std::vector vec2(vec1.size());
reverse_copy(vec1.begin(), vec1.end(), vec2.begin());
for (int i = 0; i < vec1.size(); i++)
{
std::cout << vec1[i] << " "; //输出:43 33 33 11 32 2
}
std::cout << std::endl;
for (int i = 0; i < vec2.size(); i++)
{
std::cout << vec2[i] << " "; //输出:2 32 11 33 33 43
}
std::cout << std::endl;
getchar();
return 0;
}
}
```
**rotate **:rotate可以传入三个参数，将第二个参数到第三个参数的元素放到第一个参数前面
由newFirst指向的元素成为容器第一个元素,并且将first到newFirst之间的元素移到newFirst指向元素的后面填充，其他元素位置不变.
参数:first
:newFirst
:last
返回：无
template
void rotate(forwardItr first, forwardItr newFirst, forwardItr last);
**rotate_copy **:类似与 rotate ,不过将结果写入另外一个容器.
参数:first
:middle
:last
:destFirst
返回：outputItr
template <class forwardItr, class outputItr>
outputItr rotate_copy(forwardItr first, forwardItr middle, forwardItr last,outputItr destFirst);
```c++
#include
#include
#include
#include
#include
#include
#include
int main()
{
std::vector vec1 = { 2, 32, 11, 33, 33, 43 };
auto it1 = vec1.begin() + 3;
rotate(vec1.begin(), it1, vec1.begin() + 4);
for (int i = 0; i < vec1.size(); i++)
{
std::cout << vec1[i] << " "; //输出:33 2 32 11 33 43
}
std::cout << std::endl;
std::vector vec2(vec1.size());
auto it2 = vec1.begin() + 3;
rotate_copy(vec1.begin(), it2, vec1.end(), vec2.begin());
for (int i = 0; i < vec2.size(); i++)
{
std::cout << vec2[i] << " "; //输出:11 33 43 33 2 32
}
std::cout << std::endl;
getchar();
return 0;
}
```
**merge **:将两个有序序列合并为一个有序序列,元素个数不变，并存放到另外一个序列中.重载版本使用自定义的比较.
参数:first1
:last1
:first2
:last2
:destFirst
返回:outputItr
template<class inputItr1,class inputItr2,class outputItr, class binaryPredicate>
outputItr merge(inputItr1 first1,inputItr1 last1, inputItr2 first2, inputItr2 last2,outputItr destFirst);
参数:first1
:last1
:first2
:last2
:destFirst
:op
返回:outputItr
template<class inputItr1,class inputItr2,class outputItr>
outputItr merge(inputItr1 first1,inputItr1 last1, inputItr2 first2, inputItr2 last2,outputItr destFirst, binaryPredicate op);
**inplace_merge **:合并两个排过序的连续序列,结果序列覆盖了两端范围,重载版本使用输入的操作进行排序.
参数:first1
:middle
:last
返回:void
template
void inplace_merge ( BidirectionalIterator first, BidirectionalIterator middle,BidirectionalIterator last );
参数:first1
:middle
:last
:comp
返回:void
template <class BidirectionalIterator, class Compare>
void inplace_merge ( BidirectionalIterator first, BidirectionalIterator middle,BidirectionalIterator last, Compare comp );
```c++
#include
#include
#include
#include
#include
#include
#include
#include
#include
int main()
{
{
std::vector vec1 = { 2, 11, 33, 33, 43 };
std::vector vec2 = { 4, 14, 23, 33, 44 };
std::vector vec3(vec1.size() + vec2.size());
auto result = merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), vec3.begin());
for (int i = 0; i < vec3.size(); i++)
{
std::cout << vec3[i] << " ";
}
std::cout << std::endl;
std::vector vec4 = { 4, 6, 8, 12, 20, 1, 5, 8, 10 , 15};
inplace_merge(vec4.begin(), vec4.begin() + 5, vec4.end());
for (int i = 0; i < vec4.size(); i++)
{
std::cout << vec4[i] << " ";
}
getchar();
return 0;
}
}
```
**nth_element **:将指定范围内的序列重新排序,使第n大元素处于第n位置(从0开始,其位置是下标为 n的元素),并且比这个元素小的元素都排在这个元素之前，比这个元素大的元素都排在这个元素之后,但不能保证他们是有序的,重载版本使用了自定义的比较操作.
> 找中位数写起来太过麻烦，去观摩了一下其他大佬的代码，竟然还有nth_element这种东西。
>
> <http://www.cplusplus.com/reference/algorithm/nth_element/>
> nth_element(first,nth,last)
>
> > first，last 第一个和最后一个迭代器，也可以直接用数组的位置。
> > nth，要定位的第nn 个元素，能对它进行随机访问.
>
> 将第n_thn_th 元素放到它该放的位置上，左边元素都小于它，右边元素都大于它.
```C++
int main()
{
int a[10];
for(int i=0 ; i<10 ; ++i){
a[i] = i;
}
random_shuffle(a,a+10);
for(int i=0 ; i<10 ; ++i) std::cout << a[i] << ' ';std::cout << '\n'; //8 1 9 2 0 5 7 3 4 6
nth_element(a,a+6,a+10);
for(int i=0 ; i<10 ; ++i) std::cout << a[i] << ' ';std::cout << '\n'; //5 1 4 2 0 3 6 7 8 9
return 0;
}
```
参数:_First
:_Nth
:_Last
返回:void
template
void nth_element(_RanIt _First, _RanIt _Nth, _RanIt _Last);
参数:_First
:_Nth
:_Last
:_Pred
返回:void
template<class _RanIt, class _Pr>
void nth_element(_RanIt _First, _RanIt _Nth, _RanIt _Last, _Pr _Pred);
```c++
```
**sort **:以升序重新排列范围内的元素,重载版本使用了自定义的比较操作.
参数:first
:last
返回：void
template
void sort(randomAccessItr first,randomAccessItr last);
参数:first
:last
:op
返回：void
template<class randomAccessItr, class compare>
void sort(randomAccessItr first, randomAccessItr last, compare op);
**is_sorted**:检查指定范围内元素是否排序
参数:first
:last
返回：bool 已排序返回true,未排序返回false
template
bool is_sorted (ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class Compare>
bool is_sorted (ForwardIterator first, ForwardIterator last, Compare comp);
**partion **:对指定范围内元素重新排序,根据自定义函数,把计算结果为 true 的元素放在结果为 false 的元素之前.
参数:first
:last
:pred
返回：ForwardIterator 排序后返回首个不满足条件元素迭代器
template <class ForwardIterator, class Predicate>
ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred);
**partial_sort **:对整个序列做部分排序,被排序元素的个数正好可以被放到范围内.重载版本使用自定义的比较操作.
即，对局部进行排序时，序列的前n个最小的元素放在序列的前n个位置，其余的放在序列的后面未进行排序。
参数:first
:middle
:last
返回：void
template
void partial_sort ( RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last );
参数:first
:middle
:last
:comp
返回：void
template <class RandomAccessIterator, class Compare>
void partial_sort ( RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp );
**partial_sort_copy **:与 partial_sort 相同,除了将经过排序的序列复制到另外一个容器.
参数:first
:last
:result_first
:result_last
返回：RandomAccessIterator
template <class InputIterator, class RandomAccessIterator>
RandomAccessIterator partial_sort_copy ( InputIterator first,InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last );
参数:first
:last
:result_first
:result_last
:comp
返回：RandomAccessIterator
template <class InputIterator, class RandomAccessIterator, class Compare>
RandomAccessIterator partial_sort_copy ( InputIterator first,InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp );
所谓稳定排序，是指对一个序列进行排序之后，如果两个元素的值相等，则原来乱序时在前面的元素现在（排好序之后）仍然排在前面
**stable_sort **:类似与 sort ,不过保留容器中相等元素之间的顺序关系.
参数:first
:last
返回:void
template
void stable_sort ( RandomAccessIterator first, RandomAccessIterator last );
参数:first
:last
:comp
返回:void
template <class RandomAccessIterator, class Compare>
void stable_sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );
**stable_partition **:与 partition 类似,不过保留容器中相等元素之间的相对顺序.
参数:first
:last
:pred
返回:BidirectionalIterator
template <class BidirectionalIterator, class UnaryPredicate>
BidirectionalIterator stable_partition (BidirectionalIterator first, BidirectionalIterator last, UnaryPredicate pred);
```c++
#include
#include
#include
#include
#include
#include
#include
#include
#include
int main()
{
{
std::vector vec1 = { 22, 11, 5, 33, 43 };
sort(vec1.begin(), vec1.end());
for (int i = 0; i < vec1.size(); i++)
{
std::cout << vec1[i] << " "; //输出:5 11 22 33 43
}
std::cout << std::endl;
sort(vec1.begin(), vec1.end(), [](int x, int y)->bool { return x > y; });
for (int i = 0; i < vec1.size(); i++)
{
std::cout << vec1[i] << " "; //输出:43 33 22 11 5
}
std::cout << std::endl;
std::vector vec2 = { 22, 5, 33, 43, 10 };
auto result2 = partition(vec2.begin(), vec2.end(), [](int x)->bool { return x % 2 == 0 ? true : false; });
std::cout << *result2 << std::endl; //输出:33 注意是33说明5和10是调换位置
for (int i = 0; i < vec2.size(); i++)
{
std::cout << vec2[i] << " "; //输出:22 10 33 43 5
}
std::cout << std::endl;
std::vector vec3 = { 7, 6, 9, 4, 1, 5, 8, 2, 3 };
partial_sort(vec3.begin(), vec3.begin() + 2, vec3.end()); //因为是偏移了2个位置，所以将最小的2个排序到前面2个位置，其他的不排序
for (int i = 0; i < vec3.size(); i++)
{
std::cout << vec3[i] << " "; //输出:1 2 9 7 6 5 8 4 3
}
std::cout << std::endl;
std::vector vec4(vec3.size());
partial_sort_copy(vec3.begin(), vec3.end(), vec4.begin(), vec4.end());
for (int i = 0; i < vec4.size(); i++)
{
std::cout << vec4[i] << " "; //输出:1 2 3 4 5 6 7 8 9
}
std::cout << std::endl;
getchar();
return 0;
}
}
```
## <三>删除和替换算法(15个)
**copy **:用于容器之间元素的拷贝,即将迭代器区间[first,last)的元素复制到目标容器中
参数:_First 指出被复制的元素的区间范围[ _First,_Last).
:_Last
:_DestBeg 指出复制到的目标区间起始位置
返回:OutputIterator 返回一个迭代器,指向目标容器中拷贝元素区间的下一个位置(因为是左必右开,也就是目标容器的_DestBeg位置)
template<class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator _First, InputIterator _Last, OutputIterator _DestBeg);
**copy_backward **:其复制过程是从最后的元素开始复制,直到首元素复制出来.也就是说,复制操作是从last-1开始,直到first结束.这些元素也被从后向前复制到目标容器中
参数:_First
:_Last
:_Dest
返回:_BidIt2 返回一个迭代器,指出已被复制元素区间的起始位置
template<class _BidIt1, class _BidIt2> inline
_BidIt2 copy_backward(_BidIt1 _First, _BidIt1 _Last,_BidIt2 _Dest);
**copy_if:**将满足条件的元素(对元素调用pred返回true的元素)复制到目标容器中
参数:_First
:_Last
:_Dest
:_Pred
返回:_BidIt2 返回一个迭代器,指向目标容器中最后一个拷贝元素的下一个位置
template<class InputIterator, class OutputIterator, class BinaryPredicate>
OutputIterator copy_if(InputIterator _First, InputIterator _Last,OutputIterator _Dest,Predicate _Pred);
**copy_n:**从first开始复制count个元素到result的容器中
参数:first
:count
:dest
返回:OutputIterator 返回一个迭代器,指向目标容器中最后一个拷贝元素的下一个位置
template<class InputIterator, class Size, class OutputIterator>
OutputIterator copy_n(InputIterator first, Size count, OutputIterator dest);
```c++
#include "stdafx.h"
#include
#include
#include
#include
#include
#include
#include
bool greater10(int num)
{
return num % 2 ? true : false;
}
int main()
{
{
std::vector arr = { 12, 43, 23, 65, 34, 23, 55, 56 ,3, 34 };
std::vector arr1(10);
std::vector arr2(10);
std::vector arr3(10);
std::vector arr4(10);
auto var1 = copy(arr.begin() + 3, arr.begin() + 5, arr1.begin());
for (int i = 0; i < arr1.size(); i++)
{
std::cout << arr1[i] << " ";
}
std::cout << std::endl;
auto var2 = copy_backward(arr.begin(), arr.begin() + 5, arr2.end());
for (int i = 0; i < arr2.size(); i++)
{
std::cout << arr2[i] << " ";
}
std::cout << std::endl;
auto var3 = copy_if(arr.begin(), arr.begin() + 5, arr3.begin(), greater10);
for (int i = 0; i < arr3.size(); i++)
{
std::cout << arr3[i] << " ";
}
std::cout << std::endl;
auto var4 = copy_n(arr.begin(), 5, arr4.begin());
for (int i = 0; i < arr4.size(); i++)
{
std::cout << arr4[i] << " ";
}
std::cout << std::endl;
getchar();
return 0;
}
}
```
**vector中的remove的作用是将等于value的元素放到vector的尾部，但并不减少vector的size(尾部为无效数据)**
**移除容器里面的元素应该使用容器自带的remove,不应该使用remove算法**
**remove **:删除在范围内的所有等于指定的元素,注意,该函数并不真正删除元素.内置数组不适合使用 remove 和 remove_if 函数.
参数:first
:last
:value
返回：forwardItr 指向容器中第一个无效数据的迭代器
template <class forwardItr,class Type>
forwardItr remove(forwardItr first, forwardItr last, const Type& value);
**remove_copy **:将所有不匹配的元素都复制到一个指定容器,
参数:first1
:last1
:destFirst
:value
返回：outputItr 指向被拷贝最后元素的下一个位置的迭代器
template <class inputItr,class outputItr,class Type>
outputItr remove_copy(inputItr first1, inputItr last1, outputItr destFirst, const Type& value);
**remove_if **:删除指定范围内输入操作结果为 true 的元素.
参数:first
:last
:destFirst
:op
返回：forwardItr
template <class forwardItr, class unaryPredicate>
forwardItr remove_if(forwardItr first, forwardItr last, unaryPredicate op);
**remove_copy_if **:将所有不匹配的元素拷贝到一个指定容器.
参数:first1
:last1
:destFirst
:op
返回：outputItr 指向被拷贝最后元素的下一个位置的迭代器
template <class inputItr,class outputItr, class unaryPredicate>
outputItr remove_copy_if(inputItr first1, inputItr last1, outputItr destFirst, unaryPredicate op)
```c++
#include
#include
#include
#include
#include
#include
#include
bool remove_func(int x)
{
return x % 2 == 0 ? true : false;
}
int main()
{
{
//如果为1234 remove 2 = 1344 3被复制到2的位置，4被复制到3的位置,后面的原来是什么就是什么
//也就是将元素删除后，保留未删除的数据，然后其他位置原有数据不变，比如10个元素的容器，删除了符合条件的3个元素，那么前面7个元素将存放不符合删除条件的元素，然后末尾加上3个容器中末尾的3个原始元素
//vector v; // 正如从前
//v.erase(remove(v.begin(), v.end(), 99), v.end()); // 真的删除所有
// 等于99的元素
//cout << v.size(); // 现在返回7
std::vector vec1 = { 34, 43, 34, 65, 34, 23, 55, 56 ,2, 34 };
auto result1 = remove(vec1.begin(), vec1.end(), 34);
std::cout << *result1 << std::endl; //输出:55 指向首个无效数据的迭代器，也就是vec1.begin+6的位置
for (int i = 0; i < vec1.size(); i++)
{
std::cout << vec1[i] << " "; //输出:43 65 23 55 56 2 55 56 2 34
}
std::cout << std::endl;
std::vector vec2 = { 34, 43, 34, 65, 34, 23, 55, 56 ,2, 34 };
std::vector vec3(vec2.size());
auto result2 = remove_copy(vec2.begin(), vec2.end(), vec3.begin(), 34);
std::cout << *result2 << std::endl; //输出:0 指向最后一个拷贝元素下一个位置的迭代器
for (int i = 0; i < vec3.size(); i++)
{
std::cout << vec3[i] << " "; //输出:43 65 23 55 56 2 0 0 0 0
}
std::cout << std::endl;
//同remove一样，将不要删除的元素往前移，后面的元素是无效数据
std::vector vec4 = { 34, 43, 34, 65, 34, 23, 55, 56 ,2, 34 };
remove_if(vec4.begin(), vec4.end(), remove_func);
for (int i = 0; i < vec4.size(); i++)
{
std::cout << vec4[i] << " "; //输出:43 65 23 55 34 23 55 56 2 34
}
std::cout << std::endl;
std::vector vec5 = { 34, 43, 34, 65, 34, 23, 55, 56 ,2, 34 };
std::vector vec6(vec5.size());
auto result5 = remove_copy_if(vec5.begin(), vec5.end(), vec6.begin(), remove_func);
std::cout << *result5 << std::endl; //输出:0 指向最后一个拷贝元素下一个位置的迭代器
for (int i = 0; i < vec6.size(); i++)
{
std::cout << vec6[i] << " "; //输出:43 65 23 55 0 0 0 0 0 0
}
std::cout << std::endl;
getchar();
return 0;
}
}
```
**replace **:将范围内的所有等于 old_value 的元素都用 new_value 替代.
参数:first
:last
:oldValue
:newValue
返回：无
template <class forwardItr,class Type>
void replace(forwardItr first, forwardItr last,const Type& oldValue, const Type& newValue);
**replace_copy **:与 replace 类似,不过将结果写入另外一个容器.
参数:first1
:last1
:destFirst
:oldValue
:newValue
返回：outputItr 指向dest最后拷贝元素的下一个位置
template <class inputItr,class outputItr,class Type>
outputItr replace_copy(inputItr first1, inputItr last1, outputItr destFirst,const Type& oldValue, const Type& newValue);
**replace_if **:将范围内的所有操作结果为 true 的元素用新值替代.
参数:first
:last
:op
:newValue
返回：无
template <class forwardItr, class unaryPredicate,class Type>
void replace_if(forwardItr first, forwardItr last, unaryPredicate op,const Type& newValue);
**replace_copy_if **:类似与 replace_if ,不过将结果写入另外一个容器.
参数:first1
:last1
:destFirst
:op
:newValue
返回：outputItr 指向dest拷贝最后元素的下一个位置的迭代器
template <class inputItr,class outputItr, class unaryPredicate>
outputItr replace_copy_if(inputItr first1, inputItr last1, outputItr destFirst, unaryPredicate op,const Type& newValue);
```C++
#include
#include
#include
#include
#include
#include
#include
bool replace_func(int x)
{
return x % 2 == 0 ? true : false;
}
int main()
{
{
std::vector vec1 = { 12, 22, 11, 33, 11, 4 };
replace(vec1.begin(), vec1.end(), 11, 3);
for (int i = 0; i < vec1.size(); i++)
{
std::cout << vec1[i] << " "; //输出:12 22 3 33 3 4
}
std::cout << std::endl;
std::vector vec2 = { 12, 22, 11, 33, 11, 4 };
std::vector vec3(vec2.size());
auto result1 = replace_copy(vec2.begin(), vec2.end(), vec3.begin(), 11, 3);
result1--;
std::cout << *result1 << std::endl; //输出:4
for (int i = 0; i < vec3.size(); i++)
{
std::cout << vec3[i] << " "; //输出:12 22 3 33 3 4
}
std::cout << std::endl;
std::vector vec4 = { 12, 22, 11, 33, 11, 4 };
replace_if(vec4.begin(), vec4.end(), replace_func, 7);
for (int i = 0; i < vec4.size(); i++)
{
std::cout << vec4[i] << " "; //输出:7 7 11 33 11 7
}
std::cout << std::endl;
std::vector vec5 = { 12, 22, 11, 33, 11, 4 };
std::vector vec6(vec5.size());
replace_copy_if(vec5.begin(), vec5.end(), vec6.begin(), replace_func, 5);
for (int i = 0; i < vec6.size(); i++)
{
std::cout << vec6[i] << " "; //输出:5 5 11 33 11 5
}
std::cout << std::endl;
getchar();
return 0;
}
}
```
**swap **:交换存储在两个对象中的值.
template
void swap(Type& objcet1, Type& objec2);
**swap_range **:将在范围内的元素与另外一个序列的元素值进行交换.
template<class forwardItr1, class forwardItr2>
forwardItr2 swap_ranges(forwardItr1 first,forwardItr1 last, forwardItr2 first2);
**iter_swap **:交换两个 ForwardIterator 的值.
template<class forwardItr1,class forwardItr2>
void iter_swap(forwardItr1 first,forwardItr2 scecod);
```c++
#include
#include
#include
#include
#include
#include
#include
int main()
{
{
std::vector vec1 = { 12, 22, 11, 33, 4，8 };
std::vector vec2 = { 3, 4, 23, 11, 7 };
swap(vec1, vec2);
for (int i = 0; i < vec1.size(); i++)
{
std::cout << vec1[i] << " "; //输出:3 4 23 11 7
}
std::cout << std::endl;
for (int i = 0; i < vec2.size(); i++)
{
std::cout << vec2[i] << " "; //输出:12 22 11 33 4 8
}
std::cout << std::endl;
std::vector vec3 = { 12, 22, 11, 33, 4 };
std::vector vec4 = { 3, 4, 23, 11, 7 };
swap_ranges(vec3.begin(), vec3.begin() + 3, vec4.begin() + 2);
for (int i = 0; i < vec3.size(); i++)
{
std::cout << vec3[i] << " "; //输出:23 11 7 33 4
}
std::cout << std::endl;
for (int i = 0; i < vec4.size(); i++)
{
std::cout << vec4[i] << " "; //输出:3 4 12 22 11
}
std::cout << std::endl;
std::vector vec5 = { 12, 22, 11, 33, 4 };
iter_swap(vec5.begin() + 1, vec5.begin() + 3);
for (int i = 0; i < vec5.size(); i++)
{
std::cout << vec5[i] << " "; //输出:12 33 11 22 4
}
std::cout << std::endl;
getchar();
return 0;
}
}
```
**unique **:unique的功能是去除相邻的重复元素(只保留一个),其实它并不真正把重复的元素删除,只是把重复的元素移到后面去了,然后依然保存到了原数组中,然后返回去重后最后一个元素的地址,**因为unique去除的是相邻的重复元素,所以一般用之前都会要排一下序.**
注意,unique并不直接改变容器的大小,只改变容器元素的顺序.调用unique“删除”了相邻的重复值.给“删除”加上引号是因为unique实际上并没有删除任何元素,而是将无重复的元素复制到序列的前段,从而覆盖相邻的重复元素.unique返回的迭代器如果需要添加或删除元素,则必须使用容器操作.原理与remove类似
参数:_First
:_Last
返回：ForwardIterator 指向超出无重复的元素范围末端的下一个位置.
template
ForwardIterator unique(ForwardIterator _First, ForwardIterator _Last);
template<class ForwardIterator, class Predicate>
ForwardIterator unique(ForwardIterator _First, ForwardIterator _Last,Predicate _Comp);
**unique_copy **:类似与 unique ,不过它把结果输出到另外一个容器.
template<class InputIterator, class OutputIterator>
OutputIterator unique_copy(InputIterator _First, InputIterator _Last, OutputIterator _Result);
template<class InputIterator, class OutputIterator, class BinaryPredicate>
OutputIterator unique_copy(InputIterator _First, InputIterator _Last, OutputIterator _Result,BinaryPredicate _Comp,);
```c++
#include
#include
#include
#include
#include
#include
#include
int main()
{
{
std::vector vec1 = { 12, 22, 33, 33, 33, 44 };
auto result1 = unique(vec1.begin(), vec1.end());
std::cout << *result1 << std::endl;
for (int i = 0; i < vec1.size(); i++)
{
std::cout << vec1[i] << " "; //输出:12 22 33 44 33 44
}
std::cout << std::endl;
std::vector vec2 = { 12, 22, 33, 33, 33, 44 };
std::vector vec3(vec2.size());
auto result2 = unique_copy(vec2.begin(), vec2.end(), vec3.begin());
result2--;
std::cout << *result2 << std::endl;
for (int i = 0; i < vec3.size(); i++)
{
std::cout << vec3[i] << " "; //输出:12 22 33 44 0 0
}
std::cout << std::endl;
getchar();
return 0;
}
}
```
## <四>排列组合算法(2个)：提供计算给定集合按一定顺序的所有可能排列组合
**next_permutation **:取出当前范围内的排列,并将其重新排序为下一个排列.重载版本使用自定义的比较操作.
**prev_permutation **:取出范围内的序列并将它重新排序为上一个序列.如果不存在上一个序列则返回 false .重载版本使用自定义的比较操作.
```c++
#include
#include
#include
#include
#include
#include
#include
#include
#include
int main()
{
{
int myints[] = { 1,2,3 };
std::sort(myints, myints + 3);
std::cout << "The 3! possible next_permutations with 3 elements:\n";
do {
std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
} while (std::next_permutation(myints, myints + 3));
std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
std::cout << "The 3! possible prev_permutations with 3 elements:\n";
do {
std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
} while (std::prev_permutation(myints, myints + 3));
std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
getchar();
return 0;
}
}
```
##
<五>算术算法(4个)
主要是对容器的数据元素进行数值计算,所在头文件为：
**accumlate **:函数将第三个实参用作累加的初始值(init),然后在此初值上累加输入范围内所有元素的值.accumulate算法返回累加的结果,其返回类型就是第三个实参的类型.容器内的元素类型必须与第三个实参的类型匹配,或者可转换为第三个实参的类型.
参数:first
:last
:init 累加初始值
返回:Type
template <class inputItr, class Type>
Type accumulate(inputItr first, inputItr last, Type init);
参数:first
:last
:init
:op **函数第一个参数总为初始值(会变化),第二个参数依次为集合的每一元素**
返回:Type
template <class inputItr, class Type, class binaryOperation>
Type accumulate(inputItr first, inputItr last, Type init,binaryOperation op);
```c++
template<class _InIt, class _Ty, class _Fn2>inline _Ty _Accumulate_unchecked(_InIt _First, _InIt _Last, _Ty _Val, _Fn2& _Func)
{ // return sum of _Val and all in [_First, _Last), using _Func
for (; _First != _Last; ++_First)
_Val = _Func(_Val, *_First);
return (_Val);
}
```
```c++
#include
#include
#include
#include
#include
using namespace std;
int multiply(int x, int y)
{
return x - y;
}
int main()
{
{
//用accumulate统计vector容器对象中的元素之和
std::vector vec = {32, 11, 23, 4, 44};
int sum = accumulate(vec.begin(), vec.end(), 1000);
std::cout << sum << std::endl; //输出1114
//可以使用accumulate把string型的vector容器中的元素连接起来
std::vector<std::string> vec2 = { "32", "11", "23", "4", "44" };
string str = accumulate(vec2.begin(), vec2.end(), string(" "));
std::cout << str << std::endl; //输出 321123444
int total = accumulate(vec.begin(), vec.end(), 1000, multiply);
std::cout << total << std::endl; //输出886，即1000-114
}
getchar();
return EXIT_SUCCESS;
}
```
**adjacent_difference **:创建一个新序列,该序列的每个新值都代表了当前元素与上一个元素的差.重载版本用指定的二元操作计算相邻元素的差.
参数:first
:last
:destFirst 输出集合
template<class inputItr, class outputItr, class binaryOperation>
outputItr adjacent_difference(inputItr first,inputItr last, outputItr destFirst);
参数:first
:last
:destFirst 输出集合
:op
template<class inputItr, class outputItr>
outputItr adjacent_difference(inputItr first,inputItr last, outputItr destFirst,binaryOperation op);
```c++
#include
#include
#include
#include
#include
//x为当前元素，y为上一个元素
int sub(int x, int y)
{
return x + (x - y);
}
int main()
{
{
std::vector vec = { 12, 22, 11, 33, 33, 43 };
std::vector vec2(6);
auto it = adjacent_difference(vec.begin(), vec.end(), vec2.begin());
for (int i = 0; i < vec2.size(); i++)
{
std::cout << vec2[i] << " "; //输出：12 10 -11 22 0 10
}
auto it2 = adjacent_difference(vec.begin(), vec.end(), vec2.begin(), sub);
for (int i = 0; i < vec2.size(); i++)
{
std::cout << vec2[i] << " "; //输出：12 32 0 55 33 53
}
getchar();
return 0;
}
}
```
**adjacent_difference **:创建一个新序列,该序列的每个新值都代表了当前元素与上一个元素的差.重载版本用指定的二元操作计算相邻元素的差.
参数:first
:last
:destFirst 输出集合
template<class inputItr, class outputItr, class binaryOperation>
outputItr adjacent_difference(inputItr first,inputItr last, outputItr destFirst);
参数:first
:last
:destFirst 输出集合
:op
template<class inputItr, class outputItr>
outputItr adjacent_difference(inputItr first,inputItr last, outputItr destFirst,binaryOperation op);
```c++
#include
#include
#include
#include
#include
//x为当前元素，y为上一个元素
int sub(int x, int y)
{
return x + (x - y);
}
int main()
{
{
std::vector vec = { 12, 22, 11, 33, 33, 43 };
std::vector vec2(6);
auto it = adjacent_difference(vec.begin(), vec.end(), vec2.begin());
for (int i = 0; i < vec2.size(); i++)
{
std::cout << vec2[i] << " "; //输出：12 10 -11 22 0 10
}
auto it2 = adjacent_difference(vec.begin(), vec.end(), vec2.begin(), sub);
for (int i = 0; i < vec2.size(); i++)
{
std::cout << vec2[i] << " "; //输出：12 32 0 55 33 53
}
getchar();
return 0;
}
}
```
**inner_product **:对两个序列做内积 ( 对应的元素相乘,再求和 ) ,并将内积加到一个输入的的初始值上.重载版本使用了用户定义的操作.
参数:first1
:last1
:first2
:init
template<class inputItr1, class inputItr2,class Type>
Type inner_product(inputItr1 first1,inputItr1 last1,inputItr2 first2,Type init);
参数:first1
:last1
:first2
:last2
:init
:op1
:op2
template<class inputItr1, class inputItr2,class Type, class binaryOperation1, class binaryOperation2>
Type inner_product(inputItr1 first1,inputItr1 last1,inputItr2 first2,inputItr2 last2,Type init,binaryOperation1 op1,binaryOperation2 op2);
```c++
#include
#include
#include
#include
#include
using namespace std;
int main()
{
{
std::vector vec = { 12, 22, 11};
std::vector vec2 = { 10, 10, 10};
//vec[i]*vec2[i] + vec[i+1]*vec2[i+1]
auto value = inner_product(vec.begin(), vec.end(), vec2.begin(), 0);
std::cout << value << std::endl; //输出450
// 执行plus(initValue,minus(vec[i],vec2[i]))，即initValue+=minus(vec[i],vec2[i]
auto value2 = inner_product(vec.begin(), vec.end(), vec2.begin(), 0, plus(), minus());
std::cout << value2 << std::endl; //输出15
getchar();
return 0;
}
}
```
**partial_sum **:创建一个新的元素序列,其中每个元素的值代表了范围内该位置之前所有元素之和.重载版本使用了自定义操作替代加法.
参数:first
:last
:destFirst
template<class inputItr, class outputItr>
outputItr partial_sum(inputItr first,inputItr last,outputItr destFirst);
参数:first
:last
:destFirst
:op
template<class inputItr, class outputItr, class binaryOperation>
outputItr partial_sum(inputItr first,inputItr last,outputItr destFirst,binaryOperation op);
```c++
#include
#include
#include
#include
#include
using namespace std;
//x是当前元素，y是前面元素
int sum(int x, int y)
{
return x + (y - 10);
}
int main()
{
{
std::vector vec = { 12, 22, 11, 33, 33, 43 };
std::vector sum_vec(6);
auto pos = partial_sum(vec.begin(), vec.end(), sum_vec.begin());
for (int i = 0; i < sum_vec.size(); i++)
{
std::cout << sum_vec[i] << " "; //12 34 45 78 111 154
}
auto pos2 = partial_sum(vec.begin(), vec.end(), sum_vec.begin(), sum);
for (int i = 0; i < sum_vec.size(); i++)
{
std::cout << sum_vec[i] << " "; //12 24 25 48 71 104
}
getchar();
return 0;
}
}
```
## <六>生成和异变算法(6个)
**fill **:将容器中指定位置[first, last)元素的值赋值为value.
参数:first
:last
:value
返回:无
template <class forwardItr, class Type>
void fill(forwardItr first, forwardItr last, const Type& value);
**fill_n **:将容器中指定位置[first, frist+n) 范围内的元素赋值为value.
参数:first
:n
:value
返回:无
template <class forwardItr, class size, class Type>
void fill_n(forwardItr first, size n, const Type& value);
```c++
#include
#include
#include
#include
#include
#include
#include
int main()
{
std::vector arr = { 12, 43, 23, 65, 34, 23, 55, 56 ,3, 34 };
fill(arr.begin(), arr.end(), 10);
for (int i = 0; i < arr.size(); i++)
{
std::cout << arr[i] << " ";
}
std::cout << std::endl;
fill_n(arr.begin(), 5, 3);
for (int i = 0; i < arr.size(); i++)
{
std::cout << arr[i] << " ";
}
std::cout << std::endl;
getchar();
return 0;
}
```
**for_each **:依次对范围内的所有元素执行输入的函数.
参数:first
:last
:func
返回:Function 返回f函数的首地址
```c++
template <class inputItr,class function>
Function for_each(InputIterator first, InputIterator last, Function f) {
for ( ; first != last; ++first) f(*first);
return f;
}
```
```c++
#include
#include
#include
#include
#include
#include
#include
int main()
{
{
std::vector vec1 = { 12, 22, 33, 33, 33, 44 };
for_each(vec1.begin(), vec1.end(), [](int x)->void { std::cout << x << " "; }); //输出:12 22 33 33 33 44
getchar();
return 0;
}
}
```
**generate **:用指定函数对象产生的值去给容器指定范围内元素赋值
参数:first
:last
:gen
返回:无
template <class forwardItr, class function>
void generate(forwardItr first, forwardItr last, function gen);
**generate_n **:一个函数对象产生的值给一定的范围内指定数目的容器元素赋值
参数:first
:n
:gen
返回:无
template <class forwardItr, class size, class function>
void generate_n(forwardItr first, size n, function gen);
```c++
#include
#include