第十章 泛型算法
泛型算法
- 因为它们实现共同的操作,所以称之为“算法”;而“泛型”、指的是它们可以操作在多种容器类型上。
- 泛型算法本身不执行容器操作,只是单独依赖迭代器和迭代器操作实现。
- 头文件:
#include <algorithm>
或者#include <numeric>
(算数相关) - 大多数算法是通过遍历两个迭代器标记的一段元素来实现其功能。
- 必要的编程假定:算法永远不会改变底层容器的大小。算法可能改变容器中保存的元素的值,也可能在容器内移动元素,但不能直接添加或者删除元素。
find
vector<int>::const_iterator result = find(vec.begin(), vec.end(), search_value);
- 输入:两个标记范围的迭代器和目标查找值。返回:如果找到,返回对应的迭代器,否则返回第二个参数,即标记结尾的迭代器。
练习10.1
头文件
algorithm
中定义了一个名为count
的函数,它类似find
, 接受一对迭代器和一个值作为参数。count
返回给定值在序列中出现的次数。编写程序,读取int
序列存入vector
中,打印有多少个元素的值等于给定值。
解:
见下题
练习10.2
重做上一题,但读取
string
序列存入list
中。
解:
#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;
}
初识泛型算法
- 标准库提供了超过100个算法,但这些算法有一致的结构。
- 理解算法的最基本的方法是了解它们是否读取元素、改变元素、重排元素顺序。
只读算法
- 只读取范围中的元素,不改变元素。
- 如
find
和accumulate
(在numeric
中定义,求和)。 find_first_of
,输入:两对迭代器标记两段范围,在第一段中找第二段中任意元素,返回第一个匹配的元素,找不到返回第一段的end
迭代器。- 通常最好使用
cbegin
和cend
。 equal
:确定两个序列是否保存相同的值。
练习10.3
用
accumulate
求一个vector<int>
中元素之和。
解:
见下题。
练习10.4
假定
v
是一个vector<double>
,那么调用accumulate(v.cbegin(),v.cend(),0)
有何错误(如果存在的话)?
#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风格字符串是用指向字符的指针表示的,因此会比较两个指针的值(地址),而不会比较这两个字符串的内容。
写容器元素的算法
- 一些算法将新值赋予序列中的元素。
- 算法不检查写操作。
fill
:fill(vec.begin(), vec.end(), 0);
将每个元素重置为0fill_n
:fill_n(vec.begin(), 10, 0);
- 插入迭代器
back_inserter
:- 用来确保算法有足够的空间存储数据。
#include <iterator>
back_inserter(vec)
- 拷贝算法
copy
: - 输入:前两个参数指定输入范围,第三个指向目标序列。
copy (ilst.begin(), ilst.end(), back_inserter(ivec));
copy
时必须保证目标目的序列至少要包含与输入序列一样多的元素。
练习10.6
编写程序,使用
fill_n
将一个序列中的int
值都设置为0。
解:
#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
下面程序是否有错误?如果有,请改正:
(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) reserve分配了足够的空间,但是不会创建新元素。算法可能改变容器中保存的元素的值,也可能在容器内移动元素,永远不会直接添加和删除元素(c++ priemr中文版第五版 P338),所以此处应该改为resize(10)。
练习10.8
本节提到过,标准库算法不会改变它们所操作的容器的大小。为什么使用
back_inserter
不会使这一断言失效?
back_inserter
是插入迭代器,在 iterator.h
头文件中,不是标准库的算法。
重排容器元素的算法
- 这些算法会重排容器中元素的顺序。
- 排序算法
sort
:- 接受两个迭代器,表示要排序的元素范围。
- 消除重复
unique
:- 之前要先调用
sort
- 返回的迭代器指向最后一个不重复元素之后的位置。
- 顺序会变,重复的元素被“删除”。
- 并没有真正删除,真正删除必须使用容器操作。
- 之前要先调用
练习10.9
实现你自己的
elimDups
。分别在读取输入后、调用unique
后以及调用erase
后打印vector
的内容。
#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
你认为算法不改变容器大小的原因是什么?
解:
- 将算法和容器的成员函数区分开。
- 算法的参数是迭代器,不是容器本身。
定制操作
向算法传递函数:
-
谓词(
predicate
):- 是一个可调用的表达式,返回结果是一个能用作条件的值
- 一元谓词:接受一个参数
- 二元谓词:接受两个参数
-
例子:
stable_sort
:- 保留相等元素的原始相对位置。
stable_sort(words.begin(), words.end(), isShorter);
练习10.11
编写程序,使用
stable_sort
和isShorter
将传递给你的elimDups
版本的vector
排序。打印vector
的内容,验证你的程序的正确性。
解:
#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
。
解:
#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的元素。
解:
#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;
}
lambda表达式
-
有时可能希望操作可以接受更多的参数。
-
lambda
表达式表示一个可调用的代码单元,可以理解成是一个未命名的内联函数。 -
形式:
[capture list](parameter list) -> return type {function body}
。- 其中
capture list
捕获列表是一个lambda
所在函数定义的局部变量的列表(通常为空)。不可忽略。 return type
是返回类型。可忽略。parameter
是参数列表。可忽略。function body
是函数体。不可忽略。auto f = [] {return 42;}
- 其中
-
例子:
find_if
:- 接受一对表示范围的迭代器和一个谓词,用来查找第一个满足特定要求的元素。返回第一个使谓词返回非0值的元素。
auto wc = find_if(words.begin(), words.end(), [sz](const string &a){return a.size() >= sz;});
for_each
:- 接受一个可调用对象,并对序列中每个元素调用此对象。
for_each(wc, words.end(), [](const string &s){cout << s << " ";})
练习10.14
编写一个
lambda
,接受两个int
,返回它们的和。
auto f = [](int i, int j) { return i + j; };
练习10.15
编写一个
lambda
,捕获它所在函数的int
,并接受一个int
参数。lambda
应该返回捕获的int
和int
参数的和。
解:
int x = 10;
auto f = [x](int i) { i + x; };
练习10.16
使用
lambda
编写你自己版本的biggies
。
解:
#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
。
解:
#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
类似,在划分后的序列中维持原有元素的顺序。
解:
#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;
}
lambda捕获和返回
- 定义
lambda
时会生成一个新的类类型和该类型的一个对象。 - 默认情况下,从
lambda
生成的类都包含一个对应该lambda
所捕获的变量的数据成员,在lambda
对象创建时被初始化。 - 值捕获:前提是变量可以拷贝,
size_t v1 = 42; auto f = [v1] {return v1;};
。 - 引用捕获:必须保证在
lambda
执行时,变量是存在的,auto f2 = [&v1] {return v1;};
- 尽量减少捕获的数据量,尽可能避免捕获指针或引用。
- 隐式捕获:让编译器推断捕获列表,在捕获列表中写一个
&
(引用方式)或=
(值方式)。auto f3 = [=] {return v1;}
lambda捕获列表:
捕获列表 | 解释 |
---|---|
[] |
空捕获列表。lambda 不能使用所在函数中的变量。一个lambda 只有在捕获变量后才能使用它们。 |
[names] |
names 是一个逗号分隔的名字列表,这些名字都是在lambda 所在函数的局部变量,捕获列表中的变量都被拷贝,名字前如果使用了& ,则采用引用捕获方式。 |
[&] |
隐式捕获列表,采用引用捕获方式。lambda 体中所使用的来自所在函数的实体都采用引用方式使用。 |
[=] |
隐式捕获列表,采用值捕获方式。 |
[&, identifier_list] |
identifier_list 是一个逗号分隔的列表,包含0个或多个来自所在函数的变量。这些变量采用值捕获方式,而任何隐式捕获的变量都采用引用方式捕获。identifier_list 中的名字前面不能使用& |
[=, identifier_list] |
identifier_list 中的变量采用引用方式捕获,而任何隐式捕获的变量都采用值方式捕获。identifier_list 中的名字不能包括this ,且前面必须使用& |
练习10.20
标准库定义了一个名为
count_if
的算法。类似find_if
,此函数接受一对迭代器,表示一个输入范围,还接受一个谓词,会对输入范围中每个元素执行。count_if
返回一个计数值,表示谓词有多少次为真。使用count_if
重写我们程序中统计有多少单词长度超过6的部分。
解:
#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。
解:
int i = 10;
auto f = [&i]() -> bool { return (i == 0 ? true : !(i--)); };
while (!f()) cout << i << endl;
参数绑定
lambda
表达式更适合在一两个地方使用的简单操作。- 如果是很多地方使用相同的操作,还是需要定义函数。
- 函数如何包装成一元谓词?使用参数绑定。
- 标准库
bind
函数:- 定义在头文件
functional
中,可以看做为一个通用的函数适配器。 auto newCallable = bind(callable, arg_list);
- 我们再调用
newCallable
的时候,newCallable
会调用callable
并传递给它arg_list
中的参数。 _n
代表第n个位置的参数。定义在placeholders
的命名空间中。using std::placeholder::_1;
auto g = bind(f, a, b, _2, c, _1);
,调用g(_1, _2)
实际上调用f(a, b, _2, c, _1)
- 非占位符的参数要使用引用传参,必须使用标准库
ref
函数或者cref
函数。
- 定义在头文件
练习10.22
重写统计长度小于等于6的单词数量的程序,使用函数代替
lambda
。
#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
长度的值。
解:
#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
重写此函数。
解:
#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);
}
再探迭代器
插入迭代器
- 插入器是一种迭代器适配器,接受一个容器,生成一个迭代器,能实现向给定容器添加元素。
- 三种类型:
back_inserter
:创建一个使用push_back
的迭代器。front_inserter
创建一个使用push_front
的迭代器。inserter
创建一个使用insert
的迭代器。接受第二个参数,即一个指向给定容器的迭代器,元素会被查到迭代器所指向的元素之前。
插入迭代器操作:
操作 | 解释 |
---|---|
it=t |
在it 指定的当前位置插入值t 。假定c 是it 绑定的容器,依赖于插入迭代器的不同种类,此赋值会分别调用c.push_back(t) 、c.push_front(t) 、c.insert(t, p) ,其中p 是传递给inserter 的迭代器位置 |
*it, ++it, it++ |
这些操作虽然存在,但不会对it 做任何事情,每个操作都返回it |
练习10.26
解释三种插入迭代器的不同之处。
解:
back_inserter
使用push_back
。front_inserter
使用push_front
。inserter
使用insert
,此函数接受第二个参数,这个参数必须是一个指向给定容器的迭代器。元素将被插入到给定迭代器所表示的元素之前。
练习10.27
除了
unique
之外,标准库还定义了名为unique_copy
的函数,它接受第三个迭代器,表示拷贝不重复元素的目的位置。编写一个程序,使用unique_copy
将一个vector
中不重复的元素拷贝到一个初始化为空的list
中。
解:
#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
,估计输出序列是怎样的,运行程序验证你的估计是否正确。
解:
#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);
}
前两种为正序,第三种为逆序,输出和预计一样。
iostream迭代器
- 迭代器可与输入或输出流绑定在一起,用于迭代遍历所关联的 IO 流。
- 通过使用流迭代器,我们可以用泛型算法从流对象中读取数据以及向其写入数据。
istream_iterator的操作:
操作 | 解释 |
---|---|
istream_iterator<T> in(is); |
in 从输入流is 读取类型为T 的值 |
istream_iterator<T> end; |
读取类型是T 的值的istream_iterator 迭代器,表示尾后位置 |
in1 == in2 |
in1 和in2 必须读取相同类型。如果他们都是尾后迭代器,或绑定到相同的输入,则两者相等。 |
in1 != in2 |
类似上条 |
*in |
返回从流中读取的值 |
in->mem |
与*(in).mem 含义相同 |
++in, in++ |
使用元素类型所定义的>> 运算符从流中读取下一个值。前置版本返回一个指向递增后迭代器的引用,后置版本返回旧值。 |
ostream_iterator的操作:
操作 | 解释 |
---|---|
ostream_iterator<T> out(os); |
out 将类型为T 的值写到输出流os 中 |
ostream_iterator<T> out(os, d); |
out 将类型为T 的值写到输出流os 中,每个值后面都输出一个d 。d 指向一个空字符结尾的字符数组。 |
out = val |
用<< 运算符将val 写入到out 所绑定的ostream 中。val 的类型必须和out 可写的类型兼容。 |
*out, ++out, out++ |
这些运算符是存在的,但不对out 做任何事情。每个运算符都返回out 。 |
练习10.29
编写程序,使用流迭代器读取一个文本文件,存入一个
vector
中的string
里。
解:
#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
使用流迭代器、
sort
和copy
从标准输入读取一个整数序列,将其排序,并将结果写到标准输出。
解:
#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
。
解:
#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
求和。
解:
#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
将奇数写入第一个输入文件,每个值后面都跟一个空格。将偶数写入第二个输出文件,每个值都独占一行。
解:
#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;
}
反向迭代器
- 反向迭代器就是在容器中从尾元素向首元素反向移动的迭代器。
- 对于反向迭代器,递增和递减的操作含义会颠倒。
- 实现向后遍历,配合
rbegin
和rend
。
练习10.34
使用
reverse_iterator
逆序打印一个vector
。
解:
#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
。
解:
#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的元素。
解:
#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
中。
解:
#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;
}
泛型算法结构
5类迭代器
迭代器类别 | 解释 | 支持的操作 |
---|---|---|
输入迭代器 | 只读,不写;单遍扫描,只能递增 | == ,!= ,++ ,* ,-> |
输出迭代器 | 只写,不读;单遍扫描,只能递增 | ++ ,* |
前向迭代器 | 可读写;多遍扫描,只能递增 | == ,!= ,++ ,* ,-> |
双向迭代器 | 可读写;多遍扫描,可递增递减 | == ,!= ,++ ,-- ,* ,-> |
随机访问迭代器 | 可读写,多遍扫描,支持全部迭代器运算 | == ,!= ,< ,<= ,> ,>= ,++ ,-- ,+ ,+= ,- ,-= ,* ,-> ,iter[n] ==*(iter[n]) |
练习10.38
列出5个迭代器类别,以及每类迭代器所支持的操作。
- 输入迭代器 :
==
,!=
,++
,*
,->
- 输出迭代器 :
++
,*
- 前向迭代器 :
==
,!=
,++
,*
,->
- 双向迭代器 :
==
,!=
,++
,--
,*
,->
- 随机访问迭代器 :
==
,!=
,<
,<=
,>
,>=
,++
,--
,+
,+=
,-
,-=
,*
,->
,iter[n]
==*(iter+n)
练习10.39
list
上的迭代器属于哪类?vector
呢?
list
上的迭代器是 双向迭代器vector
上的迭代器是 随机访问迭代器
练习10.40
你认为
copy
要求哪类迭代器?reverse
和unique
呢?
copy
需要两个输入迭代器,一个输出迭代器reverse
需要双向迭代器unique
需要随机访问迭代器
算法的形参模式
alg(beg, end, other args);
alg(beg, end, dest, other args);
alg(beg, end, beg2, other args);
alg(beg, end, beg2, end2, other args);
其中,alg
是算法名称,beg
和end
表示算法所操作的输入范围。dest
、beg2
、end2
都是迭代器参数,是否使用要依赖于执行的操作。
算法命名规范
- 一些算法使用重载形式传递一个谓词。
- 接受一个元素值的算法通常有一个不同名的版本:加
_if
,接受一个谓词代替元素值。 - 区分拷贝元素的版本和不拷贝的版本:拷贝版本通常加
_copy
。
练习10.41
仅根据算法和参数的名字,描述下面每个标准库算法执行什么操作:
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
复制迭代器范围内的元素到目标迭代器位置,满足谓词条件的元素用新值替换
特定容器算法
- 对于
list
和forward_list
,优先使用成员函数版本的算法而不是通用算法。
list和forward_list成员函数版本的算法:
操作 | 解释 |
---|---|
lst.merge(lst2) |
将来自lst2 的元素合并入lst ,二者都必须是有序的,元素将从lst2 中删除。 |
lst.merge(lst2, comp) |
同上,给定比较操作。 |
lst.remove(val) |
调用erase 删除掉与给定值相等(==)的每个元素 |
lst.remove_if(pred) |
调用erase 删除掉令一元谓词为真的每个元素 |
lst.reverse() |
反转lst 中元素的顺序 |
lst.sort() |
使用< 排序元素 |
lst.sort(comp) |
使用给定比较操作排序元素 |
lst.unique() |
调用erase 删除同一个值的连续拷贝。使用== 。 |
lst.unique(pred) |
调用erase 删除同一个值的连续拷贝。使用给定的二元谓词。 |
- 上面的操作都返回
void
list和forward_list的splice成员函数版本的参数:
参数 | 解释 |
---|---|
(p, lst2) |
p 是一个指向lst 中元素的迭代器,或者一个指向flst 首前位置的迭代器。函数将lst2 中的所有元素移动到lst 中p 之前的位置或是flst 中p 之后的位置。将元素从lst2 中删除。lst2 的类型必须和lst 相同,而且不能是同一个链表。 |
(p, lst2, p2) |
同上,p2 是一个指向lst2 中位置的有效的迭代器,将p2 指向的元素移动到lst 中,或将p2 之后的元素移动到flst 中。lst2 可以是于lst 或flst 相同的链表。 |
(p, lst2, b, e) |
b 和e 表示lst2 中的合法范围。将给定范围中的元素从lst2 移动到lst 或first 中。lst2 与lst 可以使相同的链表,但p 不能指向给定范围中的元素。 |
- 使用
lst.splice(args)
或flst.splice_after(args)
练习10.42
使用
list
代替vector
重新实现10.2.3节中的去除重复单词的程序。
解:
#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;
}
标签:std,vector,end,迭代,第十章,算法,vs,泛型,include
From: https://www.cnblogs.com/Epiephany/p/17135539.html