第十章 泛型算法 exce

第十章 泛型算法

练习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()
{
// 10.1
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;

// 10.2
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()
{
// Exercise 10.3
std::vector<int> v = { 1, 2, 3, 4 };
std::cout << "ex 10.03: " << std::accumulate(v.cbegin(), v.cend(), 0) << std::endl;

// Exercise 10.4
std::vector<double> vd = { 1.1, 0.5, 3.3 };
std::cout << "ex 10.04: "
<< std::accumulate(vd.cbegin(), vd.cend(), 0)
<< std::endl; // ^<-- note here.
// @attention
//
// The ouput is 4 rather than 4.9 as expected.
// The reason is std::accumulate is a template function. The third parameter is _Tp __init
// When "0" , an integer, had been specified here, the compiler deduced _Tp as
// interger.As a result , when the following statments were being excuted :
// for (; __first != __last; ++__first)
// __init = __init + *__first;
// return __init;
// all calculation would be converted to integer.

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>

// print containers like vector, deque, list, etc.
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_sortisShorter 将传递给你的 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>

// print a container like vector, deque, list, etc.
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" // Sales_data class.

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 };

// @note the elements the iterators pointing to
// must match the parameters of the predicate.
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 应该返回捕获的 intint 参数的和。

解:

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>

// from ex 10.9
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);

// sort by size, but maintain alphabetical order for same size.
std::stable_sort(vs.begin(), vs.end(), [](string const& lhs, string const& rhs){
return lhs.size() < rhs.size();
});

// get an iterator to the first one whose size() is >= sz
auto wc = std::find_if(vs.begin(), vs.end(), [sz](string const& s){
return s.size() >= sz;
});

// print the biggies
std::for_each(wc, vs.end(), [](const string &s){
std::cout << s << " ";
});
}

int main()
{
// ex10.16
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" // Sales_data class.

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>

// from ex 10.9
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());
}

// ex10.18
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 << " ";
}

// ex10.19
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()
{
// ex10.18
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;

// ex10.19
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;

// Exercise 10.20
std::size_t bigerThan6(vector<string> const& v)
{
return count_if(v.cbegin(), v.cend(), [](string const& s){
return s.size() > 6;
});
}

int main()
{
// ex10.20
vector<string> v{
"alan","moophy","1234567","1234567","1234567","1234567"
};
std::cout << "ex10.20: " << bigerThan6(v) << std::endl;

// ex10.21
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,使用 bindcheck_size 在一个 intvector 中查找第一个大于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节的练习中,编写了一个使用partitionbiggies版本。使用 check_sizebind 重写此函数。

解:

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,将其拷贝到三个其他容器中。分别使用inserterback_inserterfront_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 };

// uses inserter
list<int> lst1;
copy(vec.cbegin(), vec.cend(), inserter(lst1, lst1.begin()));
print(lst1);

// uses back_inserter
list<int> lit2;
copy(vec.cbegin(), vec.cend(), back_inserter(lit2));
print(lit2);

// uses front_inserter
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));

// output
std::copy(vec.cbegin(), vec.cend(), std::ostream_iterator<string>(std::cout, "\n"));
}

练习10.30

使用流迭代器、sortcopy 从标准输入读取一个整数序列,将其排序,并将结果写到标准输出。

解:

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 函数来排序交易记录,然后使用 findaccumulate 求和。

解:

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 在一个 intlist 中查找最后一个值为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 要求哪类迭代器?reverseunique 呢?

  • 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;
}