泛型算法

泛型算法

1
2
#include <algorithm>//存放泛型算法
#include <numric> //存放算术算法

因为它们实现共同的操作,所以称之为 算法 因为它们可以操作在多种容器类型中–不但可以作用在vectorlist这些标准库类型上

还可以同在内置数组上,甚至其他类型的序列上

首先得清楚三种容器的区别 list vector deque

三种容器均支持resieze()操作,重新划定容器大小,且此函数有重载。

vector

vectorbuilt-in数组类似,是一个在堆上建立的一维数组,它拥有一段连续的内存空间,并且起始地址不变,因此 它能非常好的支持随即存取,即[]操作符。

vector因为存储在堆上,所以支持erase( ), resieze()(重新划分容器容量)等操作;

vector不用担心越界当空间不够用的时候,系统会自动按照一定的比例(对capacity( )大小)进行扩充。

vector序列末尾添加(push_back( ))或者删除(pop_back( ))对象效率高,在中间进行插入或删除效率很低,主要是要进行元素的移动和内存的拷贝,原因就在于当内存不够用的时候要执行重新分配内存,拷贝对象到新存储区,销毁old对象,释放内存等操 作,如果对象很多的话,这种操作代价是相当高的。

为了减少这种代价,使用vector最理想的情况就是事先知道所要装入的对象数目,用成员函式 reserve( )预定下来

vector最大的优点莫过于是检索(用operator[ ])速度在这三个容器中是最快的

list

list的本质是一个双向链表(根据sgi stl源代码),内存空间不连续, 通过指针进行操作。说道链表,它的高效率首先表现是插入,删除元素, 进行排序等等需要移动大量元素的操作。显然链表没有检索操作operator[ ], 也就是说不能对链表进行随机访问,而只能从头至尾地遍历,这是它的一个缺陷。

list有不同于前两者的某些成员方法,如合并list的方法splice( ), 排序sort( ),交换list 的方法swap( )等等。

deque

deque是一个double-ended queue是由多个连续内存块构成, dequelistvector的兼容,分为多个块,每一个块大小是512字节, 块通过map块管理,map块里保存每个块得首地址。因此该容器也有索引操作operator[ ],效率没vector高。

下面是选择顺序容器类型的一些准则

  1. 如果我们需要随机访问一个容器则vector要比list好得多 。
  2. 如果我们已知要存储元素的个数则vector 又是一个比list好的选择。
  3. 如果我们需要的不只是在容器两端插入和删除元素则list显然要比vector
  4. 除非我们需要在容器首部插入和删除元素否则vector要比deque好。
  5. 如果只在容易的首部和尾部插入数据元素,则选择deque.
  6. 如果只需要在读取输入时在容器的中间位置插入元素,然后需要随机访问元素,则可考虑输入时将元素读入到一个List容器,接着对此容器重新拍学,使其适合顺序访问,然后将排序后的list容器复制到一个vector容器中

算法在容器中的应用

1
find(beg , end , search_value);//返回值为所查找元素的迭代器 , 如果没有找到,find返回其第二个迭代器实参

范例:

1
2
3
4
5
6
//假设一个list容器中存放若干整数,该容器对象名为lst
cin>>search_value
list<int>::iterator iter =
find(lst.begin() , lst.end() ,search_value );
//可以使用*iter 来引用到所要搜索的值
如果没有找到,find返回其第二个迭代器实参

同样,该查找函数可用于内置数组

算法的工作方式

以find为例:

  1. 顺序检查每个元素
  2. 如果当前的元素等于所要查找的值,那么返回指向该元素的迭代器、
  3. 否则查找下一个元素,重复 2 ,直到找到这个数为止 , 或者检查完所有的元素
  4. 如果到达集合的末尾, 而且还未找到该值, 则返回某个值,指明要查找的值不存在

算法要求:

  1. 需要某种遍历集合的方式,能够从一个元素迁移到下一个元素
  2. 必须能够知道是否到达文件尾
  3. 必须能够对容器中的每一个元素与被查找的元素相比较
  4. 需要一个类型;来指出元素在容器中的位置,或者表示找不到该元素

特别的,对于第3个要求有两种解决方案:

  1. 默认情况下:find操作要求元素类型定义了相等(==)操作符
  2. 如果元素不支持这一运算符、或者打算用其他不同的测试方法来比较元素 则使用 find_if(beg , end , pred , search_value);

只读算法

1
2
3
4
5
find()
accumulate(beg , end , value) //#include <numric>
int sum = accumulate(vec.begin() , vec.end() , 42);
//第三个形参是累加初值,该算法返回的累加结果,其返回类型就是其第三个实参的类型
说明:accumulate对要累加的元素类型一无所知
  1. 调用该函数时必须传递一个起始值,否则,accumulate将不知道使用什么初始值
  2. 容器内的元素必须与第三个实参的类型相互匹配,或者可以转换为第三个类型参数
1
2
find_first_of(beg , end , beg1 , end1 )//该函数在第一段范围内查找与第二段范围中任意元素匹配的元素,然后返回一个迭代器,指向第一个范围内相匹配的元素的迭代器
//如果没有相匹配的元素,则返回end

使用范例:

假设roster1roster2是两个存放名字的list对象,可使用该函数统计有多少个名字同时出现在两个列表中

1
2
3
4
5
6
7
size_t cnt = 0 ; //计数
list<int>::iterator it = roster1.begin();
while((it = find_first_of(it , roster1.end() , roster1.begin() , roster2.end())) != roster1.end())
{
cnt++;
++it;
}

find_first_of()函数要求每对迭代器之间精确匹配,但不要求两队之间类型匹配

写容器元素算法

  1. 直接将数据写入输入序列
  2. 带有额外的迭代器参数指定写入目标
  3. 指定数目的元素写入某个序列

1———-

1
2
fill(beg , end , 0);//将0 写入输入序列中
fill_n(beg , count , value) ; 迭代器,计数器,参数

注意:
这个函数不对写入范围进行检查,假定对指定数量的元素做写操作是安全的

错误示例:

1
2
vector<int> ivec
fill_n(ivec.begin() , 10 , 0);//error!

插入迭代器

1
#include <iterator>

back_inserter函数是迭代器适配器与容器适配器一样 , 迭代器适配器使用一个对象作为实参,并生成一个适应其实参行为的新对象 该函数运算通过容器自带的push_back() 来添加元素

范例:

1
2
vector<int> ivec;
fill_n(back_inserter(ivec , 10 , 0));

2———–

写入目标迭代器的算法

1
copy(beg , end , dest);//前两个元素表明输入范围 , 第三个元素则指向目标序列的一个元素

范例:

1
2
vector<int> vec;
copy(lst.begin() , lst.end() , back_inserter(vec));

算法的 _copy 版本 ## 这些版本的算法对输入序列的元素做出处理,但不修改原来的元素,而是创建一个新序列存储元素的 处理结果:

1
2
replace(beg , end , old_value , new_value);
replace_copy(beg , end , dest , old_value , new_value);

对元素重新排序的算法

1
2
sort(beg , end)//对指定元素序列进行排序
unique(beg , end);//该算法的使用必须建立在上一个函数的使用基础之上,该算法删除相邻的重复元素,然后重新排列输入范围内的元素,并返回一个迭代器,表示无重复的值范围的结束

注解:
注意使用过该函数的序列大小并没有发生变化,依然保存着,只是这些元素的顺序发生改变了

unique其实就是讲无重复的序列复制到序列的最前端,从而覆盖相邻的重复元素。其返回值为迭代器指向超出无重复的元素范围末端的下一个位置

谓词函数

谓词函数做某些检测的函数,返回用于条件判断的类型,指出条件是否成立

使用范例:

1
2
3
4
5
6
7
8
9
bool isShorter(const string& s1 , const string& s2)
{
return s1.size() <s2.size();
}
bool GT6(const string&s)
{
return s.size() >6;
}

1
2
3
4
5
6
stable_sort(beg , end);
stable_sort(beg , end , pred);//第三个参数为谓词函数的函数名
使用范例:
stable_sort(lst.begin() , lst.end() , isShorter);
//该函数要求其谓词函数必须有两个实参,实参的类型必须与元素类型相同,并返回一个可用作条件检测的值

1
count_if(beg , end , pred);

范例:

1
2
list<int>::size_type cnt = count_if(lst.begin() , lst.end() , GT6);
//将满足GT6这个函数的值计数

再谈迭代器

  1. 插入迭代器
  2. iosream迭代器
  3. 反向迭代器

1.———-

  1. back_inserter 创建使用push_back() 实现插入迭代器
  2. front_inserter创建是用push_front() 实现插入
  3. inserter使用insert实现插入操作。除了所关联的容器,还有第二个实参,指向插入起始位置的迭代器

inserter使用

1
2
3
vector<int> ivec
vector<int>::iterator it = find(ivec.begin() , ivec.end() , 42);
replace(lst.begin() , lst.end() , inserter(ivec , it) , 100 , 0)

区分三者:

1
2
3
4
5
6
list<int> ilst , ilst2 , ilst3;
for(list<int>::size_type i = 0 ; i != 4 ; ++i)
ilst.push_front();//3 2 1 0
copy(ilst.begin() , ilst.end() , front_inserter(ilst2));// 0 1 2 3
copy(ilst2.begin() , ilst2.end() , inserter(ilst3 , ilst2.begin())) // 3 2 1 0

切记:容器vector不可以使用front_inserterinserter 这两者迭代器

2.————–

iostream迭代器

1
2
3
4
5
6
===============iostream迭代器的构造函数===========
istream_iterator<T> in(strm) 创建从输入流strm中读取T类型的对象的istream_iterator对象
istream_iterator<T> in; istream_iterator 对象的超出末端迭代器
ostream_iterator<T> in(strm)
ostream_iterator<T> in(strm , delim) 创建XX对象,在写入的过程中使用delim作为元素的分隔符,delim是以空字符结束的字符数组
=================================================================================================================

流迭代器只定义了最基本的操作:自增,解引用和赋值

此外,两个istream迭代器是否相等,而ostream不提供比较运算

范例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
istream_iterator<int> cin_it(cin);
istream_iterator<int> end_of_stream;
ofstream outfile;
ostream_iterator<Sale_items> output(outfile , " ");
-----------------
istream_iterator上的操作
istream_iterator<int> in_it(cin);
istream_iterator<int> eof;
while(in_it != eof)
{
vec.push_back(*in_it++);
}
还可以简化:
vector<int> vec(in_it , eof);

ostream_iterator对象和ostream_iterator的使用

1
2
3
4
5
6
ostream_iterator<string> out_iter(cout , "\n");
istream_iterator<string> in_iter(cin) , eof;
while(in_iter != eof)
{
*out_iter+ = *in_iter++;
}

在类类型上使用istream_iterator

1
2
3
4
5
6
7
8
9
10
istream_iterator<Sale_items> item_iter(cin) , eof;
Sale_items sum;
sum = *item_iter++;
while(item_iter != eof)
{
if(item_iter->same_isbn(sum))
{}
else
{}
}

3.————-

反向迭代器

1
2
3
4
5
for(vector<int>::reverse_iterator iter = vec.rbegin();
iter != vec.rend() ; ++iter)
{
cout<<*iter<<" ";
}

反向迭代器的base()成员是转化为正序时向后移动一位

假设vector<string>::reverse_iterator rcomma指向序列中的一个元素那么[ivec.rbegin , rcomma)构成了一个左闭合区间,当转换为正序时则应该为:[rcomma.base() , ivec.end()) 而此时rcommarcomma.base()不是指向同一个元素,rcomma.base() 指向rcomma的后一个元素

1
2
3
4
5
6
7
8
=迭代器种类======================支持的操作==========
输入迭代器 == != -- * ->
输出迭代器 ++ *
前向迭代器 == != ++ * ->
双向迭代器 == != ++ * -> --
随机访问迭代器 == != ++ * -> -- < <= > >= + +=
-= - []
======================================================
  • map set list类型提供的是双向迭代器
  • string vector deque容器上定义的是随机访问迭代器,还有内置数组
  • istream_iterator 输入迭代器
  • ostrea,_iterator 输出迭代器

注意:尽管mapset类型提供双向迭代器,但关联容器只能使用算法的一个子集
问题在于,关联容器的键时const对象。因此,关联容器不能使用任何写序列元素的算法在处理算法时, 最好将关联容器上的迭代器视为支持自减运算的输入迭代器

泛型算法的结构

算法的形参模式

1
2
3
4
5
alg(beg , end , other parms);
alg(beg , end , dest , other parms);
alg(beg , end , beg2 , other parms);
alg(beg , end , beg2 , end2 , other parms);
//dest为目标迭代器

带单个目标迭代器的算法

注意:

调用这些算法时,必须确保输出的容器具有足够大的容量来存储输出数据,这正是通常要使用插入迭代器或者ostream_iterator来调用这些算法的原因。

带第二个输入序列的算法

算法的命名规范

  1. 包括测试输入范围内元素的算法
  2. 应用于对输入范围内元素重新排序的算法

区别带一个值或一个谓词函数参数的算术版本:

很多算法通过检查其输入范围内的元素实现其功能, 这些算法通常要用到标准关系操作符:==<.
其中大部分算法会超过第二个版本的函数,允许程序员提供比较火测试函数取代操作符的使用
例:

排序要使用 < 操作符

1
2
sort(beg , end);
sort(beg ,end , comp);//use function named comp to sort the elem

检查指定值的算法默认使用==操作符 , 系统为这类函数提供了另外命名的版本,带谓词函数形参。带有谓词函数形参的算法,其名字后带后缀 _if

1
2
find(beg , end , val);
find_if(beg , end , pred);//find first instance for which pred is true'

区别是否实现复制的算法版本

_copy 实现复制版本

1
2
reverse(beg , end);
reverse(beg , end ,dest);//将元素反向冲洗排序

list容器的特有操作

1
2
lst.merge(lst2)
lst.merge(lst2 , comp)

lst2中的元素合并到lst中。这两个list容器必须重新排序,lst2中的元素将被删除,合并后,lst2为空。返回void类型第一个版本使用<操作符第二个版本则使用comp指定的比较运算

1
2
lst.remove(val)
lst.remove_if(unaryPred)

调用lst.erase删除所有等于指定值或使指定的谓词函数返回非零值的元素。返回值为void类型

1
2
3
4
lst.sort
lst.splice(iter , lst2)
lst.splice(iter , lst2 , iter2)
lst.splice(iter , beg , end)

lst2的元素移动到lst中迭代器iter指向的元素前面。在lst2中删除移出的元素
第二个版本只移动iter2所指向的元素,这个元素必须是lst2中的元素。这种情况下,lstlst2 可以是同一个list对象,也就是说,可以在一个list对象中使用使用splice运算移动一个元素

1
2
lst.unique()
lst.unique(binaryPred)

调用erase()删除同一个值的连续副本。第一个版本使用==操作符判断元素是否相等
第二个版本则使用指定的谓词函数实现判断

1
lsr.reverse();

以上是list容器的特有算法,可以真正做到修改其关联的基础容器,真正删除指定元素

1
set_intersection(beg , end , beg1, end1 , dest);//将两个迭代器表示的范围中相同的元素提取并放在以dest迭代器为目标的容器中

热评文章