NOIP学习小站一、交换算法
1.swap
swap函数用于交换两个变量的值，需要注意的是，这里的变量的类型可以是基本数据类型，也可以是是结构、类、STL容器等。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//遍历容器的模板函数
template<typename Iter>
void list_elements(Iter begin, Iter end){
while(begin!=end){
cout<<*begin<<" ";
begin++;
}
cout<<endl;
}
struct Point{
int x,y;
Point(){}
Point(int x,int y){
this->x = x;
this->y = y;
}
void print(){
cout<<"("<<x<<","<<y<<")";
}
};
int main()
{
int a = 123,b = 456;
cout<<a<<" "<<b<<endl;
swap(a,b);
cout<<a<<" "<<b<<endl;
vector<int> va,vb;
va.push_back(1);
va.push_back(2);
vb.push_back(3);
list_elements(va.begin(),va.end());
list_elements(vb.begin(),vb.end());
swap(va,vb);
list_elements(va.begin(),va.end());
list_elements(vb.begin(),vb.end());
Point p(1,2),q(3,4);
p.print();q.print();
swap(p,q);
p.print();q.print();
return 0;
}2.iter_swap
iter_swap函数的两个参数是指针（或迭代器），调用函数后两个指针指向的变量的值被交换。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//遍历容器的模板函数
template<typename Iter>
void list_elements(Iter begin, Iter end){
while(begin!=end){
cout<<*begin<<" ";
begin++;
}
cout<<endl;
}
int main()
{
int a[5] = {1,2,3,4,5};
vector<int> ve(a,a+5);
list_elements(a,a+5);
iter_swap(a,a+4);
list_elements(a,a+5);
list_elements(ve.begin(),ve.end());
iter_swap(ve.begin(),ve.begin()+2);
list_elements(ve.begin(),ve.end());
return 0;
}二、删除
1.remove
remove(begin,end,x)用于“移除”区间\([begin,end)\)内所有与x相等的元素。函数的返回值是一个指针（或迭代器）bound，函数处理后区间\([begin,bound)\)是“移除”后剩余元素的区域，\([bound,end)\)还有其它元素（注意：这个区域的元素并非都是x）。可见，这里的“移除”并不是真正的移除。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//遍历容器的模板函数
template<typename Iter>
void list_elements(Iter begin, Iter end){
while(begin!=end){
cout<<*begin<<" ";
begin++;
}
cout<<endl;
}
int main()
{
const int N = 5;
int a[N] = {3,2,3,3,5};
vector<int> ve(a,a+N);
list_elements(a,a+N);
int *bound = remove(a,a+N,3);
list_elements(a,bound);
list_elements(ve.begin(),ve.end());
vector<int>::iterator it = remove(ve.begin(),ve.end(),3);
list_elements(ve.begin(),it);
//通过vector的erase成员函数实现真正移除元素
ve.erase(it,ve.end());
//ve.erase(remove(ve.begin(),ve.end(),3),ve.end());
list_elements(ve.begin(),ve.end());
return 0;
}2.remove_if
remove_if(begin,end,function)用于“移除”区间\([begin,end)\)内符合条件的元素（作为参数调用function函数返回值为true）。函数的返回值是一个指针（或迭代器）bound，函数处理后区间\([begin,bound)\)是“移除”后剩余元素的区域，\([bound,end)\)还有其它元素（注意：并非那些被“移除”的那些元素全部移到了这个区域）。可见，这里的“移除”并不是真正的移除。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//遍历容器的模板函数
template<typename Iter>
void list_elements(Iter begin, Iter end){
while(begin!=end){
cout<<*begin<<" ";
begin++;
}
cout<<endl;
}
//判断奇数
bool odd(const int &x){
return x%2!=0;
}
int main()
{
const int N = 5;
int a[N] = {3,2,3,3,5};
vector<int> ve(a,a+N);
list_elements(a,a+N);
int *bound = remove_if(a,a+N,odd);
list_elements(a,bound);
list_elements(ve.begin(),ve.end());
vector<int>::iterator it = remove_if(ve.begin(),ve.end(),odd);
list_elements(ve.begin(),it);
//通过vector的erase成员函数实现真正移除元素
ve.erase(it,ve.end());
//ve.erase(remove_if(ve.begin(),ve.end(),odd),ve.end());
list_elements(ve.begin(),ve.end());
return 0;
}3.unique
unique(start,end)用于“移除”区间\([begin,end)\)内的连续相等元素（仅留下一个） 。函数的返回值是一个指针（或迭代器）bound， 函数处理后区间\([begin,bound)\)是“移除”后剩余元素的区域，可见与前面的remove函数一样，unique也没有真正删除那些重复的元素。
需要注意的是，unique是移除连续相等的元素，并不能做到每个元素唯一，除非区间是有序的。例如\(\{2,2,3,2,2,2,3,3\}\)，经过unique函数处理后“剩余”的有效数据是\(\{2,3,2,3\}\)。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//遍历容器的模板函数
template<typename Iter>
void list_elements(Iter begin, Iter end){
while(begin!=end){
cout<<*begin<<" ";
begin++;
}
cout<<endl;
}
int main()
{
const int N = 10;
int a[N] = {3,2,3,3,5,3,3,3,5,5};
vector<int> ve(a,a+N);
list_elements(a,a+N);
int *bound = unique(a,a+N);
list_elements(a,bound);
list_elements(ve.begin(),ve.end());
vector<int>::iterator it = unique(ve.begin(),ve.end());
list_elements(ve.begin(),it);
//通过vector的erase成员函数实现真正移除元素
ve.erase(it,ve.end());
//ve.erase(unique(ve.begin(),ve.end()),ve.end());
list_elements(ve.begin(),ve.end());
return 0;
}三、替换
1.replace
replace(begin,end,oldv,newv)用于将区间\([begin,end)\)内的oldv全部替换成newv。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//遍历容器的模板函数
template<typename Iter>
void list_elements(Iter begin, Iter end){
while(begin!=end){
cout<<*begin<<" ";
begin++;
}
cout<<endl;
}
int main()
{
const int N = 10;
int a[N] = {1,2,3,4,5,5,6,7,8,9};
vector<int> ve(a,a+N);
list_elements(a,a+N);
replace(a,a+N,5,-1);
list_elements(a,a+N);
list_elements(ve.begin(),ve.end());
replace(ve.begin(),ve.end(),5,-1);
list_elements(ve.begin(),ve.end());
return 0;
}2.replace_if
replace_if(begin,end,function,newv)用于将区间\([begin,end)\)内的符合条件的元素（作为参数调用function函数返回值为true）全部替换成newv。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//遍历容器的模板函数
template<typename Iter>
void list_elements(Iter begin, Iter end){
while(begin!=end){
cout<<*begin<<" ";
begin++;
}
cout<<endl;
}
//判断奇数
bool odd(const int &x){
return x%2!=0;
}
int main()
{
const int N = 10;
int a[N] = {1,2,3,4,5,5,6,7,8,9};
vector<int> ve(a,a+N);
list_elements(a,a+N);
replace_if(a,a+N,odd,-1);
list_elements(a,a+N);
list_elements(ve.begin(),ve.end());
replace_if(ve.begin(),ve.end(),odd,-1);
list_elements(ve.begin(),ve.end());
return 0;
}四、复制
1.copy
copy(begin,end,dest_begin)用于将区间\([begin,end)\)内的所有元素依次复制到以dest_begin开头的序列中：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//遍历容器的模板函数
template<typename Iter>
void list_elements(Iter begin, Iter end){
while(begin!=end){
cout<<*begin<<" ";
begin++;
}
cout<<endl;
}
int main()
{
const int N = 10;
int a[N] = {1,2,3,4,5,6,7,8,9,10};
vector<int> ve(a,a+N);
int b[N];
copy(a,a+N,b);
list_elements(b,b+N);
vector<int> ve2;
ve2.resize(ve.size());
copy(ve.begin(),ve.end(),ve2.begin());
list_elements(ve2.begin(),ve2.end());
return 0;
}2.copy_backward
copy_backward(begin,end,dest_end)用于将区间\([begin,end)\)内的所有元素依次复制到另一个序列\([dest\_end-end+begin,dest\_end)\)，dest_end是目标序列最后一个元素的下一个位置。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//遍历容器的模板函数
template<typename Iter>
void list_elements(Iter begin, Iter end){
while(begin!=end){
cout<<*begin<<" ";
begin++;
}
cout<<endl;
}
int main()
{
const int N = 10;
int a[N] = {1,2,3,4,5,6,7,8,9,10};
vector<int> ve(a,a+N);
int b[N];
copy_backward(a,a+N,b+N);
list_elements(b,b+N);
vector<int> ve2;
ve2.resize(ve.size()+5);
copy_backward(ve.begin(),ve.end(),ve2.end());
list_elements(ve2.begin(),ve2.end());
return 0;
}如果是将一个序列的第一个区域的元素拷贝到该序列另一个区域，并且这两个区域有重叠的时候，copy函数和copy_backward的效果是不一样的。
五、生成和异变
1.fill
fill(begin,end,x)用于将区间\([begin,end)\)填充为x，也就是所有元素赋值为x。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//遍历容器的模板函数
template<typename Iter>
void list_elements(Iter begin, Iter end){
while(begin!=end){
cout<<*begin<<" ";
begin++;
}
cout<<endl;
}
int main()
{
const int N = 10;
int a[N] = {1,2,3,4,5,6,7,8,9,10};
fill(a,a+5,0);
list_elements(a,a+N);
vector<int> ve(10,-1);
list_elements(ve.begin(),ve.end());
fill(ve.begin()+2,ve.end(),0);
list_elements(ve.begin(),ve.end());
return 0;
}2.fill_n
fill_n(begin,n,x)用于将区间\([begin,begin+n)\)填充为x，也就是所有元素赋值为x（将begin为首的序列的前n个元素都赋值成x）。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//遍历容器的模板函数
template<typename Iter>
void list_elements(Iter begin, Iter end){
while(begin!=end){
cout<<*begin<<" ";
begin++;
}
cout<<endl;
}
int main()
{
const int N = 10;
int a[N] = {1,2,3,4,5,6,7,8,9,10};
fill_n(a,5,0);
list_elements(a,a+N);
vector<int> ve(10,-1);
list_elements(ve.begin(),ve.end());
fill_n(ve.begin()+2,8,0);
list_elements(ve.begin(),ve.end());
return 0;
}3.for_each
for_each(begin,end,function)用于将区间\([begin,end)\)的每个元素作为参数调用function函数。如果function函数参数是引用形式，在function内部修改参数变量的值会导致序列中的元素值也发生变化。
#include<iostream>
#include<algorithm>
using namespace std;
//遍历容器的模板函数
template<typename Iter>
void list_elements(Iter begin, Iter end){
while(begin!=end){
cout<<*begin<<" ";
begin++;
}
cout<<endl;
}
void print(const int &x){
cout<<x<<endl;
}
//参数是引用形式，在函数体内部修改了引用参数的值
void square(int &x){
x = x*x;
}
int main()
{
const int N = 10;
int a[N] = {1,2,3,4,5,6,7,8,9,10};
for_each(a,a+N,print);
for_each(a,a+N,square);
list_elements(a,a+N);
return 0;
}4.transform
transform(begin,end,dest_begin,function)用于将区间\([begin,end)\)内的所有元素作为参数调用function函数的返回值依次复制到以dest_begin开头的序列中：
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
//遍历容器的模板函数
template<typename Iter>
void list_elements(Iter begin, Iter end){
while(begin!=end){
cout<<*begin<<" ";
begin++;
}
cout<<endl;
}
int square(const int &x){
return x*x;
}
char upper(const char &ch){
if(ch>='a' && ch<='z') return ch-('a'-'A');
return ch;
}
int main()
{
const int N = 10;
int a[N] = {1,2,3,4,5,6,7,8,9,10};
transform(a,a+N,a,square);
list_elements(a,a+N);
string s = "hello world";
cout<<s<<endl;
transform(s.begin(),s.end(),s.begin(),upper);
cout<<s<<endl;
//使用内置函数::tolower
transform(s.begin(),s.end(),s.begin(),::tolower);
cout<<s<<endl;
//使用内置函数::toupper
transform(s.begin(),s.end(),s.begin(),::toupper);
cout<<s<<endl;
return 0;
}