第十章 泛型算法
练习10.1
头文件algorithm
中定义了一个名为count
的函数,它类似find
, 接受一对迭代器和一个值作为参数。count
返回给定值在序列中出现的次数。编写程序,读取int
序列存入vector
中,打印有多少个元素的值等于给定值。
解:
见下题
练习10.2
重做上一题,但读取 string
序列存入 list
中。
解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include <iostream> #include <string> #include <vector> #include <algorithm> #include <list> int main () { std::vector<int > v = { 1 , 2 , 3 , 4 , 5 , 6 , 6 , 6 , 2 }; std::cout << "ex 10.01: " << std::count (v.cbegin (), v.cend (), 6 ) << std::endl; std::list<std::string> l = { "aa" , "aaa" , "aa" , "cc" }; std::cout << "ex 10.02: " << std::count (l.cbegin (), l.cend (), "aa" ) << std::endl; return 0 ; }
练习10.3
用 accumulate
求一个 vector<int>
中元素之和。
解:
见下题。
练习10.4
假定 v
是一个vector<double>
,那么调用 accumulate(v.cbegin(),v.cend(),0)
有何错误(如果存在的话)?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include <iostream> #include <string> #include <vector> #include <algorithm> #include <numeric> int main () { std::vector<int > v = { 1 , 2 , 3 , 4 }; std::cout << "ex 10.03: " << std::accumulate (v.cbegin (), v.cend (), 0 ) << std::endl; std::vector<double > vd = { 1.1 , 0.5 , 3.3 }; std::cout << "ex 10.04: " << std::accumulate (vd.cbegin (), vd.cend (), 0 ) << std::endl; return 0 ; }
结果会是 int
类型。
练习10.5
在本节对名册(roster
)调用equal
的例子中,如果两个名册中保存的都是C风格字符串而不是string
,会发生什么?
C风格字符串是用指向字符的指针表示的,因此会比较两个指针的值(地址),而不会比较这两个字符串的内容。
练习10.6
编写程序,使用 fill_n
将一个序列中的 int
值都设置为0。
解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include <iostream> #include <vector> #include <algorithm> using std::vector; using std::cout; using std::endl; using std::fill_n;int main () { vector<int > vec{ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 }; fill_n (vec.begin (), vec.size (), 0 ); for (auto i : vec) cout << i << " " ; cout << endl; }
练习10.7
下面程序是否有错误?如果有,请改正:
1 2 3 4 5 6 7 (a) vector<int > vec; list<int > lst; int i; while (cin >> i) lst.push_back (i); copy (lst.cbegin (), lst.cend (), vec.begin ()); (b) vector<int > vec; vec.reserve (10 ); fill_n (vec.begin (), 10 , 0 );
解:
(a) 应该加一条语句 vec.resize(lst.size())
。copy
时必须保证目标目的序列至少要包含与输入序列一样多的元素。
(b) 从语句上来说没错误,这段代码没有任何结果。但是从逻辑上来说,应该将 vec.reserve(10)
改为 vec.resize(10)
。
练习10.8
本节提到过,标准库算法不会改变它们所操作的容器的大小。为什么使用 back_inserter
不会使这一断言失效?
back_inserter
是插入迭代器,在 iterator.h
头文件中,不是标准库的算法。
练习10.9
实现你自己的elimDups
。分别在读取输入后、调用unique
后以及调用erase
后打印vector
的内容。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include <iostream> #include <string> #include <vector> #include <algorithm> template <typename Sequence>auto println (Sequence const & seq) -> std::ostream& { for (auto const & elem : seq) std::cout << elem << " " ; return std::cout << std::endl; } auto eliminate_duplicates (std::vector<std::string> &vs) -> std::vector<std::string>& { std::sort (vs.begin (), vs.end ()); println (vs); auto new_end = std::unique (vs.begin (), vs.end ()); println (vs); vs.erase (new_end, vs.end ()); return vs; } int main () { std::vector<std::string> vs{ "a" , "v" , "a" , "s" , "v" , "a" , "a" }; println (vs); println (eliminate_duplicates (vs)); return 0 ; }
练习10.10
你认为算法不改变容器大小的原因是什么?
解:
将算法和容器的成员函数区分开。
算法的参数是迭代器,不是容器本身。
练习10.11
编写程序,使用 stable_sort
和 isShorter
将传递给你的 elimDups
版本的 vector
排序。打印 vector
的内容,验证你的程序的正确性。
解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 #include <iostream> #include <string> #include <vector> #include <algorithm> #include <numeric> #include <list> template <typename Sequence>inline std::ostream& println (Sequence const & seq) { for (auto const & elem : seq) std::cout << elem << " " ; std::cout << std::endl; return std::cout; } inline bool is_shorter (std::string const & lhs, std::string const & rhs) { return lhs.size () < rhs.size (); } void elimdups (std::vector<std::string> &vs) { std::sort (vs.begin (), vs.end ()); auto new_end = std::unique (vs.begin (), vs.end ()); vs.erase (new_end, vs.end ()); } int main () { std::vector<std::string> v{ "1234" , "1234" , "1234" , "Hi" , "alan" , "wang" }; elimdups (v); std::stable_sort (v.begin (), v.end (), is_shorter); std::cout << "ex10.11 :\n" ; println (v); return 0 ; }
练习10.12
编写名为 compareIsbn
的函数,比较两个 Sales_data
对象的isbn()
成员。使用这个函数排序一个保存 Sales_data
对象的 vector
。
解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include <iostream> #include <string> #include <vector> #include <algorithm> #include "../ch07/ex7_26.h" inline bool compareIsbn (const Sales_data &sd1, const Sales_data &sd2) { return sd1.isbn ().size () < sd2.isbn ().size (); } int main () { Sales_data d1 ("aa" ) , d2 ("aaaa" ) , d3 ("aaa" ) , d4 ("z" ) , d5 ("aaaaz" ) ; std::vector<Sales_data> v{ d1, d2, d3, d4, d5 }; std::sort (v.begin (), v.end (), compareIsbn); for (const auto &element : v) std::cout << element.isbn () << " " ; std::cout << std::endl; return 0 ; }
练习10.13
标准库定义了名为 partition
的算法,它接受一个谓词,对容器内容进行划分,使得谓词为true
的值会排在容器的前半部分,而使得谓词为 false
的值会排在后半部分。算法返回一个迭代器,指向最后一个使谓词为 true
的元素之后的位置。编写函数,接受一个 string
,返回一个 bool
值,指出 string
是否有5个或更多字符。使用此函数划分 words
。打印出长度大于等于5的元素。
解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <iostream> #include <string> #include <vector> #include <algorithm> bool predicate (const std::string &s) { return s.size () >= 5 ; } int main () { auto v = std::vector<std::string>{ "a" , "as" , "aasss" , "aaaaassaa" , "aaaaaabba" , "aaa" }; auto pivot = std::partition (v.begin (), v.end (), predicate); for (auto it = v.cbegin (); it != pivot; ++it) std::cout << *it << " " ; std::cout << std::endl; return 0 ; }
练习10.14
编写一个lambda
,接受两个int
,返回它们的和。
1 auto f = [](int i, int j) { return i + j; };
练习10.15
编写一个 lambda
,捕获它所在函数的 int
,并接受一个 int
参数。lambda
应该返回捕获的 int
和 int
参数的和。
解:
1 2 int x = 10 ;auto f = [x](int i) { i + x; };
练习10.16
使用 lambda
编写你自己版本的 biggies
。
解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 #include <iostream> #include <string> #include <vector> #include <algorithm> void elimdups (std::vector<std::string> &vs) { std::sort (vs.begin (), vs.end ()); auto new_end = std::unique (vs.begin (), vs.end ()); vs.erase (new_end, vs.end ()); } void biggies (std::vector<std::string> &vs, std::size_t sz) { using std::string; elimdups (vs); std::stable_sort (vs.begin (), vs.end (), [](string const & lhs, string const & rhs){ return lhs.size () < rhs.size (); }); auto wc = std::find_if (vs.begin (), vs.end (), [sz](string const & s){ return s.size () >= sz; }); std::for_each(wc, vs.end (), [](const string &s){ std::cout << s << " " ; }); } int main () { std::vector<std::string> v { "1234" ,"1234" ,"1234" ,"hi~" , "alan" , "alan" , "cp" }; std::cout << "ex10.16: " ; biggies (v, 3 ); std::cout << std::endl; return 0 ; }
练习10.17
重写10.3.1节练习10.12的程序,在对sort
的调用中使用 lambda
来代替函数 compareIsbn
。
解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <iostream> #include <string> #include <vector> #include <algorithm> #include "../ch07/ex7_26.h" int main () { Sales_data d1 ("aa" ) , d2 ("aaaa" ) , d3 ("aaa" ) , d4 ("z" ) , d5 ("aaaaz" ) ; std::vector<Sales_data> v{ d1, d2, d3, d4, d5 }; std::sort (v.begin (), v.end (), [](const Sales_data &sd1, const Sales_data &sd2){ return sd1.isbn ().size () < sd2.isbn ().size (); }); for (const auto &element : v) std::cout << element.isbn () << " " ; std::cout << std::endl; return 0 ; }
练习10.18
重写 biggies
,用 partition
代替 find_if
。我们在10.3.1节练习10.13中介绍了 partition
算法。
解:
见下题
练习10.19
用 stable_partition
重写前一题的程序,与 stable_sort
类似,在划分后的序列中维持原有元素的顺序。
解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 #include <iostream> #include <string> #include <vector> #include <algorithm> void elimdups (std::vector<std::string> &vs) { std::sort (vs.begin (), vs.end ()); auto new_end = std::unique (vs.begin (), vs.end ()); vs.erase (new_end, vs.end ()); } void biggies_partition (std::vector<std::string> &vs, std::size_t sz) { elimdups (vs); auto pivot = partition (vs.begin (), vs.end (), [sz](const std::string &s){ return s.size () >= sz;} ); for (auto it = vs.cbegin (); it != pivot; ++it) std::cout << *it << " " ; } void biggies_stable_partition (std::vector<std::string> &vs, std::size_t sz) { elimdups (vs); auto pivot = stable_partition (vs.begin (), vs.end (), [sz](const std::string& s){ return s.size () >= sz; }); for (auto it = vs.cbegin (); it != pivot; ++it) std::cout << *it << " " ; } int main () { std::vector<std::string> v{ "the" , "quick" , "red" , "fox" , "jumps" , "over" , "the" , "slow" , "red" , "turtle" }; std::cout << "ex10.18: " ; std::vector<std::string> v1 (v) ; biggies_partition (v1, 4 ); std::cout << std::endl; std::cout << "ex10.19: " ; std::vector<std::string> v2 (v) ; biggies_stable_partition (v2, 4 ); std::cout << std::endl; return 0 ; }
练习10.20
标准库定义了一个名为 count_if
的算法。类似 find_if
,此函数接受一对迭代器,表示一个输入范围,还接受一个谓词,会对输入范围中每个元素执行。count_if
返回一个计数值,表示谓词有多少次为真。使用count_if
重写我们程序中统计有多少单词长度超过6的部分。
解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include <iostream> #include <string> #include <vector> #include <algorithm> using std::vector;using std::count_if;using std::string;std::size_t bigerThan6 (vector<string> const & v) { return count_if (v.cbegin (), v.cend (), [](string const & s){ return s.size () > 6 ; }); } int main () { vector<string> v{ "alan" ,"moophy" ,"1234567" ,"1234567" ,"1234567" ,"1234567" }; std::cout << "ex10.20: " << bigerThan6 (v) << std::endl; int i = 7 ; auto check_and_decrement = [&i]() { return i > 0 ? !--i : !i; }; std::cout << "ex10.21: " ; while (!check_and_decrement ()) std::cout << i << " " ; std::cout << i << std::endl; return 0 ; }
练习10.21
编写一个 lambda
,捕获一个局部 int
变量,并递减变量值,直至它变为0。一旦变量变为0,再调用lambda
应该不再递减变量。lambda
应该返回一个bool
值,指出捕获的变量是否为0。
解:
1 2 3 int i = 10 ;auto f = [&i]() -> bool { return (i == 0 ? true : !(i--)); };while (!f ()) cout << i << endl;
练习10.22
重写统计长度小于等于6的单词数量的程序,使用函数代替lambda
。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include <iostream> #include <vector> #include <string> #include <algorithm> #include <functional> using std::string;using namespace std::placeholders;bool isLesserThanOrEqualTo6 (const string &s, string::size_type sz) { return s.size () <= sz; } int main () { std::vector<string> authors{ "Mooophy" , "pezy" , "Queequeg90" , "shbling" , "evan617" }; std::cout << count_if (authors.cbegin (), authors.cend (), bind (isLesserThanOrEqualTo6, _1, 6 )); }
练习10.23
bind
接受几个参数?
假设被绑定的函数接受 n
个参数,那么bind
接受n + 1
个参数。
练习10.24
给定一个string
,使用 bind
和 check_size
在一个 int
的vector
中查找第一个大于string
长度的值。
解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include <iostream> #include <vector> #include <algorithm> #include <functional> using std::cout;using std::endl;using std::string;using std::vector;using std::find_if;using std::bind;using std::size_t ;auto check_size (string const & str, size_t sz) { return str.size () < sz; } int main () { vector<int > vec{ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 }; string str ("123456" ) ; auto result = find_if (vec.begin (), vec.end (), bind (check_size, str, std::placeholders::_1)); if (result != vec.end ()) cout << *result << endl; else cout << "Not found" << endl; return 0 ; }
练习10.25
在10.3.2节的练习中,编写了一个使用partition
的biggies
版本。使用 check_size
和 bind
重写此函数。
解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include <iostream> #include <vector> #include <string> #include <algorithm> #include <functional> using std::string; using std::vector;using namespace std::placeholders;void elimdups (vector<string> &vs) { std::sort (vs.begin (), vs.end ()); vs.erase (unique (vs.begin (), vs.end ()), vs.end ()); } bool check_size (const string &s, string::size_type sz) { return s.size () >= sz; } void biggies (vector<string> &words, vector<string>::size_type sz) { elimdups (words); auto iter = std::stable_partition (words.begin (), words.end (), bind (check_size, _1, sz)); for_each(words.begin (), iter, [](const string &s){ std::cout << s << " " ; }); } int main () { std::vector<std::string> v{ "the" , "quick" , "red" , "fox" , "jumps" , "over" , "the" , "slow" , "red" , "turtle" }; biggies (v, 4 ); }
练习10.26
解释三种插入迭代器的不同之处。
解:
back_inserter
使用 push_back
。
front_inserter
使用 push_front
。
inserter
使用 insert
,此函数接受第二个参数,这个参数必须是一个指向给定容器的迭代器。元素将被插入到给定迭代器所表示的元素之前。
练习10.27
除了 unique
之外,标准库还定义了名为 unique_copy
的函数,它接受第三个迭代器,表示拷贝不重复元素的目的位置。编写一个程序,使用 unique_copy
将一个vector
中不重复的元素拷贝到一个初始化为空的list
中。
解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include <iostream> #include <algorithm> #include <vector> #include <list> #include <iterator> int main () { std::vector<int > vec{ 1 , 1 , 3 , 3 , 5 , 5 , 7 , 7 , 9 }; std::list<int > lst; std::unique_copy (vec.begin (), vec.end (), back_inserter (lst)); for (auto i : lst) std::cout << i << " " ; std::cout << std::endl; }
练习10.28
一个vector
中保存 1 到 9,将其拷贝到三个其他容器中。分别使用inserter
、back_inserter
和 front_inserter
将元素添加到三个容器中。对每种 inserter
,估计输出序列是怎样的,运行程序验证你的估计是否正确。
解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include <iostream> #include <algorithm> #include <vector> #include <list> #include <iterator> using std::list; using std::copy; using std::cout; using std::endl;template <typename Sequence>void print (Sequence const & seq) { for (const auto & i : seq) std::cout << i << " " ; std::cout << std::endl; } int main () { std::vector<int > vec{ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 }; list<int > lst1; copy (vec.cbegin (), vec.cend (), inserter (lst1, lst1.begin ())); print (lst1); list<int > lit2; copy (vec.cbegin (), vec.cend (), back_inserter (lit2)); print (lit2); list<int > lst3; copy (vec.cbegin (), vec.cend (), front_inserter (lst3)); print (lst3); }
前两种为正序,第三种为逆序,输出和预计一样。
练习10.29
编写程序,使用流迭代器读取一个文本文件,存入一个vector
中的string
里。
解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include <iostream> #include <fstream> #include <vector> #include <string> #include <iterator> using std::string;int main () { std::ifstream ifs ("../data/book.txt" ) ; std::istream_iterator<string> in (ifs) , eof ; std::vector<string> vec; std::copy (in, eof, back_inserter (vec)); std::copy (vec.cbegin (), vec.cend (), std::ostream_iterator <string>(std::cout, "\n" )); }
练习10.30
使用流迭代器、sort
和 copy
从标准输入读取一个整数序列,将其排序,并将结果写到标准输出。
解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <iostream> #include <vector> #include <algorithm> #include <iterator> using namespace std;int main () { vector<int > v; istream_iterator<int > int_it (cin) , int_eof ; copy (int_it, int_eof, back_inserter (v)); sort (v.begin (), v.end ()); copy (v.begin (), v.end (), ostream_iterator <int >(cout," " )); cout << endl; return 0 ; }
练习10.31
修改前一题的程序,使其只打印不重复的元素。你的程序应该使用 unique_copy
。
解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include <iostream> #include <vector> #include <algorithm> #include <iterator> using namespace std;int main () { vector<int > v; istream_iterator<int > int_it (cin) , int_eof ; copy (int_it, int_eof, back_inserter (v)); sort (v.begin (), v.end ()); unique (v.begin (), v.end ()); copy (v.begin (), v.end (), ostream_iterator <int >(cout, " " )); cout << endl; return 0 ; }
练习10.32
重写1.6节中的书店程序,使用一个vector
保存交易记录,使用不同算法完成处理。使用 sort
和10.3.1节中的 compareIsbn
函数来排序交易记录,然后使用 find
和 accumulate
求和。
解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <iostream> #include <vector> #include <algorithm> #include <iterator> #include <numeric> #include "../include/Sales_item.h" int main () { std::istream_iterator<Sales_item> in_iter (std::cin) , in_eof ; std::vector<Sales_item> vec; while (in_iter != in_eof) vec.push_back (*in_iter++); sort (vec.begin (), vec.end (), compareIsbn); for (auto beg = vec.cbegin (), end = beg; beg != vec.cend (); beg = end) { end = find_if (beg, vec.cend (), [beg](const Sales_item &item){ return item.isbn () != beg->isbn (); }); std::cout << std::accumulate (beg, end, Sales_item (beg->isbn ())) << std::endl; } }
练习10.33
编写程序,接受三个参数:一个输入文件和两个输出文件的文件名。输入文件保存的应该是整数。使用 istream_iterator
读取输入文件。使用 ostream_iterator
将奇数写入第一个输入文件,每个值后面都跟一个空格。将偶数写入第二个输出文件,每个值都独占一行。
解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <fstream> #include <iterator> #include <algorithm> int main (int argc, char **argv) { if (argc != 4 ) return -1 ; std::ifstream ifs (argv[1 ]) ; std::ofstream ofs_odd (argv[2 ]) , ofs_even (argv[3 ]) ; std::istream_iterator<int > in (ifs) , in_eof ; std::ostream_iterator<int > out_odd (ofs_odd, " " ) , out_even (ofs_even, "\n" ) ; std::for_each(in, in_eof, [&out_odd, &out_even](const int i) { *(i & 0x1 ? out_odd : out_even)++ = i; }); return 0 ; }
练习10.34
使用 reverse_iterator
逆序打印一个vector
。
解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include <iostream> #include <vector> using namespace std;int main () { vector<int > v = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 }; for (auto it = v.crbegin (); it != v.crend (); ++it) { cout << *it << endl; } return 0 ; }
练习10.35
使用普通迭代器逆序打印一个vector
。
解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include <iostream> #include <vector> using namespace std;int main () { vector<int > v = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 }; for (auto it = std::prev (v.cend ()); true ; --it) { std::cout << *it << " " ; if (it == v.cbegin ()) break ; } std::cout << std::endl; return 0 ; }
练习10.36
使用 find
在一个 int
的list
中查找最后一个值为0的元素。
解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include <iostream> #include <list> #include <algorithm> using namespace std;int main () { list<int > l = { 1 , 2 , 0 , 4 , 5 , 6 , 7 , 0 , 9 }; auto it = find (l.crbegin (), l.crend (), 0 ); cout << distance (it, l.crend ()) << endl; return 0 ; }
练习10.37
给定一个包含10 个元素的vector
,将位置3到7之间的元素按逆序拷贝到一个list
中。
解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include <iostream> #include <list> #include <algorithm> #include <vector> #include <iterator> using namespace std;int main () { vector<int > v = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 }; list<int > l; copy (v.crbegin () + 3 , v.crbegin () + 8 , back_inserter (l)); for (auto i : l) std::cout << i << " " ; cout << endl; return 0 ; }
练习10.38
列出5个迭代器类别,以及每类迭代器所支持的操作。
输入迭代器 : ==
,!=
,++
,*
,->
输出迭代器 : ++
,*
前向迭代器 : ==
,!=
,++
,*
,->
双向迭代器 : ==
,!=
,++
,--
,*
,->
随机访问迭代器 : ==
,!=
,<
,<=
,>
,>=
,++
,--
,+
,+=
,-
,-=
,*
,->
,iter[n]
==*(iter[n])
练习10.39
list
上的迭代器属于哪类?vector
呢?
list
上的迭代器是 双向迭代器
vector
上的迭代器是 随机访问迭代器
练习10.40
你认为 copy
要求哪类迭代器?reverse
和 unique
呢?
copy
需要两个输入迭代器 ,一个输出迭代器
reverse
需要双向迭代器
unique
需要随机访问迭代器
练习10.41
仅根据算法和参数的名字,描述下面每个标准库算法执行什么操作:
1 2 3 4 replace (beg, end, old_val, new_val);replace_if (beg, end, pred, new_val);replace_copy (beg, end, dest, old_val, new_val);replace_copy_if (beg, end, dest, pred, new_val);
解:
replace
在迭代器范围内用新值替换所有原来的旧值。
replace_if
在迭代器范围内,满足谓词条件的元素用新值替换。
replace_copy
复制迭代器范围内的元素到目标迭代器位置,如果元素等于某个旧值,则用新值替换
replace_copy_if
复制迭代器范围内的元素到目标迭代器位置,满足谓词条件的元素用新值替换
练习10.42
使用 list
代替 vector
重新实现10.2.3节中的去除重复单词的程序。
解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <iostream> #include <string> #include <list> using std::string; using std::list;void elimDups (list<string> &words) { words.sort (); words.unique (); } int main () { list<string> l = { "aa" , "aa" , "aa" , "aa" , "aasss" , "aa" }; elimDups (l); for (const auto & e : l) std::cout << e << " " ; std::cout << std::endl; }