6.算法
（1）算法介绍
（1）什么是算法
所谓算法就是数据的具体处理方式，在程序中算法的常见组织形式就是
函数，单个的子函数就是一个小型的算法单元。
（2）c++中涉及的算法有两类
（1）c++函数库提供的算法函数（现成可用的算法）
（1）成员算法函数
所有的容器的都有自己的成员算法函数，比如vector/list/map都提供了
swap算法函数。
除此外C++中所有类库提供的类，比如string/array都有成员算法。
成员算法的特点是，成员算法的操作几乎只与当前类有关。
（2）全局算法
c++中实现了大量的全局算法，这些全局算法的特点就是，可以针对很多
类型的数据操作，几乎都是利用函数模板实现，具有高度的抽象性，与具
体的数据类型无关。
c++的STL模板库就提供了专门针对容器的全局算法函数。
（2）自定义算法
（1）c++编程的工作是什么
编写各种算法函数，定义类只是实现各种成员算法的封装的一种手段，整个
c++程序真正核心是各种算法函数。
（2）全局算法和成员算法
（1）与类相关的就写为成员算法函数
（2）超脱各种类类型的，就写成全局算法，这一点在讲函数时就已经提到过。
（3）操作STL容器时涉及的算法
（1）使用容器成员算法
（2）STL全局算法
（3）自定义自己的针对这些容器操作的算法函数（成员/全局）
也就是说我们可以通过容器提供的迭代器遍历，自己实现对容器的增加/删除/查找/
修改/排序等算法，但不提倡这样的做法。
注意：如果使用STL提供的外部算法函数的话，必须包含<algorithm>头文件。
（2）STL全局算法大致有三类
（1）查找类
find()，find_end()，adjacent_find()，count(), mismatch(),
seaech(), equal()。
（2）修改类
swap(), copy(), transform(). replace(), remove(), reverse(),
rotate(), fill(), random_shffle()。
（3）排序类
sort() stable_sort(), binary_search(), merage(), min(),
max()。
（3）查找类算法
（1）常用全局算法函数
find()：只有一个函数模板
函数模板：
template <class InputIterator, class T>
InputIterator find ( InputIterator first, InputIterator last, const T& value );
功能：查找[first,last)之间是否有value，没有就返回end()。
find_if()：只有一个模板
template <class InputIterator, class Predicate>
InputIterator find_if ( InputIterator first, InputIterator last, Predicate pred );
功能：根据自定义函数进行比较查找。由于该函数默认只允许一个参数。
为了让比较更为灵活，往往需要定义函数类类型（或者利用仿函数和绑定实现也可以，
具体请看例子）。
find_end()：提供两个函数模板
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_end ( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2 );
功能：在[ForwardIterator1,ForwardIterator2)查找[first2, last2)中
任何一个元素出现的最后位置，返回指向该位置的迭代器。
template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
ForwardIterator1 find_end ( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2.
BinaryPredicate pred);
功能：在[ForwardIterator1,ForwardIterator2)查找[first2, last2)，但是
多了一个参数，可以用于传递一个比较函数的地址。
find_first_of：功能与模板和find_end相似，只是返回的是第一次出现的位置的
迭代器。
adjacent_find()：有两个模板
template <class ForwardIterator>
ForwardIterator adjacent_find ( ForwardIterator first, ForwardIterator last );
功能：查询相邻两个元素是否相等，如果相等就返回指向第一个元素的
迭代器。
template <class ForwardIterator, class BinaryPredicate>
ForwardIterator adjacent_find ( ForwardIterator first, ForwardIterator last,
BynaryPredicate pred );
功能：查询相邻两个元素是否相等，如果相等就返回指向第一个元素的
迭代器，可以提供自己定义的比较函数。
count()：只有一个函数模板
template <class InputIterator, class T>
typename iterator_traits<InputIterator>::difference_type
count ( ForwardIterator first, ForwardIterator last, const T& value );
功能：在[ForwardIterator1,ForwardIterator2)查找value的出现的次数并返回。
（2）例子：
#include <iostream>
#include <algorithm>
#include<iterator>
#include<list>
using namespace std;
class Student {
public:
Student(const string name=" ", const string num=" "):name(name), num(num) { }
string getname() const { return name; }
string getnum() const { return num; }
private:
string name;
string num;
};
class Compare {
public:
Compare(const Student *stu, int comptype):stu(stu), comptype(comptype) { }
bool operator()(Student *op) {
if(1 == comptype) {
return(op->getname()==stu->getname());
} else if(2 == comptype) {
return(op->getnum()==stu->getnum());
}
}
private:
const Student *stu;
int comptype;
};
bool compare(Student *&op) {
return (op->getname() == "name1");
}
bool compare1(Student *&op1, Student *&op2) {
return (op1->getname() == op2->getname());
}
bool compare2(Student *&op1, Student *&op2) {
if(op1 == op2) return true;
else if(op1->getname() == op2->getname()&&op1->getnum() == op2->getnum()) {
return true;
} else return false;
}
void print_find_element(std::list<Student *>::iterator it, std::list<Student *>::iterator end) {
if(it != end) {
cout <<"查找结果：" <<(*it)->getname()<<" "<<(*it)->getnum()<<endl;
} else cout<<"没有找到"<<endl;
}
int main(void)
{
Student *stu[10] = {NULL};
std::list<Student *>::iterator it;//定义一个空的list，存放的数据类型伟Student *
/* 初始化对象数组 */
for(int i=0; i<sizeof(stu)/sizeof(stu[0]); i++) {
stu[i] = new Student(string("name")+string(1, i+'0'), string("11")+string(1, i+'0'));
}
/* 利用对象数组初始化list */
std::list<Student *> v1(stu, stu+sizeof(stu)/sizeof(stu[0]));
cout<<"使用find查找，由于容器存放的是对象地址，所以需要为对象地址查找 "<<endl;
it = find(v1.begin(), v1.end(), stu[1]);
print_find_element(it, v1.end());
cout<<"\n使用find_if查找，自定义比较函数，在函数中确定查找方式为按名字查找 "<<endl;
it = find_if(v1.begin(), v1.end(), compare);
print_find_element(it, v1.end());
cout<<"\n使用find_if查找，定义比较函数类类型，重写()后按照学号查找 "<<endl;
it = find_if(v1.begin(), v1.end(), Compare(new Student("wwwww", "111"), 2));
print_find_element(it, v1.end());
cout<<"\n使用find_first_of查找[stu+2, stu+5)中某个在list中出现的最开始的位置，自定义比较函数"<<endl;
it = find_first_of(v1.begin(), v1.end(), stu+2, stu+5,compare1);
print_find_element(it, v1.end());
cout<<"\n使用adjacent_find在list中使用自定义比较函数查找否有相等的相邻元素"<<endl;
it = adjacent_find(v1.begin(), v1.end(), compare2);
print_find_element(it, v1.end());
return 0;
}
（4）修改类算法
（1）常见函数
swap()：只有一个函数模板
template <class T> void swap ( T& a, T& b );
功能：交换两个a和b两个容器中的内容。
copy()：只有一个模板
template <class InputIterator, class OutputIterator>
OutputIterator copy ( InputIterator first, InputIterator last, OutputIterator result );
功能：将[InputIterator, OutputIterator)内容复制到result开始的位置。
但是被复制的容器不能为空，比如使用vector和list为空时，必须
是使用resize函数预先开辟元素空间，如果开辟的空间不够只能复制
一部分，如果空间过多，会导致无效内容的存在。
使用copy函数只能实现浅拷贝，如果容器存放的是指针，那么经过copy复制后，
两个容器里面存放的所有指针指向的都是相同的数据空间。
transform()：有两个模板，实现对容器中数据进行指定操作。
前面提到，copy只能浅拷贝，如果希望实现深拷贝，我们就需要使用transform
函数。之所以能够实现深拷贝，是因为我们可以通过指定自定义的函数实现具体
的拷贝过程。
对transform来说，同样要求被复制的容器不能为空，比如vector和list，必须
是使用resize函数开辟元素空间，如果开辟的空间不够只能复制一部分，如果空
间过多，会导致无效内容存在。
template < class InputIterator, class OutputIterator, class UnaryOperator >
OutputIterator transform ( InputIterator first1, InputIterator last1,
OutputIterator result, UnaryOperator op);
功能：对[first1, last1)之间内容做指定的op操作，将结果转存到result容器中，
template < class InputIterator1, class InputIterator2,
class OutputIterator, class BinaryOperator >
OutputIterator transform ( InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, OutputIterator result,
BinaryOperator binary_op );
功能：对[first1, first1)和first2开时的内容进行指定的op运算，结果转存到
result中，要求用于做运算的两个容器内容要想等，否者会抛出异常。
replace()：只有一个模板
template < class ForwardIterator, class T >
void replace ( ForwardIterator first, ForwardIterator last,
const T& old_value, const T& new_value );
功能：将[first, last)之间old_value替换为new_value。
remove()：只有一个模板
template < class ForwardIterator, class T >
ForwardIterator remove ( ForwardIterator first, ForwardIterator last,
const T& value );
功能：将[first, last)之间等于value的数据删除。
remove_if()：只有一个模板
template < class ForwardIterator, class Predicate >
ForwardIterator remove_if ( ForwardIterator first, ForwardIterator last,
Predicate pred );
功能：同remove，但是可以按照自定义的pred的要求删除。
reverse()：只有一个模板
template <class BidirectionalIterator>
void reverse ( BidirectionalIterator first, BidirectionalIterator last);
功能：将[first, last)之间元素顺序颠倒。
rotate()：只有一个模板
template <class ForwardIterator>
void rotate ( ForwardIterator first, ForwardIterator middle,
ForwardIterator last );
功能：将[middle,last)元素旋转到开始位置，middle为第一个元素，将
[first,middle)元素旋转到后面。
比如123456789，以4为middle进行旋转后为456789123。
fill()：只有一个模板
template < class ForwardIterator, class T >
void fill ( ForwardIterator first, ForwardIterator last, const T& value );
功能：使用value填充[first,last)之间内容。
random_shuffle()：有两个模板
template <class RandomAccessIterator>
void random_shuffle ( RandomAccessIterator first, RandomAccessIterator last );
功能：将[first,last)之间的内容按照默认算法进行随机排序。
template <class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle ( RandomAccessIterator first, RandomAccessIterator last,
RandomNumberGenerator& rand );
功能：将[first,last)之间的内容按照rand指定的随机序列号进行随机
重新排序，需要自己实现rand函数。
但是这个函数只能对数组/数组类型的容器如vector操作，对list操作
无效，因为list等其它容器不支持随机访问。
（2）例子
#include <iostream>
#include <algorithm>
#include<iterator>
#include<list>
using namespace std;
class Student {
public:
Student(const string name=" ", const string num=" "):name(name), num(num) { }
void setname(const string name) { this->name = name; }
void setnum(const string num) { this->num=num; }
string getname() const { return name; }
string getnum() const { return num; }
private:
string name;
string num;
};
class Trans_operate {
public:
Trans_operate(const string str=" "):str(str) { }
Student *operator()(Student *op) {
Student *tmp = new Student(op->getname()+str, op->getnum()+str);
return tmp;
}
private:
const string str;
};
class Remove_operate {
public:
Remove_operate(const Student *stu, int optype):stu(stu), optype(optype) { }
bool operator()(Student *op) {
if(1 == optype) return(op->getname()==stu->getname());
else if(2 == optype) return(op->getnum()==stu->getnum());
else return false;
}
private:
const Student *stu;
int optype;
};
int random_fun(int i) {
return (rand()%i);
}
/* 使用迭代器便利map */
template <class Iter> void show_list(Iter first, Iter last) {
for( ;first!=last; first++) {
cout << (*first)->getname() <<endl;
}
}
int main(void)
{
Student *stu[10] = {NULL};
/* 初始化对象数组 */
for(int i=0; i<sizeof(stu)/sizeof(stu[0]); i++) {
stu[i] = new Student(string("name")+string(1, i+'0'), string("11")+string(1, i+'0'));
}
/* 利用对象数组初始化list */
std::list<Student *> l1(stu, stu+sizeof(stu)/sizeof(stu[0]));
std::list<Student *> l2;
cout<<"\n交换l1和l2"<<endl;
swap(l1, l2);
if(!l1.empty()) {
cout<<"显示l1"<<endl;
show_list(l1.begin(), l1.end());
}
else cout<<"l1是空的"<<endl;
if(!l2.empty()) {
cout<<"显示l2"<<endl;
show_list(l2.begin(), l2.end());
}
else cout<<"l2是空的"<<endl;
cout<<"\n交换l1和l2后，l1变成了空，将l2的部分内容复制会l1"<<endl;
cout<<"但是由于l1变成了空，需要使用resize函数开辟需要的元素空间"<<endl;
l1.resize(l2.size()-2);
copy(++l2.begin(), --l2.end(), l1.begin());
cout<<"显示l1"<<endl;
show_list(l1.begin(), l1.end());
cout<<"显示l2"<<endl;
show_list(l2.begin(), l2.end());
cout<<"\n将l1中的对象深拷贝到l3中，需要自定义操作函数类"<<endl;
cout<<"要求l3容器不能为空"<<endl;
std::list<Student *> l3(l1.size());
transform(l1.begin(), l1.end(), l3.begin(), Trans_operate("**"));
cout<<"\n将l3中的[begin(), ++begin())替换l3begin()开始的元素"<<endl;
replace(l1.begin(), l1.end(), *(++l1.begin()), *(++l3.begin()));
cout<<"显示l1"<<endl;
show_list(l1.begin(), l1.end());
cout<<"\n按照条件删除元素"<<endl;
remove_if(l1.begin(), l1.end(), Remove_operate(new Student("name4", "111"), 1));
cout<<"显示l1"<<endl;
show_list(l1.begin(), l1.end());
cout<<"\n将l1[++++++l1.begin(), l1.end())的元素进行反转"<<endl;
reverse(++++++l1.begin(), l1.end());
cout<<"显示l1"<<endl;
show_list(l1.begin(), l1.end());
cout<<"\n将l2[l2.begin(), l2.end())的元素以++++++l2.begin()为中心进行rotate"<<endl;
rotate(l2.begin(), ++++++l2.begin(), l2.end());
cout<<"显示l2"<<endl;
show_list(l2.begin(), l2.end());
cout<<"\n将l2中[++++++l2.begin(), ------l2.end())使用new Student(\"wwwww\", \"999\")填充"<<endl;
fill(++++++l2.begin(), ------l2.end(), new Student("wwwww", "999"));
cout<<"显示l2"<<endl;
show_list(l2.begin(), l2.end());
ptrdiff_t (*p_myrandom)(ptrdiff_t) = random_fun;
cout<<"\n将stu中的元素按照自定义的方式随机化"<<endl;
random_shuffle(stu, stu+sizeof(stu)/sizeof(stu[0]), p_myrandom);
cout<<"显示stu"<<endl;
show_list(stu, stu+sizeof(stu)/sizeof(stu[0]));
return 0;
}
（5）排序相关的算法
（1）常见函数
sort()：有两个模板
template <class RandomAccessIterator>
void sort ( RandomAccessIterator first, RandomAccessIterator last );
功能：将[first，last)之间的内容进行默认的升序排序，但是注意，只有
基本类型有被提供默认的升序排序。
template <class RandomAccessIterator, class Compare>
void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );
功能：将[first，last)之间的内容进行自定义的排序，需要提供比较函数的
函数对象。特别是如果容器中存放的类类型的数据来说，就必须提
供自定义的比较函数对象，否者会导致编译不通过。
注意：
由于sort全局算法函数只支持随机迭代器，所以sort只能对数组和数组类型
的容器比如vetor进行排序。
如果希望对list按照自定义继续宁排序，需要调用list自己成员函数sort。
对于关联容器map来说，只能在存入元素的时候进行排序，寻找一个合适
的位置后将元素插入，所以只能在插入的时候排序，不能进行独立的排序。
stable_sort()：两个模板，与sort功能与参数同，唯一的区别是遇到相等元素时
不会对其进行交换。
search()：有两个模板
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search ( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2 );
功能：在[firs,last)之间查询有没有[first，last2)元素序列，有的话，返回
第一次出现的迭代器。注意与find区别，search查找的是一整块序列，
而find查找的是序列中的一个或者元素有没有在容器中出现。
template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
ForwardIterator1 search ( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2.
BinaryPredicate pred );
功能：与上同，但是可以提供带两个参数的自定义比较函数。具体查阅函数手册
binary_search()：二分法查找，有两个模板
template <class ForwardIterator, class T>
bool binary_search ( ForwardIterator first, ForwardIterator last,
const T& value );
功能：在[first， last)之间搜索value，找到返回true，失败返回false
与前面讲解find_if函数功能基本相同，只是find_if如果成功，返回
的是指向找到元素的迭代器，失败则返回end()。
template <class ForwardIterator, class T, class Compare>
bool binary_search ( ForwardIterator first, ForwardIterator last,
const T& value, Compare comp );
指定比叫函数时，比较函数格式如下：
bool myfunction (int op1,int op2) { return op1>op2); }
其中op2时需要查找的元素。
功能：与上同，但是可以指定自定义比较函数。比较函数格式请查阅手册
merge()：两个模板
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge ( InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result );
功能：将[first1, last1)和[firsr2, last2)之间的内容合并，合并时会
按照默认排序函数进行排序，这只能针对基本类型操作。
template <class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator merge ( InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp );
功能：同上，但是可以指定自定义的比较函数。
备注：
list也提供了一个属于自己的merge成员函数，利用该函数可以将其它链表合并到
自己中。使用全局的merge可以将两个链表合并到第三个链表中。
这二者还有一个区别就是，list的merge函数合并成功后，被合并的list会被清空，
但是全局的merge函数实现合并操作后，被合并的两个list不会被清空。
min()：经过比较后，返回最小值，有两个模板。
template <class T> const T& min ( const T& a, const T& b );
功能：返回最小值，调用默认比较函数（只对基本类型有效）。
template <class T, class Compare>
const T& min ( const T& a, const T& b, Compare comp );
功能：同上，可以提供自定义比较函数，对类类型对象操作时，必须使用
这个模板，因为必须指定比较函数。
max()：功能与模板同min，只是返回的是最大的值。
（2）演示例子
#include <iostream>
#include <algorithm>
#include<iterator>
#include<list>
#include<string.h>
#include<stdio.h>
using namespace std;
class Student {
public:
Student(const string name=" ", const string num=" "):name(name), num(num) { }
void setname(const string name) { this->name = name; }
void setnum(const string num) { this->num=num; }
string getname() const { return name; }
string getnum() const { return num; }
private:
string name;
string num;
};
class Compare {
public:
Compare(int cmptype, int cmpoder):cmpoder(cmpoder), cmptype(cmptype) { }
/* 如果是二分法binary_search函数调用比较函数，那么op2表示需要被查找的元素 */
bool operator()(Student *op1, Student *op2) {
cout <<op1<<endl;
cout <<op2<<endl;
cout <<op1->getname()<<endl;
cout <<op2->getnum()<<endl;
if(1 == cmptype) {//按照名字排序
if(1 == cmpoder) {
return(op1->getname() > op2->getname());
} else if(2 == cmpoder) {
return(op1->getname() < op2->getname());
} else if(3==cmpoder) return(op1->getname() == op2->getname());
}
else if(2 == cmptype) {//按照学号排序
if(1 == cmpoder) {
return(op1->getnum() > op2->getnum());
} else if(2 == cmpoder) {
return(op1->getnum() < op2->getnum());
} else if(3==cmpoder) return(op1->getnum() == op2->getnum());
} else return false;
}
private:
int cmpoder;
int cmptype;
};
/* 使用迭代器便利map */
template <class Iter> void show_list(Iter first, Iter last) {
for( ;first!=last; first++) {
cout << (*first)->getname() << " "<<(*first)->getnum()<<endl;
}
}
int main(void)
{
Student *stu[10] = {NULL};
/* 初始化对象数组 */
for(int i=0; i<sizeof(stu)/sizeof(stu[0]); i++) {
stu[i] = new Student(string("name")+string(1, i+'0'), string("11")+string(1, i+'0'));
}
/* 利用对象数组初始化list */
std::list<Student *> l1(stu, stu+sizeof(stu)/sizeof(stu[0]));
cout<<"\n对stu的内容按照要求排序"<<endl;
sort(stu, stu+sizeof(stu)/sizeof(stu[0]), Compare(2, 2));
show_list(stu, stu+sizeof(stu)/sizeof(stu[0]));
cout<<"\n全局sort不能对list进行排序，对list排序需要调用list的成员函数sort"<<endl;
l1.sort(Compare(1, 1));
show_list(l1.begin(), l1.end());
cout<<"\n在l2中搜索[++++l1.begin(), ------l1.end())区间的内容"<<endl;
std::list<Student*>::iterator it;
it = search(l1.begin(), l1.end(), ++++l1.begin(), ------l1.end(), Compare(2, 3));
if(it!=l1.end()) {
cout <<"找到,第一个元素是："<<endl;
cout <<(*it)->getname()<<" "<<(*it)->getnum() <<endl;
}
cout<<"\n使用二分法在l2中按照要求查找new Student(\"name4\", \"111\")"<<endl;
bool ret = binary_search(l1.begin(), l1.end(), new Student("name4", "111"), Compare(2, 1));
cout << "ret = " << ret << endl;
if(ret) cout <<"找到"<<endl;
else cout <<"未找到"<<endl;
cout << "\n使用全局merge函数，将l1和l2合并到l3中，自定义合并后的排序顺序 " << endl;
std::list<Student *> l2(++++l1.begin(), ------l1.end());
std::list<Student *> l3(l1.size()+l2.size());
Student *stu3[13];
merge(l1.begin(), l1.end(), l2.begin(), l2.end(), l3.begin(), Compare(2, 2));
show_list(l3.begin(), l3.end());
cout << "\n调用l1的merge函数，将l2合并到自己空间中，使用自定义排序函数 " << endl;
l1.merge(l2, Compare(2, 2));
show_list(l1.begin(), l1.end());
cout << "\n比较*l1.begin(), *(++++l1.begin()谁最小，使用自定义比较函数比较"<<endl;
Student *p = min(*l1.begin(), *(++++l1.begin()), Compare(2, 2));
cout << p->getname()<<" "<<p->getnum()<<endl;
cout << "\n比较*l1.begin(), *(++++l1.begin()谁最大，使用自定义比较比较"<<endl;
p = max(*l1.begin(), *(++++l1.begin()), Compare(2, 2));
cout << p->getname()<<" "<<p->getnum()<<endl;
return 0;
}
网友评论