概述:大多数算法都定义在头文件#include<algorithm>,标准库还在#include<numeric>定义了一组数值泛型算法。
泛型算法本身不会执行容器操作,它们只会运行在迭代器之上,执行迭代器的操作
结论:算法永远不会改变底层容器的大小,算法可能改变容器中保存的元素的值或者移动元素,但永远不会直接添加或者删除元素。
!除了少数以外,标准库算法都对一个范围内的元素进行操作,我们将此元素范围称为“输入范围”。接受输入范围的算法总能使用前两个参数
来指定范围,两个参数分别为首元素和尾元素的下一个迭代器。
注意!当算法传递的参数是类时需要注意,因为算法一般内部都有关系运算符来比较,类可能没有重载这个操作,所以会失败!
读算法
1.accumulate
#include <numeric> #include <algorithm> #include <iostream> #include <vector> #include <string> using namespace std; int main() { //accumulate(egin, end, initial_value); vector<int>ivec = {1,2,3,4,5,6,7,8,9,0}; cout << accumulate(ivec.begin(), ivec.end(), 0) << endl; //字符串必须类型相同,如果accumulate中s换为""就会出错,""是const char*类型的,类型不一致 //所以序列中的元素必须和第三个参数相匹配,或者能转换成第三个参数。 string s = ""; vector<string>ivecs = {"hello", "world", "haha"}; cout << accumulate(ivecs.begin(), ivecs.end(), s) << endl; }
!注意
<<1.对于只读不改变的算法我们最好使用a.cbegin( )和a.cend( ),const_iterator类型的迭代器
<<2.!accumulate的第三个参数决定了函数中使用哪个加法运算符以及返回值类型
#include <algorithm> #include <iostream> #include <numeric> #include <vector> int main() { std::vector<double>ivec = {1.1, 1.2, 1.3}; std::cout << accumulate(ivec.begin(), ivec.end(), 0) << std::endl; std::cout << accumulate(ivec.begin(), ivec.end(), 0.0) << std::endl; }
2.equal
只读算法,判断两个序列是否保存相同的值
#include <iostream> #include <string> #include <algorithm> #include <vector> using namespace std; int main() { //equal(a.begin(),a,end(), b.pos); vector<int>ivec1 = {0,1,2,3,4,5,6,7,8,9}; vector<int>ivec2 = {0,1,2,3,4,5,6,7,8,9}; //比较是根据ivec1来比较,ivec1最多有9个元素,如果ivec2少于ivec1个数,返回false,完全匹配返回true cout << equal(ivec1.begin(), ivec1.end(), ivec2.begin()) << endl; cout << equal(ivec1.begin(), ivec1.end(), ivec2.begin()+1) << endl; //元素类型不必完全相同只要能用==比较就行 vector<string>ivecs1 = {"hello", "world", "hehe"}; vector<const char*>ivecs2 = {"hello", "world", "hehe"}; cout << equal(ivecs1.begin(), ivecs1.end(), ivecs2.begin()) << endl; cout << equal(ivecs1.begin(), ivecs1.end(), ivecs2.begin()+1) << endl; }
注意:
算法实现假设第二个序列至少和第一个序列一样长
那些只接受单一迭代器来表示第二个序列的算法都假设第二个序列至少和第一个一样长
写算法
一些算法将新值赋值到序列中的元素,我们使用时必须注意确保原大小不小于我们要求算法写入的数目。
算法不会执行容器操作,不可能改变容器的大小
1.fill
fill接受一对迭代器表示一个范围,还接受一个值作为第三个参数,fill将给定的这个值赋予输出序列中的每个元素
fill_n接受一个单迭代器,一个计数值,和一个值,它将给定值赋予迭代器指向的元素开始的指定个数。
#include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { vector<int>ivec(10); //fill(begin, end, initail); fill(ivec.begin(), ivec.end(), 10); for(const int&i : ivec) cout << i << " "; cout << endl; fill(ivec.begin(), ivec.begin()+(ivec.end()-ivec.begin())/2, 100); for(const int&i : ivec) cout << i << " "; cout << endl; vector<int>ivec2(10, 1); for(const int&i : ivec2) cout << i << " "; cout << endl; //fill_n(source, num, initial); fill_n(ivec2.begin(), 6, 0); for(const int&i : ivec2) cout << i << " "; cout << endl; }
注意:
向目的位置迭代器写入数据的算法假定目的位置足够大,能容纳要写入的元素。
2.back_inserter
插入迭代器:是一种向容器中添加元素的迭代器
一种保证算法有足够元素空间来容纳输出数据的方法是使用插入迭代器
#include <iterator> #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { vector<int>ivec; cout << "size:" << ivec.size() << endl; auto it = back_inserter(ivec); *it = 100; cout << "size:" << ivec.size() << endl; for(const int&i : ivec) cout << i << " "; cout << endl; fill_n(back_inserter(ivec), 10, 9); cout << "size:" << ivec.size() << endl; for(const int&i : ivec) cout << i << " "; cout << endl; }
3.拷贝
拷贝算法是另一个向目的位置迭代器指向的输出序列中的元素写入数据的算法。
参数是三个迭代器,前两个表示一个输入范围,第三个表示目的序列的起始位置
!注意:传递给copy的目的序列至少要包含与输出序列一样多的元素。
#include <algorithm> #include <vector> #include <iostream> #include <list> using namespace std; int main() { vector<int>ivec(10, 1); for(const int&i : ivec) cout << i << " "; cout << endl; vector<int>ivec2(10, 0); for(const int&i : ivec2) //ivec2全是0 cout << i << " "; cout << endl; copy(ivec.begin(), ivec.end(), ivec2.begin()); //copy for(const int&i : ivec2) //copy后ivec2全是1 cout << i << " "; cout << endl; replace(ivec.begin(), ivec.end(), 1, 100); //replace for(const int&i : ivec) cout << i << " "; cout << endl; list<int>il(10, 0); //将ivec先copy一份到il的末尾,然后拷贝过去的数中100全部替换为42。 replace_copy(ivec.begin(), ivec.end(), back_inserter(il), 100, 42); //copy and replace cout << "--------------------------" << endl; for(const int&i : ivec) cout << i << " "; cout << endl; for(const int&i : il) cout << i << " "; cout << endl; }
!注意:算法不会改变容器的大小,有算法移动数据等类似操作是确保对方容器有足够的大小。
c.reserve改变的是容器的容量
c.resize改变的是容器的大小
容器的容量不为0但是容器的size为0,意味着容器的此时没有存储空间,不能用类似copy函数等等来像容器里面赋值。
4.重排容器元素的算法
sort(c.begin( ), c.end( )); :排序
uniq_iter = unique(c.begin( ), c.end( )); :去重,重复的元素,并不改变容器的大小,重复的元素移动到了“不重复元素”的末尾。返回不重复元素的下一个位置的迭代器,
或者说是重复元素中的第一个元素。
#include <iostream> #include <algorithm> #include <vector> #include <fstream> #include <string> #include <sstream> using namespace std; int main(int argc, char *argv[]) { ifstream is(argv[1]); vector<string>ivecs; string s; while(!is.eof()) { getline(is, s); istringstream strm(s); string ts; while(!strm.eof()) { strm >> ts; ivecs.push_back(ts); } } for(const string&s : ivecs) cout << s << " "; cout << endl; //对数据进行排序,不改变容器的大小 //sort(begin, end); sort(ivecs.begin(), ivecs.end()); for(const string&s : ivecs) cout << s << " "; cout << endl; //对容器的元素进行去重,实际上是只是把重复的元素移动到了末尾,并不改容器的大小,返回不重复元素中的最后一个 //元素的下一个迭代器,或者说是重复元素的第一个迭代器。 // iter = unique(begin, end); auto uniq_iter = unique(ivecs.begin(), ivecs.end()); for(const string&s : ivecs) cout << s << " "; cout << endl; //擦除重复的元素 ivecs.erase(uniq_iter, ivecs.end()); for(const string&s : ivecs) cout << s << " "; cout << endl; return 0; }
5.定制操作
sort算法默认内部是<比较的,当我们希望改变内部是>比较就要向算法传递参数
谓词:谓词是一个可调用的表达式,其返回结果是一个能用作条件的值。
谓词分为一元谓词和二元谓词:分别是接受一个参数和两个参数
接受谓词参数的算法对输出序列中的元素调用谓词,因此元素类型必须能转换成谓词的参数类型
例子中isshorter就是一个二元谓词函数。
#include <iostream> #include <algorithm> #include <vector> #include <fstream> #include <sstream> using namespace std; bool isShorter(const string &s1, const string &s2) //当调用sort算法是内部就不用<了,而是用谓词函数作参照,是按照size()来排顺序的 { return s1.size() < s2.size(); } int main(int argc, char *argv[]) { fstream is(argv[1]); string s; vector<string>ivecs; while(!is.eof()) { getline(is, s); istringstream st(s); while(!st.eof()) { st >> s; ivecs.push_back(s); } } sort(ivecs.begin(), ivecs.end()); auto uniq_iter = unique(ivecs.begin(), ivecs.end()); ivecs.erase(uniq_iter, ivecs.end()); stable_sort(ivecs.begin(), ivecs.end(), isShorter); for(const string &s : ivecs) cout << s << " "; cout << endl; cout << *(ivecs.begin()+1) << endl; }
stable_sort( c.begin( ), c.end( ), 谓词函数);
和sort比较,stable_sort是一种稳定排序,当排序的内容含有相同部分时并不会改变他们的次序,不如1,4,3,4,5. stable_sort( )的话第一个4永远在第二个4前面。
partition( c.begin( ), c.end( ), 谓词函数);
对容器的内容进行划分,使得谓词为true的值会排在容器的前半部分,而使谓词为false的值会排在后半部分。
算法返回一个迭代器,指向最后一个使谓词为true的元素之后的位置
6.lambda表达式
根据算法需要什么谓词函数我们可以定义专门的谓词函数,但是为每种操作定义一个谓词函数是非常麻烦的,
如果我们可以不必为每个可能的大小的编写一个独立的谓词,显然更有实际价值。
lambda:
一个lambda表达式表示一个可调用的代码单元,我们可以将其理解为一个未命名的内联函数。
和任何函数类似,一个lambda具有一个返回类型,一个参数列表和一个函数体,但和函数不同,lambda可能定义在函数的内部。
形式:[捕获列表](参数列表) -> 返回类型 { 函数体 }
捕获列表:是一个lambda所在函数中定义的局部变量的列表(通常为空)。返回类型使用尾置返回类型,其他和普通函数一样。
可以忽略参数列表和返回类型(等价指定一个空的),但是必须永远包含捕获列表和函数体。
auto f = [ ] { return 42; }
如果忽略返回类型,lambda根据函数体中的代码推断出来返回类型。如果函数只是一个return语句,则返回类型从返回的表达式的类型推断出来。否则返回类型为void
<1.向lambda传递参数
[](const string&s1, const string&s2) { return s1.size( ) >= s2.size( ); }
lambda不能含有默认参数,空捕获列表表示不用所在函数里面的任何局部变量。
<2.使用捕获列表
一个lambda可以出现在一个函数中,使用其局部变量,但他只能使用那些明确指名的变量。
一个lambda通过将局部变量包含在其捕获列表中指出将来会使用这些变量。
捕获列表指引lambda在其内部包含访问局部变量所需的信息
sz] (const string&s) { s.size() >= sz; };
lambda以一对[ ]开始,我们可以在其中提供一个","分割的名字列表,这些名字都是来自它所在的函数内。
auto wc = find_if(ivec.begin(), ivec.end(), //find_if前两个参数是迭代器,第三个是一个谓词,返回满足条件条件的第一个迭代器。 [sz] (const string&s) { return s.size() >= sz; });
例子:
返回第一个满足大小小于sz参数的迭代器
#include <iostream> #include <string> #include <fstream> #include <sstream> #include <vector> #include <algorithm> using namespace std; bool isshorter(const string&s1, const string&s2) { return s1.size() < s2.size(); } auto find(const vector<string>&ivecs, string::size_type sz)->vector<string>::iterator { auto iter = find_if(ivecs.begin(), ivecs.end(), [sz](const string &s) {return s.size() >= sz; }); auto count = ivecs.end() - iter; for(auto it = ivecs.begin(); it != iter; ++it) cout << *it << endl; //for_each打印出长度大于sz的单词 //for_each(iter, ivecs.end(), [sz](const string &s) { cout << s << endl; }); } int main(int argc, char *argv[]) { fstream is(argv[1]); string s; string word; vector<string>ivec; while(!is.eof()) //最好改写成while(getline(is, s)) {} 不然会多循环一次。 { getline(is, s); istringstream ist(s); while(!ist.eof()) { ist >> word; ivec.push_back(word); } } string::size_type sz = 0; sort(ivec.begin(), ivec.end(), isshorter); for(const string&s : ivec) cout << s << " "; cout << endl; cin >> sz; find(ivec, sz); }
循环输出的是满足条件的元素的之前所有元素。
注意:捕获列表为空,是因为我们只对lambda所在函数中定义的(非static)变量使用捕获列表。
捕获列表只用于局部非static变量,lambda可以直接使用局部static变量和在它所在函数之外声明的名字。
c++11
7.lambda捕获和返回
捕获的两种方式:
值捕获:采用值捕获的前提是变量可以拷贝,和参数不同,被捕获的变量的值是在lambda创建时拷贝,而不是调用时拷贝
string::size_type sz =42; auto f = [sz] { return sz; }; sz = 0; cout << f() << endl;
结果f( )的值是42,因为在创建时就拷贝sz了。所以捕获的sz是42,且是拷贝不会被改变。
!注意:由于被捕获的变量的值是在lambda创建时的拷贝,因此随后对其修改不会影响到lambda对应的那个值。
引用捕获:
string::size_type sz =42; auto f = [&sz] { return sz; }; sz = 0; cout << f() << endl;
结果f( )值是0;
和我们普通传引用一样,传的参数被绑定了。所以修改后lambda捕获也会被修改。
“ 采用引用方式捕获一个变量,就必须确保被引用的对象在lambda执行的时候是存在的 ”,lambda捕获的都是局部变量,这些变量在函数结束后就不复存在了
如果lambda可能在函数结束后执行,捕获的引用指向的局部变量已经消失。
引用捕获有时是必要的,比如说参数包含流,流是不能被拷贝的。
注意:尽量保持lambda的变量捕获简单化
捕获一个变量如int,string或其他的非指针类型,通常可以采用简单的值捕获方式,在此情况下,只需要关注变量在捕获时是否包含我们所需要的值就行了。
如果我们捕获一个指针或引用,就必须保证在lambda执行时,绑定到迭代器,指针或引用的对象存在,有可能在捕获时,绑定的对象是我们所期望的,
但是在执行时,对象的值可能已经改变的。
我们应该尽可能减少捕获的数据量,来避免潜在的捕获导致的问题,而且,如果可能,应该避免捕获指针或引用。
隐式捕获:
除了显示列出我们希望使用的所在函数的变量外,还可以让编译器根据lambda体中的代码来推断我们要使用哪些变量,
在捕获列表写一个&或=,&告诉编译器采用引用方式捕获,=告诉编译器采用值传递方式捕获。
当我们混用隐式捕获和显示捕获时,捕获列表的第一个元素必须是&或=。
[=, &os] { os << s << endl; } [&, s] { os << s << endl; }
例如:隐式捕获采用的是值捕获,那么显示捕获必须采用引用方式,同理。
捕获列表的几种形式
[ ] 空列表
[ names] 逗号分隔的名字列表
[&] 隐式引用捕获
[=] 隐式值捕获
[&, identifier_list] 隐式变量采用引用捕获,值捕获采用列表形式
[=, identifier_list] 隐式变量采用值捕获,引用捕获采用列表形式
可变的lambda
默认情况下,对于一个被值拷贝的变量,lambda不会改变其值。
#include <iostream> using namespace std; int main() { size_t sz = 43; auto f = [sz]() { return ++sz; };//值传递,是创建时所拷贝的。 error:lambda内部sz是read_only的 cout << f() << endl; }
如果想要修改sz就需要在参数列表后面加上mutable关键字。
#include <iostream> using namespace std; int main() { size_t sz = 43; auto f = [sz]()mutable { return ++sz; };//值传递,是创建时所拷贝的。 cout << f() << endl; }
引用捕获可以直接修改
指定lambda的返回类型,必须使用尾置返回类型。
有时默认推到类型可能是错误的。
#include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { vector<int>ivec(10, -1); for(const int i : ivec) cout << i << " "; cout << endl; transform(ivec.begin(), ivec.end(), ivec.begin(), [](int i)->int { return i < 0 ? -i : i; }); for(const int &i : ivec) cout << i << " "; cout << endl; }
transform(a.begin( ), a.end( ), 指定写入的位置, lambda表达式);
转换元素。
例题:10.21
捕获一个int变量,不为1时递减,变为0退出。
#include <iostream> using namespace std; int main() { int a; cout << "input a:"; cin >> a; while(a != 0) { cout << a << endl; auto f = [&a]()->bool { if(a > 0) {--a; return false;}//定义lambda,是一个未命名的匿名内敛函数。 else if(a == 0) return true;}; f(); //缺少f();就成死循环了,上面的代码只是定义,不会执行,f()才是执行代码。 } }
通常不捕获或者语句很多的情况下最好使用函数。
!!!!
auto find(const vector<string>&ivec, string::size_type sz) -> typename vector<string>::iterator { auto iter = partition(ivec.begin(), ivec.end(), //parition算法问题。 [=](const string&s) { return s.size() >= sz; }); return iter; }
这个错误找了很久,原因是传参数vector不能用const, partition算法会交换位置。
第二个要注意的是尾置返回类型vector<string>::iterator,返回的是一个类型,加typename将vector<string>::iterator转换为类型。
7.标准库bind函数。
lambda为了适应形如一元谓词函数想要传递两个参数出现的,它也有许多不适应的地方,比如函数语句很大的情况下等等。
c++11引入了bind函数来解决这个问题。
头文件#include <functional>
可以把bind函数看作一个通用的函数适配器,它接受一个可调用的对象,生成一个新的可调用的对象来适应原有的参数列表。
bind的一般形式:
auto newCallable = bind(callable, arg_list);
newCallable本身是一个可调用的对象,arg_list是一个逗号分割的参数列表,对应给定callable的参数。
当我们调用newCallable时,newCallable会调用callable,并传递给它arg_list中的参数。
arg_list可能包含形如_n的名字,n是一个整数,这些参数是占位符,表示了newCallable的参数,它们占据了传递给newCallable的参数的位置。
数值n表示生成的可调用对象中参数的位置。
auto check = bind(check_size, _1, 6);
_1表示check_size的第一个参数,比如是字符串s,第二个参数固定为6。
那么调用时就是
check(s);
我们可以使用bind修正参数的值,可以用bind绑定给定可调用中的参数或重新安排顺序。
例子:
#include <iostream> #include <functional> //bind和placeholders命名空间都在functional里面 using namespace std; int add1(int a, int b, int c, int d, int f) { return a+b+c+d+f; } int main() { int a,b,d; cin >> a >> b >> d; //bind将add1绑定到f上面,除了_1和_2需要我们传参。 auto f = bind(add1, a, b, std::placeholders::_1, d, std::placeholders::_2); //调用f(),参数是(1,1)传递给_1和_2。 //等价于调用add1(a,b,_1,d,_2); cout << f(1, 1) << endl; } //参数_1和_2可以颠倒,那么传参时也需要颠倒。
绑定引用参数:
和lambda类似,有时我们对有些绑定的参数希望以引用方式传递,或是绑定的参数无法拷贝,比如说流参数。
for_each(word.begin(), word.end(), bind(print, os, _1, " ")); //error:os是流,我们不能拷贝一个流 <pre name="code" class="cpp">for_each(word.begin(), word.end(), bind(print, ref(os), _1, " ")); //希望传递给bind一个对象而又不拷贝它,就必须使用ref函数。
函数ref( )返回一个对象,包含它的引用,此对象是可以拷贝的。标准库还有cref函数,生成一个保存const 引用的类。
最后理解下bind
看两个例子:
1.ivec中的字符串长度小于等于sz的数量
bool length(const string&s, string::size_type sz) { return s.size() <= sz; } int count(vector<string>&ivec, string::size_type sz) { auto wc = count_if(ivec.begin(), ivec.end(), bind(length, std::placeholders::_1, sz)); }
2.ivec中的int值那个是第一个大于字符串s的长度。
bool check_size(const string&s, string::size_type sz) { return s.size() <= sz; } auto Find(vector<int>&ivec, string& s)->vector<int>::iterator { auto wc = find_if(ivec.begin(), ivec.end(), bind(check_size, s, std::placeholders::_1)); }
8.再探迭代器
头文件#include<iterator>
<1.插入迭代器
<2.流迭代器
<3.反向迭代器
<4. 移动迭代器
<1.插入迭代器
插入迭代器是一种迭代器适配器,它接受一个容器,生成一个迭代器,能实现向给定容器添加元素。
插入迭代器有三种
<<1.front_inserter 创建一个使用push_front的迭代器 容器必须支持push_front
<<2.back_inserter 创建一个使用push_back的迭代器 容器必须支持push_back
<<3.inserter 创建一个使用insert的迭代器,此函数接受两个参数,这个参数必须是指向给定容器的迭代器。元素将被插入到给定迭代器所表示的元素之前。
#include <iostream> #include <vector> #include <iterator> #include <list> #include <algorithm> using namespace std; int main() { list<int>il = {1, 2, 3, 4}; list<int>ils; copy(il.begin(), il.end(), back_inserter(ils)); for(const int i : ils) cout << i << " "; cout << endl; list<int>ils2; copy(il.begin(), il.end(), front_inserter(ils2)); for(const int i : ils2) cout << i << " "; cout << endl; list<int>ils3; copy(il.begin(), il.end(), inserter(ils3, ils3.begin())); //写ils3.begin()和ils3.end()结果不变 for(const int i : ils3) cout << i << " "; cout << endl; }
注意:有写操作会自动扩大容器的capicaty,这样我们在执行这些操作的时候可以不用管容量的大小,
但是有些操作是不会扩大容器的容量的,这样就要保证我们在执行这些操作的时候必有足够的容量。
list<int>il(10); //如果il后面不指定容量的话,会报错,因为unique_copy操作不会修改il的容量。 unique_copy(ivec.begin(), ivec.end(), il.begin());
<2.流迭代器
istream_iterator 读取输入流
ostream_iterator 输出流写数据
这些迭代器将他们对应的流当作一个特定类型的元素序列来处理,通过使用流迭代器我们可以用泛型算法从流对象读取数据以及写入数据。
#include <iostream> #include <iterator> #include <fstream> #include <algorithm> using namespace std; int main(int argc, char *argv[]) { ifstream is(argv[1]); istream_iterator<int>in_iter(is); //绑定输入流 istream_iterator<int>eof; //eof被定义为空的istream_iterator,从而可以当作尾后迭代器来使用。一旦关联的流遇到文件尾或IO错误,迭代器就和尾后迭代器相等 cout << "accumulate is :" << accumulate(in_iter, eof, 0) << endl; }
算法通过流迭代器操作流里面的数据,如上面的例子,通过argv[1]传递参数创建一个文件流,通过流迭代器来处理流。
#include <algorithm> #include <vector> #include <string> #include <iostream> #include <iterator> using namespace std; int main() { ostream_iterator<int>os_iter(cout, " "); //将cout绑定到ostream_iterator上,并且第二个参数是每次使用迭代器后都会默认输出一个空格。 int i; vector<int>ivec; while(cin >> i) { ivec.push_back(i); } sort(ivec.begin(), ivec.end()); //unique_copy(ivec.begin(), ivec.end(), os_iter); //写入到输出流中但是不重复。 copy(ivec.begin(), ivec.end(), os_iter); //写到输出流中的输出迭代器。 cout << endl; }
例子:
接受三个参数,一个输入文件和两个输出文件,输入文件是整数,将奇数和偶数分别写到不同的文件。
#include <iostream> #include <iterator> #include <vector> #include <algorithm> #include <fstream> using namespace std; int main(int argc, char*argv[]) { ifstream is(argv[1]); ofstream os(argv[2]); ofstream os2(argv[3]); //将文件流和不同的迭代器绑定。其实就是可以通过流迭代器来访问其中的元素 ostream_iterator<int>os_iter(os, " "); ostream_iterator<int>os_iter2(os2, " "); istream_iterator<int>is_iter(is), eof; while(is_iter != eof) //测试是否到达尾空迭代器 { if(*is_iter % 2 == 0) { *os_iter++ = *is_iter; //写到文件 } else { *os_iter2++ = *is_iter; //写到文件 } is_iter++; } }
<4.反向迭代器
反向迭代器就是在容器中从尾元素向首元素反向移动的迭代器。
对于反向迭代器,iter++是向 后移动,iter--是向前移动。
反向迭代器也有const和非const版本。
除了forward_list和流以外,其他的容器都定义了反向迭代器。不可能在流中反向移动。
#include <iostream> #include <vector> #include <iterator> using namespace std; int main() { vector<int>ivec = {1,2,3,4,5,6,7,8,9}; for(auto iter = ivec.rbegin(); iter != ivec.rend(); ++iter) cout << *iter << endl; //正常排序 sort(ivec.begin(), ivec.end()); //按逆序排序 sort(ivec.rbegin(), ivec.rend()); }
但是用反向迭代器有些需要注意
#include <iostream> #include <algorithm> #include <string> using namespace std; int main() { string s = " a boy ,haha"; cout << string(s.begin(), s.end()) << endl; cout << string(s.rbegin(), s.rend()) << endl; auto iter = find(s.rbegin(), s.rend(), ','); //cout << string(iter, s.rend()) << endl; cout << string(iter.base(), s.end()) << endl; }
通过分析最后一个逗号输出最后一个单词。使用反向迭代器查找会很方便
但是如果用注释来的来输出单词就输出成ahah,而不是haha,反向迭代器找到了位置但是
也却反向输出的,所以需要reverse_iterator的base成员函数将反向迭代器转换成普通的迭代器
iter和iter.base( )注意不是相同位置而是相邻位置。
注意:迭代器做减法时要分清是什么容器的迭代器比如list就不行,但是vector可以。
9.泛型算法结构
任何算法的最基本结构就是它要求迭代器提供哪些操作。
算法所要求的迭代器操作可以分为5个迭代器类别
输入迭代器:只读,不写,单遍扫描,只能递增
输出迭代器:只写,不读,单遍扫描,只能递增
前向迭代器:可以读写,多遍扫描,只能向前
双向迭代器:可以读写,多遍扫描,可以递增递减
随机访问迭代器:可读写,多遍扫描,支持全部迭代器运算。
9.1.算法的形参模式
大多数算法具有下面4种形式之一
alg(beg, end, other args);
alg(beg, end, des, other args);
alg(beg, end, beg2, other args);
alg(beg, end, beg2, end2, other args);
alg是算法的名字,beg和end表示算法所操作的范围,几乎所有的算法都接受一个输入范围,
是否有其他的参数依赖于要执行的操作。
des是目的位置,beg2end2是第二个范围。
!注意:
在执行算法的时候我们要注意容器的大小问题,有些操作不包含自动扩大容器大小的操作,我们必须保证操作的容器有足够的空间。
9.2.算法的命名规则
<1.一些算法使用重载形式传递一个谓词
接受谓词参数来代替<或==运算符的算法,以及那些不接受额外参数的算法,通常都是重载的函数。
具体调用应该调用哪个版本不会产生奇异。
<<1.接受谓词参数的算法都有附加的_if前缀
<<2.写到额外目的的空间的算法都在名字后面附加一个_copy
<<3.一些算法同时提供_if和_copy版本,这些版本接受一个目的位置迭代器和一个谓词。
10.特定容器的算法
比如通用版本的sort要求随机访问迭代器,因此不能用于list和forward_list。
所以STL定义了他们单独的函数。
这些链表版本的性能比对应的通用版本好的多。
对于list和forward_list应该优先使用成员函数版本而不是通用算法。
链表特有版本会彻底改变底层的容器。
#include <algorithm> #include <list> #include <iostream> #include <iterator> #include <functional> #include <vector> using namespace std; int main() { list<int>il1 = {1,2,3,4,5}; list<int>il2 = {6,7,8,9,10}; //合并后,il2为空 il1.merge(il2); //il1.merge(il2, comp); 使用给定的比较操作,第一个版本默认使用<比较 for(const int i : il1) cout << i << " "; cout << endl; for(const int i : il2)//il2输出为空。 cout << i << " "; cout << endl; list<int>il3 = {1,2,3,4,5}; il3.remove(2); //il3.remove_if(pred); 删除满足pred条件的 for(const int i : il3) cout << i << " "; cout << endl; list<int>il4 = {1,2,3,4,5}; //逆序 il4.reverse(); for(const int i : il4) cout << i << " "; cout << endl; list<int>il5 = {1,3,2,4,5}; //排序,默认< il5.sort(); //il5.sort(comp); for(const int i : il5) cout << i << " "; cout << endl; list<int>il6 = {1,1,3,2,4,2,4,5}; il6.sort(); //成功删除重复需要先排序。 il6.unique(); for(const int i : il6) cout << i << " "; cout << endl; list<int>il7 = {1,2,3,4,5,6,7}; list<int>il8 = {1,2,3}; //灵活合并 //il7.splice(il7.begin(), il8); //il7.splice(il7.begin(), il8, il8.begin()); 只有指定的一个元素添加到il7了。 il7.splice(il7.begin(), il8, ++il8.begin(), il8.end()); for(const int i : il7) cout << i << " "; cout << endl; }
通用版本一般不会销毁原来的版本,而链表版本会销毁给定的链表。
《c++ primer》这章内容比较多,代码也比较多,需要经常复习,而且书上并没有包含全部的算法。
运用算法时我们应该好好考虑所执行算法的容器是什么内部结构实现的,可以避免用错算法。