星星博客 »  > 

3-泛型编程风格

目录

            • 3.1指针的算术运算(The Arithmetic of Pointers)
            • 3.2了解Iterator(泛型指针)(Making Sense of Iterators)
            • 3.3所有容器的共通操作(Operations Common to All Containers)
            • 3.4使用顺序性容器(Using the Sequential Containers)
            • 3.5使用泛型算法(Using the Generic Algorithms)
            • 3.6如何设计一个泛型算法(How to Design a Generic Algorithm)
            • Function Object
            • Function Object Adapter
            • 3.7使用Map(Using a Map)
            • 3.8使用Set(Using a Set)
            • 3.9如何使用Iterator Inserter(How to User Iterator Inserters)
            • 3.10 使用iostream Iterator(Using the iostream Iterators)

标准模板库:Standard Template Library( STL)

STL
容器container
vector list set map ...
泛型算法generic algorithm
find sort replace merge ...
  1. 顺序性容器(sequential container):vector、list。主要用于进行迭代(iterate)操作。
  2. 关联容器(associative container):map、set。主要用于快速查找容器中的元素值。

泛型算法提供了许多可作用于容器类及数组类型上的操作。这些算法之所以被称为泛型(generic),是因为它们和它们想要的操作的元素类型无关。

泛型算法系通过function template技术,达到“与操作对象的类型相互独立”的目的。而实现“与操作容器无关”,就是不要直接在容器身上进行操作。而是借由一对iterator(first和last),标示我们要进行迭代的元素范围。

3.1指针的算术运算(The Arithmetic of Pointers)

给定一个vector和一个值,如果此值在vector内,返回一个指针指向该值;反之则返回0。下面是代码:

  1. 处理整数
int* find(const vector<int> &vec, int value) {
	for (int i = 0; i < vec.size(); i++)
		if (vec[i] == value)
			return &vec[i];
	return 0;
}
  1. 可以处理更多类型——前提是该类型定义有equality(相等)运算符
template <typename elemType>
elemType* find(const vector<elemType> &vec, const elemType &value) {
	for (int i = 0; i < vec.size(); i++)
		if (vec[i] == value)
			return &vec[i];
	return 0;
}
  1. 不用重载的方式让函数可以同时处理vector和array内的任意类型元素——前提是该类型的equality运算符皆已定义
  • 先了解array如何被传入函数,以及array如何被函数返回
int min(int array[24]) {...}

1.min()似乎仅能接受拥有24个元素的array? 错!我们可以传递任意大小的array给min()。
2.以传值方式传入? 错!当【数组】被传给函数或由函数返回,仅有第一个元素的【地址】会被传递。

  • 以下的min()函数声明就精确多了
int min(int *array) {...}

由于只知道array的首地址,没传入array的size,这就迫使我们必须为不同大小的array编写其专属的min()函数。

  • ➀增加一个参数,表示array的大小
template <typename elemType>
elemType* find(const elemType *array, int size, const elemType &value); 
  • ➁传入另一个地址,指示array读取操作的终点(此值我们称为**“标兵”**)
template <typename elemType>
elemType* find(const elemType *array, const elemType *sentinel, const elemType &value); 

以上操作后,array从参数列表中彻底消失了。
通过下标(subscript)访问元素:

template <typename elemType>
elemType* find(const elemType *array, int size, const elemType &value) {
	if (!array || size < 1)
		return 0;
	for (int i = 0; i < size; i++)
		if (array[i] == value)// 可以对指针使用subscript(下标)运算符
			return &array[i];
	return 0;
}

通过指针直接访问元素:

template <typename elemType>
elemType* find(const elemType *array, int size, const elemType &value) {
	if (!array || size < 1)
		return 0;
	for (int i = 0; i < size; i++, array++)// array++:指针的算术运算
		if (*array == value)// 用*array提领其值
			return &array[i];
	return 0;
}

下面代码中将array的声明从参数列表中完全移除,第二个指针参数扮演着标兵的角色:

template <typename elemType>
elemType* find(const elemType *first, const elemType *last, const elemType &value) {
	if (!first || !last)// 注:first是首元素地址,而last是【最后一个元素的下一个地址】
		return 0;
	// 当first不等于last,就把value拿来和first所指的元素比较。
	// 如果两者相等,便返回first,否则将first递增1,令它指向下一个元素。
	for (; first != last; first++)
		if (*first == value)
			return first;
	return 0;
}

如何调用find()呢?

int    ia[8] = {1, 1, 2, 3, 5, 8, 13, 21};
double da[6] = {1.5, 2.0, 2.5, 3.0, 3.5, 4.0};
string sa[4] = {"pooh", "piglet", "eeyore", "tigger"};

int    *pi = find(ia, ia + 8, ia[3]);
double *pd = find(da, da + 6, da[3]);
string *ps = find(sa, sa + 4, sa[3]);

vector和array相同,都是以一块连续内存储存其所有元素。
但是,vector可以是空的,array则不然。

如果svec为空,则下面代码便会产生一个运行时错误:

find(&svec[0], &svec[svec.size()], search_value);

所以,可以先作一下判断:

vector<string> svec;
if (!svec.empty()) { ... }

通常,我们将“取用第一个元素的地址”的操作包装为函数:

template <typename elemType>
inline elemType* begin(const vector<elemType> &vec) {
	return vec.empty() ? 0 : &vec[0];
}

上述begin()函数对应的函数就是end(),end()函数会返回0或vector最后元素的下一个地址。
采用这种方式,我们便有了安全的、放之四海皆准的方式 ,使find()可应用于任意vector之上。

find(begin(svec), end(svec), search_value);

现在,让我们扩展find(),让它也能支持标准库所提供的list类别。

list也是一个容器。list的元素以一组指针相互链接(linked):前向(forward)指针指向下一个(next)元素;向后(backward)指针指向上一个(preceding)元素。
指针的算术运算符并不适用于list,因为指针的算术运算必须首先假设所有元素都储存在连续空间里。

我们不需要提供另一个find()函数来支持list。事实上,除了参数列表之外,find()的实现内容一点也不需要改变。
解决这个问题的办法是,在底层指针的行为之上提供一层抽象,取代程序原本的“指针直接操作”方式。我们把底层指针的处理通通放在此抽象层中,让用户无须直接面对指针操作。

3.2了解Iterator(泛型指针)(Making Sense of Iterators)

迭代器与指针:迭代器(Iterator)是指针(pointer)的泛化,提供了对对象的间接访问。迭代器针对容器,而指针类型针对数组。

这个抽象层如何实现?是的,我们需要一组对象,可提供有如内置运算符(++, *, ==, !=)一般的运算符,并允许我们只为这些运算符提供一份实现代码即可。
接下来要设计一组iterator class,让我们得以使用“和指针相同的语法”来进行程序的编写。
如果first和last都是list的iterator,我们可以这样写:

// first和last皆为iterator class object(泛型指针类对象)
while (first != last) {// inequality运算符
	cout << *first << ' ';// dereference运算符
	++first;// increment运算符
}

以上操作好像把first和last当作指针一样。
差别在于:其dereference(提领, *)运算符、inequality(不等, !=)运算符、increment(递增, ++)运算符是由iterator class(泛型指针类)内相关的inline函数提供
每个标准容器都提供有一个名为begin()的操作函数,返回一个iterator,指向第一个元素;另一个end()函数返回指向最后一个元素的下一位置的iterator。因此,不论此刻如何定义iterator对象,以下都是对iterator进行赋值(assign)、比较(compare)、递增(increment)、提领(dereference)操作:

for (iter = svec.begin(); iter != svec.end(); iter++)
	cout << *iter << ' ';

以上代码中的iterator对象,有些信息是在对iterator的定义中应该提供的:
(1)迭代对象(某个容器)的类型,用来决定如何访问下一元素;
(2)iterator所指的元素类型,用来决定iterator提领操作的返回值。

以上是iterator对象应该如何定义的一些说明和解释。
下面看看标准库中的iterator对象:

vector<string> svec;
vector<string>::iterator iter = svec.begin();

此处iter被定义为一个iterator指向一个vector,后者的元素类型为string。其初值指向svec的第一个元素。::表示此iterator是位于string vector定义内的嵌套[nested]类型
对于const vector,我们要用const_iterator来进行遍历操作:

const vector<string> cs_vec;
vector<string>::const_iterator iter = cs_vec.begin();

const_iterator允许我们读取vector的元素,但不允许任何写入操作。
要通过iterator取得元素值,采用一般指针的提领方式:

cout << "string value of element:" << *iter;

同理,如果要通过iter调用底部的string元素所提供的操作,可以使用arrow运算符:

cout << "size of element " + *iter + " is " + iter->size();

以下是重新实现后的display()函数:

template <typename elemType>
void display(const vector<elemType> &vec, ostream &os) {
	vector<elemType>::const_iterator iter = vec.begin();
	vector<elemType>::const_iterator end_it = vec.end();
	for (; iter != end_it; iter++)// 如果vec是空的,iter就等于end_it了
		os << *iter << ' ';
	os << endl;
}

现在重新实现find(),让它同时支持两种形式:➀一对指针;➁一对指向某种容器的iterator。以下代码对➀或➁两种情况都是适用的:

template <typename iteratorType, typename elemType>
iteratorType find(iteratorType first, iteratorType last, const elemType &value) {
	for (; first != last; first++)
		if (value == *first)
			return first;
	return last;
}

现在可以使用翻修过的find()来处理array、vector和list:

const int asize = 8;
int ia[asize] = {1, 1, 2, 3, 5, 8, 13, 21};
vector<int> ivec(ia, ia + asize);
list<int> ilist(ia, ia + asize);

int *pia = find(ia, ia + asize, 1024);
if (pia != ia + asize)
	// 找到了......
vector<int>::iterator it;
it = find(ivec.begin(), ivec.end(), 1024);
if (it != ivec.end())
	// 找到了......
list<int>::iterator iter;
iter = find(ilist.begin(), ilist.end(), 1024);
if (iter != ilist.end())
	// 找到了......

如果用户希望赋予equality运算符不同的意义,这个find()的弹性便嫌不足了。如何才能增加其弹性?
解法之一:传入一个函数指针,取代原本固定使用的equality运算符。
解法之二:运用所谓的function object(这是一种特殊的class)。

下一个目标,是将现有的find()版本演化为泛型算法。
标准库提供了超过60个泛型算法(事实上几近75个)。
●搜索算法(search algorithm):find()、count()、adjacent_find()、find_if()、count_if()、binary_search()、find_first_of()。
●排序(sorting)及次序整理(ordering)算法:merge()、partial_sort()、partition()、random_shuffle()、reverse()、rotate()、sort()。
●复制(copy)、删除(deletion)、替换(substitution)算法:copy()、remove()、remove_if()、replace()、replace_if()、swap()、unique()。
●关系(relational)算法:equal()、includes()、mismatch()。
●生成(generation)与质变(mutation)算法:fill()、for_each()、generate()、transform()。
●数值(numeric)算法:accmulate()、adjacent_difference()、partial_sum()、inner_product()。
●集合(set)算法:set_union()、set_difference()。

3.3所有容器的共通操作(Operations Common to All Containers)

下列为所有容器类(以及string类)的共通操作:
●equality(==)和inequality(!=)运算符,返回true或false。
●assignment(=)运算符,将某个容器复制给另一个容器。
empty()会在容器无任何元素时返回true,否则返回false。
size()返回容器内目前持有的元素个数。
clear()删除所有元素。

void comp(vector<int> &v1, vector<int> &v2) {
	if (v1 == v2) return;
	if (v1.empty() || v2.empty()) return;
	vector<int> t;
	t = v1.size() > v2.size() ? v1 : v2;
	t.clear();
}

每个容器都提供了begin()、end()函数和insert()、erase()函数:
begin()返回一个iterator,指向容器的第一个元素。
end()返回一个iterator,指向容器最后一个元素的下一位置。
insert()将单一或某个范围内的元素插入容器内。
erase()将容器内的单一元素或某个范围内的元素删除。
push_back():末端插入一个元素;
pop_back():删除最后一个元素;
insert():在某个位置插入一个或多个元素;

3.4使用顺序性容器(Using the Sequential Containers)

顺序性容器用来维护一组排列有序、类型相同的元素。
vectorlist是两个主要的顺序性容器。
vector以一块连续内存来存放元素。vector内的每个元素都被储存在距离起始点的固定偏移位置上。

对vector进行随机访问(random access)——例如先取其第5个元素,再取其第17个元素,然后取其第9个元素——颇有效率。
如果将元素插入任意位置,而不是vector的末端,那么效率很低。因为,插入位置右端的每个元素,都必须被复制一份,依次向右移动。同理,删除除vector最后一个元素以外的任意元素,同样缺乏效率。

list以双向链接(double-linked)而非连续内存来储存内容,因此可以执行前进或后退操作。list中的每个元素都包含三个字段:value、back指针(指向前一个元素)、front指针(指向下一个元素)。

在list的任意位置进行元素的插入或删除操作,都颇具效率。因为,list本身只需适当设定back指针和front指针即可。
如果对list进行随机访问,则效率不彰。例如,依次访问第5、17、9个元素,都必须遍历介于其中的所有元素。

第三种顺序性容器是deque

deque行为与vector颇为相似——都以连续内存储存元素。
与vector不同的是,deque对于最前端元素的插入和删除操作,效率更高。
如果要在容器最前端插入元素并执行末端删除操作,那么deque便很理想。

要使用顺序性容器,首先必须包含相关的头文件,也就是以下三者之一:

#include <vector>
#include <list>
#include <deque>

定义顺序性容器对象的方式有五种:
➊产生空的容器:

list<string> slist;
vector<int> ivec;

➋产生特定大小的容器:(每个元素都以默认值作为初值。)

list<int> ilist(1024);
vector<string> svec(32);

➌产生特定大小的容器,并为每个元素指定初值:

vector<int> ivec(10, -1);
list<string> slist(16, "unassigned");

➍通过一对iterator产生容器:

int ia[8] = {1, 1, 2, 3, 5, 8, 13, 21};
vector<int> fib(ia, ia + 8);

➎根据某个容器产生出新容器:(复制原容器内的元素,作为新容器初值。)

list<string> slist;// 空容器
list<string> slist2(slist);// 将slist复制给slist2

list和deque独有的函数:push_front()pop_front()
pop_back()和pop_front()这两个操作函数并不会返回被删除的元素值。

要读取最前端元素的值,用:front()
要读取末端元素的值,用:back()

#include <deque>
deque<int> a_line;
int ival;
while (cin >> ival) {
	a_line.push_back(ival);// 将ival插入a_line末端
	int curr_value = a_line.front();// 读取a_line最前端元素的值
	// ... 进行一些操作
	a_line.pop_front();// 删除a_line最前端元素
}

每个容器除了拥有通用的插入函数insert(),还支持四种变形:

iterator insert(iterator position, elemType value)
将value插入position之前。它会返回一个iterator,指向被插入的元素。
————————————————————————————————————————————————
以下代码将ival插入ilist内,并维持其递增次序:
list<int> ilist;
// ... 填充ilist
list<int>::iterator it = ilist.begin();
while (it != ilist.end) {
	if (*it >= ival) {
		ilist.insert(it, ival);
		break;
	}
	++it;
}
if (it == ilist.end())
	ilist.push_back(ival);

iterator insert(iterator position, int count, elemType value)
在position之前插入count个元素,这些元素的值都和value相同。————————————————————————————————————————————————
例:
string sval("Part Two");
list<string> slist;
// ... 填充slist
list<string>::iterator it = find(slist.begin(), slist.end(), sval);
slist.insert(it, 8, string("dummy"));

void insert(iterator1 position, iterator2 first, iterator2 last)
在position之前插入[first,last)所标示的各个元素。
————————————————————————————————————————————————
例:
int ia1[7] = {1, 1, 2, 3, 5, 55, 89};
int ia2[4] = {8, 13, 21, 34};
list<int> elems(ia1, ia1 + 7);
list<int>::iterator it = find(elems.begin(), elems.end(), 55);
elems.insert(it, ia2, ia2 + 4);

iterator insert(iterator position)
在position之前插入元素。元素的初值为其所属类型的默认值。

每个容器除了拥有通用的删除函数erase(),还支持两种变形:

iterator erase(iterator posit)
删除posit所指的元素。
————————————————————————————————————————————————
例如,删除slist中第一个“元素值为str”的元素:
list<string>::iterator it = find(slist.begin(), slist.end(), str);
slist.erase(it);// 返回的iterator对象指向被删除之最后一个元素的下一个位置。

iterator erase(iterator first, iterator last)
删除除[first,last)范围内的元素。
————————————————————————————————————————————————
例如,把slist中“元素值为str”和“元素值为sval”两元素间的所有元素删除掉:
list<string>::iterator first = slist.begin(), last = slist.end();
list<string>::iterator it1 = find(first, last, str);
list<string>::iterator it2 = find(first, last, sval);
slist.erase(it1, it2);// 返回的iterator对象指向被删除之最后一个元素的下一个位置。

list并不支持iterator的偏移运算,这也是我们不能写:slist.erase(it1, it1 + num_tries);而必须将it1和it2传入erase()的原因。

下面看一个完整的例子:

// inserting into a list
#include <iostream>
#include <list>
#include <vector>
int main () {
  std::list<int> mylist;
  std::list<int>::iterator it;
  // set some initial values:
  for (int i=1; i<=5; ++i) 
  	mylist.push_back(i); // 1 2 3 4 5
  it = mylist.begin();
  ++it;// it points now to number 2
  mylist.insert(it, 10);// 1 10 2 3 4 5
  // "it" still points to number 2
  mylist.insert(it, 2, 20);// 1 10 20 20 2 3 4 5
  --it;// it points now to the second 20
  std::vector<int> myvector(2, 30);
  mylist.insert(it, myvector.begin(), myvector.end());
  // 1 10 20 30 30 20 2 3 4 5
  std::cout << "mylist contains:";
  for (it=mylist.begin(); it!=mylist.end(); ++it)
  	std::cout << ' ' << *it;
  std::cout << '\n';
  return 0;
}
mylist contains: 1 10 20 30 30 20 2 3 4 5
3.5使用泛型算法(Using the Generic Algorithms)

要使用泛型算法,首先得包含头文件:

#include <algorithm>

我们以vector来储存数列,以此练习泛型算法的运用。
如果给定值已存在于数列中,is_elem()返回true,否则返回false。
下面为四种可能的泛型搜索算法:
➊find()用于搜索无序(unordered)集合中是否存在某值。搜索范围由iterator[first,last)标出。如果找到目标,find()返回一个iterator指向该值,否则返回一个iterator指向last。
➋binary_search()用于有序(sorted)集合的搜索。如果搜索到目标,返回true;否则返回false。
binary_search()比find()更有效率,因为find()属于linear search,效率较binary search差。
➌count()返回数值相等的元素数目。
➍search()比对某个容器内是否存在某个子序列。例如给定序列{1, 3, 5, 7, 2, 9},如果搜索子序列{5, 7, 2},则search()会返回一个iterator指向子序列起始处。如果子序列不存在,就返回一个iterator指向容器末尾。

Fibonacci数列是个递增序列,因此binary_search()是最佳选择:

#include <algorithm>
bool is_elem(vector<int> &vec, int elem) {
	// 如果elem=34,意指Fibonacci数列的第9个元素
	// 而我们的vector仅储存前6个元素:1,1,2,3,5,8,那么搜索操作不成功
	// 调用binary_search()之前,必须先检查是否需要扩展vector
	return binary_search(vec.begin(), vec.end(), elem);
}

调用binary_search()之前,必须确定数列中存有足够数量的元素。即,elem必须在此数列之内。
有个泛型算法max_element(),将一对iterator传给它,会返回该范围内的最大值。

#include <algorithm>
extern bool grow_vec(vector<int>&, int);
bool is_elem(vector<int> &vec, int elem) {
	int max_value = max_element(vec.begin(), vec.end());
	if (max_value < elem)
		return grow_vec(vec, elem);
	if (max_value == elem)
		return true;
	return binary_search(vec.begin(), vec.end(), elem);
}

grow_vec()会持续地将数列元素一一加入vector,直到加入的数值大于或等于elem。
由于我们的vector元素是递增排列的,所以int max_value = vec.empty()? 0 : vec[vec.size()-1]。

binary_search()要求,其作用对象必须经过排序(sorted),这一责任由程序员承担。
如果我们不确定是否已排序,可以将容器先复制一份:

vector<int> temp(vec.size());
copy(vec.begin(), vec.end(), temp.begin());
// 然后,先对新容器排序操作,再调用binary_search()
sort(temp.begin(), temp.end());
return binary_search(temp.begin(), temp.end(), elem);
3.6如何设计一个泛型算法(How to Design a Generic Algorithm)

任务:有一个整数vector,我们必须返回一个新的vector,其中内含原vector之中小于10的所有数值。
一个快速但缺乏弹性的解法是:

vector<int> less_than(const vector<int> &vec, int less_than_val) {// 此处less_than_val=10
	vector<int> nvec;
	for (int i = 0; i < vec.size(); i++)
		if (vec[ix] < less_than_val)
			nvec.push_back(vec[i]);
	return nvec;
}

有可能小于10也可能大于10还可能等于10,并且10这个数也可能更改。现取函数名为filter:

vector<int> filter(const vector<int> &vec, int filter_value, bool (*pred)(int, int)) {
	vector<int> nvec;
	for (int i = 0; i < vec.size(); i++)
		// 调用pred所指函数。比较vec[i]和filter_value。
		if (pred(vec[i], filter_value))
			nvec.push_back(vec[i]);
	return nvec;
}
// 满足函数指针的函数
bool less_than(int v1, int v2) {
	return v1 < v2 ? true : false;
}
bool greater_than(int v1, int v2) {
	return v1 > v2 ? true : false;
}

下面是filter()函数使用方式:

vector<int> big_vec;
int value;
// ...填充big_vec和value
vector<int> lt_10 = filter(big_vec, value, less_than);

让我们找出所有等于10的元素吧:(count_occurs():不对任一元素进行两次以上的查看)

int count_occurs(const vector<int> &vec, int val) {
	vector<int>::const_iterator iter = vec.begin();
	int occurs_count = 0;
	while ((iter = find(iter, vec.end(), val))!= vec.end()) {
		++occurs_count;
		++iter;// 指向下一个元素
	}
	return occurs_count;
Function Object

标准库预先定义了些function object。所谓function object是某种class的实例对象,这类class对function call运算符做了重载操作,如此一来可使function object被当成一般函数来使用。

function object实现了我们原本可能以独立函数加以定义的事物。但又何必如此呢?
主要是为了效率。我们可以令call运算符成为inline,从而消除“通过函数指针来调用函数”时需要付出的额外代价。

标准库事先定义了一组function object,分为:
算术运算(arithmetic)、关系运算(relational)和逻辑运算(logical)三大类。
以下列表中的type在实际使用时会替换为内置类型或class类型:

..
6个算术运算plus< type>,minus< type>,negate< type>,multiplies< type>,divides< type>,modules< type>
6个关系运算less< type>,less_equal< type>,greater< type>,greater_equal< type>,equal_to< type>,not_equal_to< type>
3个逻辑运算logical_and< type>,logical_or< type>,logic_not< type>

要使用事先定义的function object,首先得包含相关头文件:

#include <functional>

默认情况下sort()是升序排列,我们将元素降序排列:

sort(vec.begin(), vec.end(), greater<int>());

其中的greater< int>()会产生一个未命名的class template object,传给sort()。
binary_search()期望其搜索对象先经过排序,为了正确搜索vector,就必须传给它某个function object object,供vector排序使用:

binary_search(vec.begin(), vec.end(), elem, greater<int>());

我们对Fibonacci数列可以做些其他操作,如:每个元素和自身相加、和自身相乘、被加到对应的Pell数列等等。做法之一是使用泛型算法transform()并搭配plus< int>和multiplies< int>。
我们必须传给transform()的参数有:
➀一对iterator,标示出欲转换的元素范围;
➁一个iterator,所指元素将应用于转换上;
➂一个iterator,所指位置(及其后面的空间)用来存放转换结果;
➃一个function object,表现出我们想要应用的转换操作。
以下是将Pell数列加到Fibonacci数列的写法:

transform(fib.begin, fib.end,    //➀
          pell.begin(),          //➁
          fib_plus_pell.begin(), //➂
          plus<int>);            //➃
Function Object Adapter

function object less< type>期望外界传入两个值,如果第一个值小于第二个值就返回true。本例中,每个元素都必须和用户所指定的数值进行比较。理想情形下,我们需要将less< type>转化为一个一元(unary)运算符。这可通过“将其第二个参数绑定(bind)至用户指定的数值”完成。这么一来less< type>便会将每个元素拿出来一一与用户指定的数值比较。
真的可以做到这样吗?是的。标准库提供adapter(适配器)便应此而生。

function object adapter会对function object进行修改操作。binder adapter(绑定适配器)会将function object的参数绑定至某特定值,使binary(二元) function object转化为unary(一元)function object。这正是我们需要的。

标准库提供了两个binder adapter
bind1st会将指定值绑定至第一操作数;bind2nd将指定值绑定至第二操作数。

vector<int> filter<const vector<int> &vec, int val, less<int> &lt) {
	vector<int> nvec;
	vector<int>::const_iterator iter = vec.begin();
	while ((iter = find_if(iter, vec.end(), bind2nd(lt, val))) != vec.end()) {
		nvec.push_back(*iter);
		iter++;
	}
	return nvec;
}

bind2nd(less< int>, val);会把val绑定于less< int>的第二个参数身上。于是,less< int>会将每个元素拿来和val比较。上例第一操作数是iter,第二操作数就是固定值val。如果iter<val则true。
find_if()的定义如下:

template <class InputIterator, class UnaryPredicate>
InputIterator find_if(InputIterator first, InputIterator last, UnaryPredicate pred);
●first、last:输入迭代器到序列的初始和最终位置。使用的范围是[first,last),它包含first和last之间的所有元素,包括first指向的元素,但不包括last指向的元素。
●pred:接受范围内的元素作为参数并返回可转换为bool类型的值的【一元函数】。返回的值表明该元素是否被认为是此函数的上下文中的匹配。 函数不能修改它的参数。 它可以是函数指针,也可以是函数对象(function object)。
●返回值:指向pred不返回false的范围内第一个元素的迭代器。 如果pred对所有元素都为false,则函数返回last。
这个函数模板的行为相当于:
template<class InputIterator, class UnaryPredicate>
InputIterator find_if(InputIterator first, InputIterator last, UnaryPredicate pred) {
  while (first!=last) {
    if (pred(*first)) return first;
    ++first;
  }
  return last;
}

下面看一个泛型函数find_if()的例子:

#include <iostream>     // std::cout
#include <algorithm>    // std::find_if
#include <vector>       // std::vector

bool IsOdd (int i) {
  return ((i%2)==1);
}

int main () {
  std::vector<int> myvector;
  myvector.push_back(10);
  myvector.push_back(25);
  myvector.push_back(40);
  myvector.push_back(55);

  std::vector<int>::iterator it = std::find_if (myvector.begin(), myvector.end(), IsOdd);
  std::cout << "The first odd value is " << *it << '\n';
  return 0;
}
The first odd value is 25

看一个bind2nd()和bind1st()的例子:

#include <iostream>
#include <functional>
#include <algorithm>
using namespace std;
int main () {
  int numbers[] = {10,-20,-30,40,-50};
  int cx;
  cx = count_if(numbers, numbers+5, bind2nd(less<int>(), 0));
  cout << "There are " << cx << " negative elements.\n";
  return 0;
}
There are 3 negative elements.
#include <iostream>
#include <functional>
#include <algorithm>
using namespace std;
int main () {
  int numbers[] = {10,20,30,40,50,10};
  int cx;
  cx = count_if(numbers, numbers+6, bind1st(equal_to<int>(), 10));
  cout << "There are " << cx << " elements that are equal to 10.\n";
  return 0;
}
There are 2 elements that are equal to 10.

如何消除filter()与vector元素类型,以及filter()与vector容器类型的依赖关系,以使filter()更加泛型化呢?

template <typename InputIterator, typename OutputInterator, typename ElemType, typename Comp>
OutputIterator filter(InputIterator first, InputIterator last, OutputIterator at, const ElemType &val, Comp pred) {
	while ((first = find_if(first, last, bind2nd(pred, val))) != last) {
		cout << "found value:" << *first << endl;
		*at++ = *first++;
	}
	return at;
}

现在测试以上filter()在array和vector上的使用:

int main() {
	const int value = 8;
	const int elem_size = 8;
	int ia[elem_size] = {12, 8, 43, 0, 6, 21, 3, 7};
	vector<int> ivec(ia, ia + elem_size);
	// 下面这个容器用来储存过滤结果
	int ia2[elem_size];
	vector<int> ivec2(elem_size);
	
	cout << "filtering integer array for values less than 8\n";
	filter(ia, ia + elem_size, ia2, value, less<int>());

	cout << "filtering integer vector for values greater than 8\n";
	filter(ivec.begin(), ivec.end(), ivec2.begin(), value, greater<int>());
}
filtering integer array for values less than 8
found value:0
found value:6
found value:3
found value:7
filtering integer vector for values greater than 8
found value:12
found value:43
found value:21

另一种adapter是所谓的negator,它会对function object的真伪值取反。
not1可对unary function object的真伪值取反,not2可对binary function object的真伪值取反。
例如,要找出所有大于或等于10的元素,可以将function object less< int>()的运算结果取反:

while ((iter = find_if(iter, vec.end(), not1(bind2nd(less<int>(), 10)))) != vec.end())

我们也有其他解法,比如下面这个non-template版本:

vector<int> sub_vec(const vector<int> &vec, int val) {
	vector<int> local_vec(vec);// 对副本进行操作
	sort(local_vec.begin(), local_vec.end());// 先排序
	vector<int>::iterator it = find_if(local_vec.begin(), local_vec.end(),
									   bind2nd(greater<int>(), val));
	local_vec.erase(it, local_vec.end());// 删除位置之后到末尾的所有元素
	return local_vec;
}
3.7使用Map(Using a Map)
#include <map>
#include <string>
map<string, int> words;// 带有string key和int value的map
words["vermeer"] = 1;// 输入key/value的最简单方式

以下for循环会打印所有单字及其出现次数:

map<string, int>::iterator it = words.begin();
for(; it != words.end(); ++it)
	cout << "key: " << it->first
		 << "value: " << it->second <<endl;

map对象有一个名为first的member,对应于key
另一个名为second的member,对应于value

查询map内是否存在某个key,有三种方法:
➊把key当成索引

int count = 0;
if (!(count = words["vermeer"]))
	// vermeer并不存在于words这个map内

缺点:如果key不存在于map内,这个key会自动加入map中,value则会被设置成所属类型的默认值。
➋利用map的find()函数

int count = 0;
map<string, int>::iterator it;
it = words.find("vermeer");
if (it != words.end())
	count = it->second;

➌利用map的count()函数(它返回某特定项在map内的个数)

int count = 0;
string search_word("vermeer");
if (words.count(search_word))// ok,它存在
	count = words[search_word];

如果我们需要储存多份相同的key值,就必须使用multimap

3.8使用Set(Using a Set)
#include<set>
#include<string>
set<string> word_exclusion;
string tword;
while (cin >> tword) {
	if (word_exclusion.count(tword))
		continue;
	words[tword]++;
}

对于任何key值,set只能存储一份。如果要储存多份相同的key值,必须使用multiset
默认情况下,set元素皆依据所属类型默认的less-than运算符进行排列,例如:

int ia[10] = {1, 3, 5, 8, 5, 3, 1, 5, 8, 1};
vector<int> vec(ia, ia + 10);
set<int> iset(vec.begin(), vec.end());
// iset的元素将是{1, 3, 5, 8}

插入单一元素:

iset.insert(ival);

插入某个范围的元素:

iset.insert(vec.begin(), vec.end());

在set身上进行迭代:

set<int>::iterator it = iset.begin();
for (; it != iset.end(); ++it)
	cout << *it << ' ';

在泛型算法中有不少和set相关的算法:set_intersection()、set_union()、set_difference()、set_symmetric_difference()。

3.9如何使用Iterator Inserter(How to User Iterator Inserters)

前面对filter()的实现,将源端(容器)中的每一个符合条件的元素一一赋值(assign)到目的端(容器):

while((first = find_if(first, last, bind2nd(pred, val))) != last)
	*at++ = *first++;

这种形式下,目的端的容器必须够大,以储存被赋值进来的每个元素。at每次递增后,at是否指向一个有效的容器位置,这是程序员的责任。
“确保at所指目的端容器的空间够大”,目的端容器的大小可能过大,也可能太小,这是个问题。
比如让目的端容器大小等于源端容器大小,但这样目的端容器就过大。

所有“会对元素进行复制行为”的泛型算法,例如copy()、copy_backwards()、remove_copy()、replace_copy()、unique_copy()等等,都和filter()的实现极为相似。每个算法都接受一个iterator,标示出复制的起始位置。每复制一个元素,都会被赋值(assigned),iterator则会递增到下个位置。

标准库提供了三个insertion adatper,这些adapter让我们得以避免使用容器的assignment运算符
back_inserter()会以容器push_back()函数取代assignment运算符。对于vector来说,这是比较适合的inserter。传入back_inserter的参数,应该就是容器本身:

vector<int> result_vec;
unique_copy(ivec.begin(), ivec.end(), back_inserter(result_vec));

inserter会以容器的insert()函数取代assignment运算符,它接受两个参数:一个容器,一个iterator,指向容器内的插入操作起点。

vector<string> svec_res;
unique_copy(svec.begin(), svec.end(), inserter(svec_res, svec_res.end()));

front_inserter()会以容器的push_front()函数取代assignment。这个inserter只适用于list和deque。

list<int> ilist_clone;
copy(ilist.begin(), ilist.end(), front_inserter(ilist_clone));

下面重新实现上述例子:

int main() {
	const int value = 8;
	const int elem_size = 8;
	int ia[elem_size] = {12, 8, 43, 0, 6, 21, 3, 7};
	vector<int> ivec(ia, ia + elem_size);
	int ia2[elem_size];// 内置数组不支持插入操作
	vector<int> ivec2;
	cout << "filtering integer array for values less than 8\n";
	filter(ia, ia + elem_size, ia2, value, less<int>());
	cout << "filtering integer vector for values greater than 8\n";
	filter(ivec.begin(), ivec.end(),
	       back_inserter(ivec2), value, greater<int>());
}

filter()会依次将每个元素赋值(assign)给目的端vector——本例为ivec2。由于本例并未设定ivec2的大小,所以赋值操作会产生运行时错误。但一旦将ivec2传给inserter adapter,元素的赋值操作(assignment)即被替换为插入操作。如果只在vector的末端插入元素,效率会比较高,因此我们选用back_inserter。

3.10 使用iostream Iterator(Using the iostream Iterators)

新任务:从标准输入设备读取一串string元素,将它们存到vector内,并进行排序,最后将这些字符串写回标准输出设备。一般解法如下:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	string word;
	vector<string> text;
	while (cin >> word)
		text.push_back(word);
	sort(text.begin(), text.end());
	for (i = 0; i < text.size(); ++i)
		cout << text[i] << ' ';
}

标准库定义有供输入及输出使用的iostream iterator类,称为istream_iteratorostream_iterator,分别支持单一类型的元素读取和写入。
先得包含头文件:

#include <iterator>

利用istream_iterator从标准输入设备读取字符串。我们需要一对iterator:first和last来标示元素范围。
first iterator:

istream_iterator<string> is(cin);

它是将is定义为一个绑定标准输入设备的istream_iterator。
last iterator:

istream_iterator<string> eof;

last iterator表示要读取的最后一个元素的下一位置。对标准输入设备而言,end-of-file即代表last。只要在定义istream_iterator时不为它指定istream对象,它便代表end-of-file。

可以这样使用:(由于不知为vector保留多少空间,所以选用了back_inserter)

copy(is, eof, back_inserter(text));

我们还需要一个ostream_iterator,标示字符串元素的输出位置。

ostream_iterator<string> os(cout, " ");

以上即是将os定义为一个绑至标准输出设备的ostream_iterator。第二个参数是分隔符字符串常量。

可以这样使用:

copy(text.begin(), text.end(), os);

copy()会将储存在text中的每个元素一一写到由os所表示的ostream上。每个元素以空格分隔。

以下是完整代码:

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int main() {
	istream_iterator<string> is(cin);
	istream_iterator<string> eof;
	vector<string> text;
	copy(is, eof, back_inserter(text);
	sort(text.begin(), text.end());
	ostream_iterator<string> os(cout, " ");
	copy(text.begin(), text.end(), os);
}

如果是文件读写,只需将istream_iterator绑定至ifstream object,将ostream_iterator绑定至ofstream object即可:

#include <iostream>
#include <fstream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int main() {
	ifstream in_file("input_file.txt");
	ofstream out_file("output_file.txt");
	if (!in_file || !out_file) {
		cerr << "!! unable to open the necessary files.\n";
		return -1;
	}
	istream_iterator<string> is(in_file);
	istream_iterator<string> eof;
	vector<string> text;
	copy(is, eof, back_inserter(text));
	sort(text.begin(), text.end());
	ostream_iterator<string> os(out_file, " ");
	copy(text.begin(), text.end(), os);
}

相关文章