交换、删除、替换、生成算法

一、交换算法

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());
    auto 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());
    auto 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());
    auto 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;
}