网站建设情况汇报,做企业网站不好混,46设计网,网站代码需要注意什么1.概述根据名字就知道如何使用相关算法#xff0c;比如copy函数#xff0c;就是复制的意思#xff0c;它需要一个范围#xff0c;以及要复制的位置copy(begin, end, container_begin);#include iostream
#includevector
#includealgorithm
#includ…1.概述根据名字就知道如何使用相关算法比如copy函数就是复制的意思它需要一个范围以及要复制的位置copy(begin, end, container_begin);#include iostream
#includevector
#includealgorithm
#includeiterator
using namespace std;int main(int argc, char** argv) {
vectorint data(10);//创建一个大小为10的向量
cout data.capacity() endl;
int arr[10] {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
copy(begin(arr), end(arr), data.begin());//copy(起点,终点,容器开头);
for(auto it : data){
cout it ;
}
cout endl;
return 0;
}copy函数需要容器的起点这样就要求我们提前设定容器的大小比如上面的代码设定了容器的大小为10有时候我们并知道需要copy多少数据所以我们可以使用back_inserter()这个函数返回一个特殊的迭代器插入的时候容器会自动扩大插入到前面数据的后面#include iostream
#includevector
#includealgorithm
#includeiterator
using namespace std;
int main(int argc, char** argv) {
vectorint data;
int d[] {1,2,3,4,5,6,7,8,9,10};
copy(begin(d), end(d), back_inserter(data));
for(int i : d){
cout i endl;
}
return 0;
}(1)判定函数很多算法需要一个返回bool类型的函数根据函数来自定义算法的工作过程比如remove_copy_if()除了限定范围还要指定函数返回为false的数据会被复制#include iostream
#includevector
#includealgorithm
#includeiterator
using namespace std;
bool compare(int x){
return x 6;
}
int main(int argc, char** argv) {
vectorint data;
int d[] {1,2,3,4,5,6,7,8,9,10};
remove_copy_if(begin(d), end(d), back_inserter(data), compare);//复制小于6的数据
for(int i : data){
cout i endl;
}
return 0;
}类似的还有replace_copy_if(起点终点容器起点函数替代数据)#include iostream
#includevector
#includealgorithm
#includeiterator
using namespace std;
bool compare(int x){
return x 6;
}
int main(int argc, char** argv) {
vectorint data;
int d[] {1,2,3,4,5,6,7,8,9,10};
replace_copy_if(begin(d), end(d), back_inserter(data), compare, 10);
for(int i : data){
cout i endl;
}
return 0;
}而replace_if则是改变原始的数据而不是输出到新的容器#include iostream
#includevector
#includealgorithm
#includeiterator
using namespace std;
bool compare(int x){
return x 6;
}
int main(int argc, char** argv) {
vectorint data;
int d[] {1,2,3,4,5,6,7,8,9,10};
replace_if(begin(d), end(d),compare, 10);
for(int i : d){
cout i endl;
}
return 0;
}(2)流迭代器流迭代器把数据当作流进行操作#include iostream
#includevector
#includealgorithm
#includeiterator
using namespace std;
bool compare(int x){return x 6;
}
int main(int argc, char** argv)
{vectorint data;int d[] {1,2,3,4,5,6,7,8,9,10};copy(begin(d), end(d), ostream_iteratorint(cout,\n));//直接输出到coutreturn 0;
}输出流迭代器重载拷贝-复制操作符该重载操作符向相应的流写入数据,当然我们也可以使用其他的流来操作数据比如输入流来操作输入数据到某个容器或者相应的流.2.函数对象有时候需要根据对象调用函数以对象名作为函数进行调用这样做的好处是对于需要多个参数才能实现的功能可以通过函数对象实现#include iostream
#includevector
#includealgorithm
#includeiterator
#includefstream
using namespace std;
class MyFunction{
private:
int value;
public:
MyFunction(int i):value(i){}
bool operator()(int x){
return x value;
}
};
int main(int argc, char** argv){
int arr[] {1,2,3,4,5,6,7,8,9,10};
vectorint data;
MyFunction fun(5);//函数对象
remove_copy_if(begin(arr), end(arr), back_inserter(data), fun);//复制小于等于5的数据
for(int i : data){
cout i ;
}
}2.1自动创建函数对象头文件functional定义了大量的通用的函数对象其中函数对象适配器可以调整函数对象。比如greater是一个二元函数对象也就是有两个参数当第一个参数大于第二个参数时返回true从greater重写上面的程序还不够需要函数对象适配器调整参数这里使用bind2nd可以调整greater函数的第二个参数#include iostream
#includevector
#includealgorithm
#includeiterator
#includefstream
using namespace std;
int main(int argc, char** argv){int arr[] {1,2,3,4,5,6,7,8,9,10};vectorint data;remove_copy_if(begin(arr), end(arr), back_inserter(data), bind2nd(greaterint(),5));for(int i : data){cout i ;}return 0;
}bind2nd创建一个binder2nd函数对象这个对象储存和传递两个参数给bind2nd第一个参数是二元函数或者函数对象。这里的函数不能任意定义必须是按照一种特殊的形式来定义。int arr[] {1,1,1,4,5,6,7,8,9,10};
vectorint data;
greaterint g;
auto b bind2nd(g, 5);
cout count_if(begin(arr), end(arr), b) endl;equal_to是一个标准二元函数对象not1是一个函数对象适配器它对一元函数对象的值进行设置C提供了许多函数对象比如加减乘除取余大于小于不等于等等2.2 可调整的函数对象在前面我们介绍了函数适配器用来调整函数对象的值之所以可以调整是因为他们使用了一套公用的规则比如bind2nd就需要知道函数对象的参数类型和返回类型使用bind2nd来操作自定义的函数对象除非自定义的对象使用C约定的规则否则无法成功对于一元函数对象类型名是argument_type和result_type对于二元函数对象类型名是first_argumen_type和second_argument_type和result_typebind1st的重载函数定义如下typename Op::result_type operator()(const typename Op::second_argument_type x) const为这些类提供类型名的函数对象被称为可调整的函数对象C提供了两个类来提供这些类型程序员自定义的函数对象通过继承的方式可以使用这些类型这两个类分别是unary_function和binary_functionunary_function的定义templateclass arg, class Resultstruct unary_function{typedef Arg argument_type;typedef Result result_type;};binary_function的定义类似不过变成了first_argumen_type和second_argument_type和result_type2.3 函数指针适配器函数可以通过函数名来调用但是有很大的局限性。有时候需要函数指针来调用函数这是可能用到函数指针适配器它可以把函数指针转化为函数对象ptr_fun就是函数指针适配器但是它只能封装一元函数或者二元函数它的定义如下templateclass Arg, class Resultpointer_to_unary_functionArg, Result ptr_fun(Result (*fptr)(Arg){return pointer_to_unary_functionArg, Result(fptr);}函数模板可以推测出函数的返回值类型和函数的参数类型然后返回一个函数对象而pointer_to_unary_function是一个函数对象其定义如下templateclass Arg, class Resultclass pointer_to_unary_function: public unary_functionArg, Result{Result (*fptr)(Arg);//储存函数public:pointer_to_unary_function(Result (*x)(Arg) : fptr(x){}Result operator()(Arg x)const{return fptr;}};结合上面两份代码可知ptr_fun通过接受一个函数推测出函数的类型然后生成一个pointer_to_unary_function函数对象调用对象函数使用这种方法调用函数有一个缺陷就是可能会产生二义性比如函数重载了此刻就需要模板特化使用例子#include iostream
#includealgorithm
#includeiterator
#includevector
#includefunctional
using namespace std;
int isEven(int a){return a % 2 0;
}
int main(int argc, char** argv) {int arr[] {1,2,3,4,5,6,7,8,9,10};vectorintbuf;transform(begin(arr), end(arr), back_inserter(buf), ptr_fun(isEven));for(int i : buf){cout i endl;}return 0;
}for_each函数for_each(起点终点操作)这个函数把一段序列的对象调用到操作上这个操作可以自定义。比如输出一个数组#include iostream
#includealgorithm
#includeiterator
#includevector
#includefunctional
using namespace std;
void print(int a){
cout a endl;
}
int main(int argc, char** argv)
{int arr[] {1,2,3,4,5,6,7,8,9,10};ostream_iteratorint out(cout, );for_each(begin(arr), end(arr), print);return 0;
}我们也可以通过这个方法来实现多态通过mem_fun函数实现另外还有mem_fun_ref。他们之间不同点在于mem_fun需要对象是指针而mem_fun_ref需要对象是普通对象#include iostream
#includealgorithm
#includeiterator
#includevector
#includefunctional
using namespace std;
class Base{
public:virtual void print() 0;virtual ~Base(){}
};class One:virtual public Base{
public:
void print(){cout One endl;
}
};class Two: virtual public Base{
public:void print(){cout Two endl;}
};int main(int argc, char** argv)
{vectorBase* vs;vs.push_back(new One);vs.push_back(new Two);for_each(begin(vs), end(vs), mem_fun(Base::print));//输出 One Two for(Base* i : vs){delete i;}return 0;
}下面作为对比#include iostream
#includealgorithm
#includeiterator
#includevector
#includefunctional
using namespace std;
class Angle{int value;public:Angle(int v): value(v){}void print(){cout value endl;}
};
int main(int argc, char** argv) {vectorAngle* va;for(int i 0; i 5; i){va.push_back(new Angle(i));}for_each(begin(va), end(va), mem_fun(Angle::print));//输出 One Two return 0;
}transform函数起点到终点的序列调用第四个参数的函数保存在第三个参数这个参数一般是序列的首地址generate函数让起点到终点的序列调用第三个参数的函数并且把结果保存在序列中2.4 编写自己的函数对象适配器下面我们写一个程序自动生成一个字符串序列然后在主函数中转化为小数
#include iostream
#includealgorithm
#includeiterator
#includevector
#includefunctional
#includectime
#includecstdlib
#includestring
using namespace std; //生成一个随机的数字字符串
class NumStringGen{const int sz;
public:NumStringGen(int ssz): sz(ssz){}string operator()(){string digits(0123456789);const int ndigits digits.size();string r(sz, );r[0] digits[rand()% (ndigits - 1)] 1; for(int i 0; i sz; i){if(sz 3 i sz/2)r[i] .;elser[i] digits[rand() % ndigits];}return r;}}; //输出整个序列
templateclass Iter
void print(Iter first, Iter last, const char* nm ,const char* sep \n,ostream os cout){if(nm ! 0 *nm ! \0)os nm : sep;typedef typename iterator_traitsIter::value_type T;copy(first, last, ostream_iteratorT(cout, sep));os endl;
} int main(int argc, char** argv) {const int sz 9;vectorstring vs(sz);srand(time(0));NumStringGen fun(sz);//生成字符串结果添加到vs generate(begin(vs), end(vs), fun);//生成
// print(vs.begin(), vs.end());//输出生成的函数 const char* vcp[sz];transform(vs.begin(), vs.end(), vcp, mem_fun_ref(string::c_str)); print(begin(vcp), end(vcp));//将字符换转化为小数vectordouble vd;transform(begin(vcp), end(vcp), back_inserter(vd), atof);print(begin(vd), end(vd));return 0;
}
//我们选生成了对应的字符串序列然后再转化为数字这里我们可以把两个操作合二为一
#include iostream
#includealgorithm
#includeiterator
#includevector
#includefunctional
#includectime
#includecstdlib
#includestring
using namespace std; //生成一个随机的数字字符串
class NumStringGen{const int sz;
public:NumStringGen(int ssz): sz(ssz){}string operator()(){string digits(0123456789);const int ndigits digits.size();string r(sz, );r[0] digits[rand()% (ndigits - 1)] 1; for(int i 0; i sz; i){if(sz 3 i sz/2)r[i] .;elser[i] digits[rand() % ndigits];}return r;}}; //输出整个序列
templateclass Iter
void print(Iter first, Iter last, const char* nm ,const char* sep \n,ostream os cout){if(nm ! 0 *nm ! \0)os nm : sep;typedef typename iterator_traitsIter::value_type T;copy(first, last, ostream_iteratorT(cout, sep));os endl;
} //R是返回值的参数类型E是函数形参类型
templateclass R, class E, class F1, class F2
class unary_composer{F1 f1;F2 f2;
public:unary_composer(F1 fone, F2 ftwo): f1(fone), f2(ftwo){}R operator()(E x){return f1(f2(x));}
};//函数适配器,根据生成一个函数对象然后在对象中调用对象的函数重载
templateclass R, class E, class F1, class F2
unary_composerR, E, F1, F2 compose(F1 f1, F2 f2){return unary_composerR, E, F1, F2(f1, f2);
}int main(){double x composedouble, const string(atof, mem_fun_ref(string::c_str))(12.34);cout x endl;
}总结ptr_fun,mem_fun,mem_fun_refptr_fun针对普通函数 fun()mem_fun针对成员函数但是需要指针调用 p-fun()mem_fun_ref针对成员函数但是不需要指针调用p.fun()下面的代码对上面的代码进行了简单化不需要那么多的类型推断
#include iostream
#includealgorithm
#includeiterator
#includevector
#includefunctional
#includectime
#includecstdlib
#includestring
using namespace std; //生成一个随机的数字字符串
class NumStringGen{const int sz;
public:NumStringGen(int ssz): sz(ssz){}string operator()(){string digits(0123456789);const int ndigits digits.size();string r(sz, );r[0] digits[rand()% (ndigits - 1)] 1; for(int i 0; i sz; i){if(sz 3 i sz/2)r[i] .;elser[i] digits[rand() % ndigits];}return r;}
}; //输出整个序列
templateclass Iter
void print(Iter first, Iter last, const char* nm ,const char* sep \n,ostream os cout){if(nm ! 0 *nm ! \0)os nm : sep;typedef typename iterator_traitsIter::value_type T;copy(first, last, ostream_iteratorT(cout, sep));os endl;
} //使用继承的方式自动推断参数的类型
templatetypename F1, typename F2
class unary_composer: public unary_functiontypename F2::argument_type, typename F1::result_type
{F1 f1;F2 f2;
public:unary_composer(F1 fone, F2 ftwo): f1(fone), f2(ftwo){}typename F1::result_type operator()(typename F2::argument_type x){return f1(f2(x));}
};//函数适配器,根据生成一个函数对象然后在对象中调用对象的函数重载
templateclass F1, class F2
unary_composerF1, F2 compose(F1 f1, F2 f2){return unary_composerF1, F2(f1, f2);
}int main(){const int sz 9;vectorstring vs(sz);srand(time(0));NumStringGen fun(sz);//生成字符串结果添加到vs generate(begin(vs), end(vs), fun);//生成
// print(vs.begin(), vs.end());//输出生成的函数 //将字符换转化为小数vectordouble vd;transform(begin(vs), end(vs), back_inserter(vd), compose(ptr_fun(atof), mem_fun_ref(string::c_str)));print(begin(vd), end(vd));return 0;
}
总结函数对象适配器bind1st对函数的第一个参数设置bind2nd对函数的第二个参数设置使用的方式与自定义的一样都是生成一个函数对象然后调用重载函数3.STL算法简介3.1 迭代器(1)InputIterator 输入迭代器可以使用和*来前向移动也可以使用和!来判断位置(2)OutputIterator 输出迭代器可以和*来前向迭代但是不能使用和!这是因为输入迭代器没有判断末尾的标志这个经常配合back_inserter一起使用back_inserter的返回类型就是这个(3)ForwardIterator 前面两个迭代器只能单独写入或者输出这个迭代器可以同时读写而且可以使用和!还要和*来进行迭代不过这个是前向迭代器只能(4)BidirectionaIterator是一个支持--的ForwordIterator(5)RandomAccessIterator支持一切普通指针的所有操作3.2 填充和生成这些算法能够自动用一个值来填充容器(1) void fill(ForwardIterator first, ForwardIterator last, const T value);容器开头和结尾被指定函数对象填充(2)void file_n(ForwardIterator first, Size n,const T value);容器从开头到第n容器被指定函数对象填充(3)void generate(ForwardIterator first, ForwardIterator last, Generator gen) 容器的对象挨个调用生成器将结果保存在容器的对象中(4)void generate_n(ForwardIterator first, Size n, Generator gen);3.3计数(1)IntergralValue count(InputIterator first, OutputIterator last, const EqualityComparable value);计算first到last等于value的数量(2)IntergralValue count_if(InputIterator first, OutputIterator last,Predicate pred);返回能使pred返回true的元素的个数3.4操作序列(1)OutputIterator copy(InputIterator first, InputIterator last, OutputIterator destination);使用赋值从first到last复制序列到 destination(2) BidirectionaIterator2 copy_backward(BidirectionaIterator1 first, BidirectionaIterator1 last, BidirectionaIterator2 destinationEnd);和copy函数一样但是这个操作是以相反的顺序复制元素destinationEnd是容器的末尾迭代器容器必须有足够的空间 int buf[] {1,2,3,4,5,6,7,8,9,10};vectorint v(10); copy_backward(begin(buf), end(buf), v.end());print(v.begin(), v.end(),V, );cout endl; 输出 1 2 3 4 5 6 7 8 9 10 但是它是从10开始复制倒1(3)void reverse(BidirectionaIterator first, BidirectionaIterator last);反转原序列(4)BidirectionaIterator reverse_copy(BidirectionaIterator first, BidirectionaIterator last, OutputIterator destination);复制反转序列到 destinationint main(){
int buf[] {1,2,3,4,5,6,7,8,9,10};
vectorint v(10);
reverse_copy(begin(buf), end(buf), v.begin());
print(v.begin(), v.end(),, );//输出10 9 8 7 6 5 4 3 2 1
return 0;
}(5)ForwardIterator2 swap_ranges(ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2);交换first和last范围内的元素int main(){int buf[] {1,2,3,4,5,6,7,8,9,10};vectorint v(10);swap_ranges(begin(buf), end(buf), v.begin());print(v.begin(), v.end(),V, );//输出1 2 3 4 5 6 7 8 9 10cout endl;print(begin(buf), end(buf), buf, );//输出 0 0 0 0 0 0 0 0 0 cout endl;
return 0;
}(6)void rorate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);将first到middle的序列放在last后面vectorint v({1,2,3,4,5,6,7,8,9,10});vectorint::iterator it v.begin();
it 2;
rotate(begin(v), it, end(v));
print(v.begin(), v.end(),V, );//输出3 4 5 6 7 8 9 10 1 2
cout endl;(7)OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator destination);作用和上面一样只不过是把结果复制到 destinationint buf[] {1,2,3,4,5,6,7,8,9,10};
vectorint v1;
copy(begin(buf), end(buf), back_inserter(v1));
print(v1.begin(), v1.end(),v1, );//输出1 2 3 4 5 6 7 8 9 10
vectorint::iterator it begin(v1);
it 4;
vectorint v2(10);
rotate_copy(begin(v1),it,end(v1),v2.begin());
print(v1.begin(),v1.end(),v1, );//输出 1 2 3 4 5 6 7 8 9 10
print(v2.begin(),v2.end(),v2, );//输出 5 6 7 8 9 10 1 2 3 4
cout endl;下面的四个算法是排列元素有n个则结果有n!个组合(8).bool next_permutation(BidirectionaIterator first, BidirectionaIterator last);int buf[] {1,2,3,4};
int num 4 * 3 * 2 * 1;
for(int i 0; i num; i){
next_permutation(begin(buf), end(buf));
cout i i1 ;
print(begin(buf),end(buf),buf, );
}输出24种排列,而且是以升序的方式输出(9).bool next_permutation(BidirectionaIterator first, BidirectionaIterator last, StrictWeakOrdering binary_pred);按照上面的是自定义的大于号运算但是也可以用binary_pred定义这是一个自定义的函数对象比如可以设定为greater(10)bool prev_permutation(BidirectionaIterator first, BidirectionaIterator last);(11)bool prev_permutation(BidirectionaIterator first, BidirectionaIterator last, StrictWeakOrdering binary_pred);上面四种算法其实没啥区别第一个是升序排列第三个是降序排列第二四是按照自定义的函数对象要求排列返回值要看是否有各自的前驱或者后驱如果没用则返回false一般来讲是因为排列结束了才会返回false下面两种是随机排列(12)void random_shuffle(RandAccessIterator first, RandAccessIterator end);使用默认的随机发生器它会产生均匀分布的结果int buf[] {1,2,3,4};
for(int i 0; i 5; i){
random_shuffle(begin(buf), end(buf));
print(begin(buf), end(buf),, );//输出的排列会被打乱
}(13)void random_shuffle(RandAccessIterator first, RandAccessIterator end,Predicate pred)使用用户自定义的函数对象下面两个是划分(14).BidirectionaIterator partition(BidirectionaIterator frist, BidirectionaIterator last, predicate pred);序列会按照函数对象pred的要求排列序列元素满足pred要求的排在前面不满足的排列在后面但是原本的相对位置可能会变化下面的函数在实现划分规则的同时相对位置也不会变化函数的返回值是划分位置这个位置前面全都满足pred的要求int buf[] {1,2,3,4,5,6,7,8,9,10};
print(begin(buf),end(buf),, );
vectorint v;
copy(begin(buf), end(buf),back_inserter(v));
vectorint::iterator it partition(begin(v), end(v), bind2nd(greaterint(),6));
cout 分界线: *it endl;
print(v.begin(), v.end(), , );
return 0;(15).BidirectionaIterator stable_partition(BidirectionaIterator frist, BidirectionaIterator last, predicate pred);操作序列有复制划分排列组合交换颠倒。3.5 查找与替换(1) InputIterator find(InputIterator first, InputIterator last, cons EqualityComparable value);查找在first到last范围内等于value 的元素返回第一个等于value的位置如果不存在则返回last的位置,这是一直线性查找的方式(2) InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);和上面那个一样不过这次是要求函数对象,比如greater和less(3)ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);、(4)ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, Predicate pred);struct test{bool operator()(int m, int n){cout m n endl;return m n - 1; }
};
int main(){int buf[] {1,2,3,3,5,6,7,8,9,10};print(begin(buf),end(buf),, );vectorint v;copy(begin(buf), end(buf),back_inserter(v));vectorint::iterator it adjacent_find(v.begin(), v.end(), test());if(it v.end()){cerr not find endl;return 0;}cout *it endl;return 0;
}这两个函数都是查找相邻的两个相等的元素第一个函数是调用operator然后返回第一个元素的位置第二个函数会把相等的相邻元素放入Pred对象中然后返回true或者false如果满足条件则返回第一个元素的位置(5).ForwardIterator find_first_of(ForwardIterator first1, ForwardIterator last1, forward_iterator first2, forward_iterator first2)(6).ForwardIterator find_first_of(ForwardIterator first1, ForwardIterator last1, forward_iterator first2, forward_iterator first2, BinaryPredicate binary_pred);这两个函数也是线性查找查找第二个范围是否出现了第一个范围的元素使用的是operator,找到了则返回第一个序列的找到的位置否则返回第一个序列的end不同之处在于第二个函数会使用自定义个函数对象来定义规则(7)ForwardIterator search(ForwardIterator first1, ForwardIterator last1, forward_iterator first2, forward_iterator first2);(8)ForwardIterator search(ForwardIterator first1, ForwardIterator last1, forward_iterator first2, forward_iterator first2, BinaryPredicate binary_pred);这两个函数也是线性查找查找第二个范围的元素是否在第一个范围的范围内也就是第二个范围是第一个范围的子集而且顺序也要一致第一个函仍然是调用第二个函数按照自定义的方式找到则返回第一个序列找到的位置找不到则返回end位置//v1是v的一个子集int buf[] {1,2,3,3,5,6,1,1,15,10};
print(begin(buf),end(buf),, );
vectorint v;
copy(begin(buf), end(buf),back_inserter(v));
vectorint v2({5,6});
vectorint::iterator b v.begin() 4.;
vectorint::iterator it search(v.begin(),v.end(), v2.begin(), v2.end());
if(it v.end()){
cerr not find endl;
return 0;
}cout *(it 1) endl;//找到了输出6(9)ForwardIterator find_end(ForwardIterator first1, ForwardIterator last1, forward_iterator first2, forward_iterator first2);(10)ForwardIterator find_end(ForwardIterator first1, ForwardIterator last1, forward_iterator first2, forward_iterator first2, BinaryPredicate binary_pred);这两个函数与search函数差不多只不过它查找该自己最后 出现的位置然后返回最后位置的第一个元素的迭代器(11)ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T value);(12)ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count,const T value, BinaryPredicate pred);这两个函数都是在范围里搜索连续count个与value相等的值找到了就返回第一个相等的迭代器找不到则返回last.第二个稍微有点不一样的是需要value同时满足自定义规则pred这是一个函数对象,函数的第二个参数会接受value而第一个参数在first中查找第一个函数的例子int buf[] {1,2,3,3,5,6,1,1,15,10};
vectorint v;
copy(begin(buf), end(buf),back_inserter(v));
print(v.begin(), v.end(),v, );
vectorint::iterator it search_n(v.begin(),v.end(), 2,1);//查找两个连续为1的子序列
if(it v.end()){
cerr not find endl;
return 0;
}
cout *(it) endl;上面的这个程序可以查找到两个连续为1的子序列但是找不到2以上的当count3时则会输出not found第二个函数的例子struct test{
bool operator()(int m, int n){
cout m m value n endl;
return m n - 1;
}
};
int main(){
int buf[] {1,2,3,3,5,6,1,1,15,10};
vectorint v;
copy(begin(buf), end(buf),back_inserter(v));
print(v.begin(), v.end(),v, );
vectorint::iterator it search_n(v.begin(),v.end(), 2,2,test());
if(it v.end()){
cerr not find endl;
return 0;
}
cout *(it) endl;
}test的条件时m n-1;则程序会令n value也就是2 然后查找有没有连续的两个数字满足这个条件里面只有一个子集满足也就是11(13) ForwardIterator min_element(ForwardIterator first, ForwardIterator last)(14)ForwardIterator min_element(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);第一个函数在范围内查找最小值最小值可能有多个但是返回第一个位置的迭代器这个函数使用的时operatorint buf[] {1,2,3,3,5,6,1,1,15,10};
vectorint v;
copy(begin(buf), end(buf),back_inserter(v));
print(v.begin(), v.end(),v, );
vectorint::iterator it min_element(v.begin(),v.end());
if(it v.end()){
cerr not find endl;
return 0;
}
cout *(it) endl;
//输出1 第二个函数会使用自定义的比较规则struct test{
bool operator()(int m, int n){
cout m m value n endl;
return m n;
}
};
int main(){
int buf[] {13,2,3,3,5,6,1,1,15,10};
vectorint v;
copy(begin(buf), end(buf),back_inserter(v));
print(v.begin(), v.end(),v, );
vectorint::iterator it min_element(v.begin(),v.end(),test());
if(it v.end()){
cerr not find endl;
return 0;
}
cout *(it) endl;
}我在这里自定义了比较规则使用test函数对象且没用比较符,而是则会查找与第一个元素相等的位置但是总是返回那个元素的位置没意义的程序只是解释这个函数的运算规则(13) ForwardIterator max_element(ForwardIterator first, ForwardIterator last)(14)ForwardIterator max_element(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);和上面一样的只不过时查找最大值了。(15)void replace(ForwardIterator first, ForwardIterator last, const T old_value, const T new_value);(16)void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T new_value);(17)OutputIterator replace_copy(ForwardIterator first, ForwardIterator last, OutputIterator result,const T old_value, const T new_value );(18)OutputIterator replace_copy_if(ForwardIterator first, ForwardIterator last, OutputIterator result,Predicate pred, const T new_value );看过前面的算法形势应该不难理解这几个算法的意义这四个算法是替代算法第一个函数是在范围内将old_value替换为new_value调用的是operator第二个函数是在范围内使用自定义的规则将满足规则的元素替换为new_value第三个函数是将old_value替换为new_value然后把结果输入到result第四个函数是将满足自定义条件的元素替换为new_value,然后把结果复制到result前两个函数会对原序列更改 后两个不会对原序列修改而是把结果复制到新的序列int buf[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
vectorint v;
copy(begin(buf), end(buf),back_inserter(v));//复制原序列
print(v.begin(), v.end(),v, );
vectorint v1(v);
vectorint v2(v);
vectorint v3;
vectorint v4;
replace(v.begin(), v.end(), 3, 0);//将v的3替换为0
print(v.begin(), v.end(),v, );
replace_if(v1.begin(), v1.end(), bind2nd(lessint(), 5), 0);//将v1小于5的数字替换为0
print(v1.begin(), v1.end(),v1, );
replace_copy(v2.begin(), v2.end(), back_inserter(v3), 4, 0);//将v2等于4的元素替换为0并且复制到v3
print(v2.begin(), v2.end(),v2, );//v2不变
print(v3.begin(), v3.end(),v3, );//v3变换
replace_copy_if(v2.begin(), v2.end(), back_inserter(v4), bind2nd(greaterint(),3), 0);//将v2大于3的元素替换为0
print(v2.begin(), v2.end(),v2, );//v2不变
print(v4.begin(), v4.end(),v4, );//v4变化 3.6 比较范围(1) bool equal(InputIterator first1, InputIterator last1, InputIterator first2);(2)bool equal(InputIterator first1, InputIterator last1, InputIterator first2, BinaryPredicate BinaryPredicate binary_pred)这个有点类似于search但是search需要两个范围查找第二个范围在第一个范围出现的位置但是这两个函数需要两个相等的范围指定了第一个范围和第二个范围的开头这是因为第二个范围需要第一个范围来设定。如果找到了则返回true第一个函数调用的是operator第二个函数调用的是自定义规则(3)bool lexicographical_compare(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2);(4)bool lexicographical_compare(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, BinaryPredicate binary_pred);这两个函数是按照字典比较的顺序来判断第一个范围是否小于第二个范围如果小于则返回true,两个范围不需要相等char str1[] abc;
char str2[] abcd;
vectorchar v1;
vectorchar v2;
copy(begin(str1), end(str1), back_inserter(v1));
copy(begin(str2), end(str2), back_inserter(v2));
cout lexicographical_compare(v1.begin(),v2.end(),v2.begin(),v2.end());
//输出1(5)pairInputIterator,InputIterator mismatch(InputIterator first1, InputIterator last1, InputIterator first2);(6)pairInputIterator,InputIterator mismatch(InputIterator first1, InputIterator last1, InputIterator first2, BinaryPredicate binary_pred);mismatch是比较两个序列不同的部分同样需要两个长度相等的序列然后找出序列不同的位置返回值是pair这是一个模板类成员是两个迭代器一个是first,另一个是second返回值pair第一个值first指向第一个序列找到的地方second指向第二个序列找到的地方string str1 abcdefg;
string str2 abcdsss;
pairstring::iterator, string::iterator it mismatch(str1.begin(), str1.end(),str2.begin());
cout 第一个位置 *it.first endl;
cout 第二个位置 *it.second endl;3.7 删除删除算法的参数是迭代器。对于固定的数组来讲是无法删除掉已经存在的空间的所以删除算法会把删除的对象放在数组后面而把没删除的对象放在前面然后返回一个新的末尾迭代器。这样从但是对于可变大小的序列则能够使用erase这样的算法来删除。(1).ForwardIterator remove(ForwardIterator first, ForwardIterator last, constT value);(2).ForwardIterator remove(ForwardIterator first, ForwardIterator last, predicate pred);(3).ForwardIterator remove_copy(InputIterator first, InputIterator last, OutputIterator result, constT value);(4).ForwardIterator remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, predicate pred);//1.remove
int buf[] {1,2,3,4,5,6,7,8,9,10};
auto ptr remove(begin(buf), end(buf), 6);
print(begin(buf), ptr(buf),, );
print(begin(buf),end(buf),, );//这里会输出1 2 3 4 5 7 8 9 10 10 //2.remove_if
int buf[] {1,2,3,4,5,6,7,8,9,10};
auto ptr remove_if(begin(buf), end(buf), test());
print(begin(buf), ptr,, );
print(begin(buf), end(buf), , );其他的两种没有什么区别(5). ForwardIterator unique(ForwardIterator first, ForwardIterator last);(6). ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred);(7). ForwardIterator unique_copy(ForwardIterator first, ForwardIterator last, OutputIterator result);(8). ForwardIterator unique_copy(ForwardIterator first, ForwardIterator last, OutputIterator result, BinaryPredicate binary_pred);这是一种删除相邻值相等只保留一个相等元素的算法如果要清除序列所有的相等的值最好先进行排序。int buf[] {1,2,2,4,5,6,7,8,9,10};
auto ptr unique(begin(buf), end(buf));
print(begin(buf), ptr,, );
print(begin(buf), end(buf), , );3.8.排序(1)void sort(RandAccessIterator first, RandAccessIterator last);(2)void sort(RandAccessIterator first, RandAccessIterator last, StrictWeakOrdering binary_pred);(3)void stable_sort(RandAccessIterator first, RandAccessIterator last);(4)void stable_sort(RandAccessIterator first,RandAccessIterator last, StrictWeakOrdering binary_pred);默认为升序排列sort不是稳定排序他可能交换相等元素的位置stable_sort为稳定排序保存相等元素的原位。(5)partial_sort(RandAccessIterator first, RandAccessIterator middle, RandAccessIterator last);(6)partial_sort(RandAccessIterator first, RandAccessIterator middle, RandAccessIterator last, StrictWeakOrdering binary_pred);对[first, end]进行部分的排序将排序的结果放入[first, middle)中而对于剩下的部分则不保证排序结果(7)RandAccessIterator partial_sort_copy(RandAccessIterator first, RandAccessIterator last, RandAccessIterator Result_first, RandAccessIterator Result_last);(8)RandAccessIterator partial_sort_copy(RandAccessIterator first, RandAccessIterator last, RandAccessIterator Result_first, RandAccessIterator Result_last, StrictWeakOrdering binary_pred);对first和last范围的序列排序并且复制到Result_first到Result_last中如果Result_first-Result_last的范围比first-last要大则只使用一部分排序并且复制(9)void nth_element(RandAccessIterator first, RandAccessIterator nth, RandAccessIterator last);(10)void nth_element(RandAccessIterator first, RandAccessIterator nth, RandAccessIterator last, StrictWeakOrdering binary_pred);这个算法与 partial_sort有点类似但是它比partial_sort做得工作少得多。它以nth为界比这个数小则放在左边比这个数大则放在右边int buf[] {1,2,3,4,5,6,7,8,9,10};
random_shuffle(begin(buf), end(buf));
print(begin(buf), end(buf), 原序列, );
vectorint v(begin(buf), end(buf));
vectorint v1(begin(buf), end(buf));
vectorint::iterator it v.begin();
it 4;
partial_sort(v.begin(), it, v.end());
print(v.begin(),v.end(),partial_sort, );
vectorint::iterator v_it v1.begin() 4;
nth_element(v1.begin(), v_it, v1.end());
print(v1.begin(), v1.end(), nth_element, );3.9 排序之后的操作算法以下的算法全都是排序之后的操作如果对没有排序的序列进行操作结果将会是未定义的3.9.1.二分查找法下面全部函数都是二分法这些函数都是成对的第一个是默认使用operator第二个是自定义的(1)bool binary_search(ForwardIterator first, ForwardIterator last, const T value);(2)bool binary_search(ForwardIterator first, ForwardIterator last, const T value, StrictWeakOrdering binary_pred);这个算法是查找value是否存在存在则返回true(3)ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T value);(4)ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T value,StrictWeakOrdering binary_pred);这个算法返回value在[first, last]中第一次出现的位置如果value不存在则返回它应该在这个范围中的位置。int buf[] {1,2,3,3,5,6,7,8,9,10};
auto it lower_bound(begin(buf), end(buf),3);
cout *it endl;
it lower_bound(begin(buf), end(buf),4);
cout *it endl;//输出5(3)ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T value);(4)ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T value,StrictWeakOrdering binary_pred);返回value后一个位置如果value不存在则返应该出现的位置int buf[] {1,2,3,3,5,6,7,8,9,10};
auto it upper_bound(begin(buf), end(buf),3);
cout *it endl;
it upper_bound(begin(buf), end(buf),3);
cout *it endl;(5)pairForwardIterator, ForwardIterator equal_range(ForwardIterator first, ForwardIterator last, const T value);(6)pairForwardIterator, ForwardIterator equal_range(ForwardIterator first, ForwardIterator last, const T value, StrictWeakOrdering binary_pred);这个函数是lower_bound和upper_bound的结合first指向value第一次出现的位置second指向value最后一次出现的位置3.9.2 合并算法下面几个算法是合并算法下面的函数也是成对的合并之后的序列仍然是排序过的(1). OutputIterator merge(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result);(2). OutputIterator merge(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result, StrictWeakOrdering binary_pred);将[first1,last1],[first2, last2]复制到result中结果将是升序的自定义的不一样(3)void inplace_merge(BidirectionaIterator first, BidirectionaIterator middle, BidirectionaIterator last );(4)void inplace_merge(BidirectionaIterator first, BidirectionaIterator middle, BidirectionaIterator last, StrictWeakOrdering binary_pred);这里假定[first, middle)和[middle,last)来自同一个序列已排序好的然后把结果保存在[first,last],则原序列为升序的序列3.9.3 集合算法对已排序的序列进行集合操作输出的结果仍然是排序好的1.包含(1).bool includes(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2);(2).bool includes(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, StrictWeakOrdering binary_pred);如果[first2, last2)是[first1, last1)的子集则返回true2.并集(3)OutputIterator set_union(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result);(4)OutputIterator set_union(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result);结果保存在result中返回末尾的迭代器,如果某个元素在一个集合中出现多次则result保存出现次数多的集合3.交集(5).OutputIterator set_intersection(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result);(6).OutputIterator set_intersection(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result, StrictWeakOrdering binary_pred);结果保存在result中返回末尾的迭代器如果某个元素在其中一个序列中出现多次则result保存出现次数少的序列4.集合的差(7).OutputIterator set_difference(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result);(8).OutputIterator set_difference(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result, StrictWeakOrdering binary_pred);计算两个范围之间的集合差这个差代表在第一个范围中出现但是不在第二个范围中。如果某个元素多次出现比如在第一个范围中出现n次但是在第二个范围中出先m次则结果中只保存max(n-m,0)次int buf1[] {1,2,3,3,5,6,7,8,9,10};
int buf2[] {1,3,3,100};
vectorint result;
auto ptr set_difference(begin(buf1), end(buf1), begin(buf2), end(buf2), back_inserter(result));
print(result.begin(), result.end(),, );(7).OutputIterator set_symmetric_difference(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result);(8).OutputIterator set_symmetric_difference(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result, StrictWeakOrdering binary_pred);这个差集的结果是相当于二者求并集然后分别求差集的结果也就是result包含的是1.集合1中有的元素但是集合2中没有 2.集合2中有的元素集合1中没有4 堆运算下面每一种算法都成对的出现第一种是默认使用operator第二种是自定义的函数对象1.创建堆(1)void make_heap(RandAccessIterator first, RandAccessIterator last);(2)void make_heap(RandAccessIterator first, RandAccessIterator last, StrictWeakOrdering binary_pred);2.将最后一个元素添加到堆中合适的位置(3)void push_heap(RandAccessIterator first, RandAccessIterator last)(4)void push_heap(RandAccessIterator first, RandAccessIterator last, StrictWeakOrdering binary_pred);这个就相当于添加元素到堆中不过由于是针对序列的序列可能无法再次扩充所有才会没有const T的形式3.获取堆顶元素(5)void pop_heap(RandAccessIterator first, RandAccessIterator last)(6)void pop_heap(RandAccessIterator first, RandAccessIterator last, StrictWeakOrdering binary_pred);堆顶的元素成为了first-1而原来的堆顶到了序列的末尾4.堆排序这是对已经存在的堆进行的排序对于排序之后的序列,它将不在是堆所以使用pop_heap和push_pop毫无意义(7)void sort_heap(RandAccessIterator first, RandAccessIterator last);(8)void sort_heap(RandAccessIterator first, RandAccessIterator last, StrictWeakOrdering binary_pred);int buf[] {1,2,3,3,5,6,7,8,9,10};
vectorint result;
random_shuffle(begin(buf), end(buf));//随机化
copy(begin(buf), end(buf), back_inserter(result));
print(result.begin(), result.end(),result原始数据, );
make_heap(result.begin(), result.end()-1);//[first, end-1)转化为堆
print(result.begin(), result.end(),对[first, end-1)转化为堆, );
push_heap(result.begin(), result.end());//将序列最后一个元素添加到堆中
print(result.begin(), result.end(),添加末尾元素到堆, );
vectorint v(result);//复制堆
pop_heap(result.begin(), result.end());//将序列最后一个元素添加到堆中
print(result.begin(), result.end(),堆顶元素出堆, ) ;
sort_heap(v.begin(), v.end());
print(v.begin(), v.end(),对堆进行排序, ) ;5 对某一范围的所有元素进行运算(1).UnaryFunction for_each(InputIterator first, InputIterator last, UnaryFunction f);(2).OutputIterator transform(InputIterator first. InputIterator last, OutputIterator result, UnaryFunction f);(3).OutputIterator transform(InputIterator first. InputIterator last,InputIterator first2, OutputIterator result, UnaryFunction f);for_each函数执行的是f(*first);他会丢弃掉的函数的返回值但是会把函数给返回过来程序员可以通过返回的函数对象来获取状态第一个transform执行的是f(*first),并且把结果保存在result中第二个函数是执行f(*first1,first2);两个序列的范围要相等第二个序列的范围由第一个决定 6.数值计算1.求和(1)T accumulate(InputIterator first, InputIterator last, T result); 执行的过程是 result *first(2)T accumulate(InputIterator first, InputIterator last,T result, BinaryPredicate f);执行过程是 f(result, *first)返回值是运算的结果struct f{int operator()(int y,int x){y x*x;return y;}
};
int main(int argc, char** argv) {int buf[] {1,2,3,4,5,6,7,8,9,10};int sum 0;sum accumulate(begin(buf), end(buf), 0);cout sum endl;//55sum accumulate(begin(buf), end(buf), 0, f());//f(0, buf[i])cout sum endl;//1 4 9 16 ... 100return 0;
}2.内积(3).T inner_product(InputIterator first1, InputIterator last1, InputIterator first2, T init);(4).T inner_product(InputIterator first1, InputIterator last1, InputIterator first2, T init, BinaryFunction op1, BinaryFunction op2);init代表一个初始值op1代替了加法op2代替乘法第一种默认的内积算法是 (*first1) * (*first2)那么第二种是 op1(init,op2(first1,first2));返回值是运算的结果struct a{int operator()(int x, int y){//这里x使用引用是因为这个值会被累加必须保留cout x y endl;x x y;return x;}
};
struct m{int operator()(int x, int y){cout x * y endl;return x * y;}
};
int main(int argc, char** argv) {int buf[] {1,2,3,4,5,6,7,8,9,10};int arr[] {1,1,1,1,1,1,1,1,1,1};int sum inner_product(begin(buf), end(buf), begin(arr), 0);cout sum endl;sum inner_product(begin(buf), end(buf), begin(arr), 0, a(), m());cout sum endl;return 0;
}3.部分和(5)OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result);(6)OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);这个累积和与一般的不一样它是一种斐波拉契模式的累计返回值为result容器的末尾4.相邻差(7)OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result);(8)OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);第一个元素不变其他都是后面一个元素减去前一个元素templateclass Iter
void print(Iter first, Iter last,
const char* nm ,
const char* sep \n,
ostream os cout)
{if(nm ! 0 *nm ! \0)os nm : sep;typedef typename iterator_traitsIter::value_type T;copy(first, last, ostream_iteratorT(cout, sep));os endl;
}
struct m{int operator()(int x, int y){return x * y;}
};
int main(int argc, char** argv) {int buf[] {1,2,3,4,5,6,7,8,9,10};vectorint result;adjacent_difference(begin(buf), end(buf), back_inserter(result));print(result.begin(), result.end(), , );result.clear();adjacent_difference(begin(buf), end(buf), back_inserter(result), m());//自定义计算方法变成了后一个数字乘以前一个数字print(result.begin(), result.end(), , );return 0;
}7. 通用实用工具1. 关联对象templateclass T1, class 2 struct pair//关联对象的定义创建一个关联对象可以使用make_pair(const T1. const T2);获取关联对象可以使用first和second;2.两个迭代器的之间的距离计算需要迭代多少次difference_type distance(InputIterator first, InputIterator last);返回值一般是整型3.给容器创建迭代器用于插入back_insert_iteratorContainer back_inserter(Container x);front_insert_iteratorContainer front_inserter(Container x);insert_iteratorContainer inserter(Container x, Iterator i);4.返回较小值const T min(const T, const T);5返回较大值const T max(const T, constT);6.交换值void swap(Ta , T b);每一种容器实际上都有自己的特化版本的交换算法最好用特化版的void iter_swap(ForwardIterator a, ForwardIterator b);
