C++编程失乐园

致力于解决论坛的不足,探讨C++的原理

C++随笔 之 C++标准库5(原创)--STL

STL 是个部件库 (component library) ,其中的部件包括有容器 (container ,储存任意类型对象的对象 ) 和算法。只要用户对自己定义的部件做点小小的要求, STL 中的算法就可以工作在用户自定义的容器上,或者 STL 中的容器可以使用用户自定义的算法。
我们可以把软件部件想象成一个三位空间。第一维表示数据类型(int, double, char, …),第二维表示容器(array, linked-list, …)

第三维表示算法
(sort, merge, search, …)

STL 包含 5 个主要的部分,
·算法 (Algorithm) :能运行在不同容器 (container) 上的计算过程

·容器 (Container) :能够保留并管理对象的对象

·迭代器 (Iterator) :算法存取容器 (algorithm-access to containers) 的抽象,以便算法可以应用在不同的容器上

·函数对象 (Function Object) :定义了函数调用操作符 (operator()) 的类

·适应器 (Adaptor) :封装一个部件以提供另外的接口 ( 例如用 list 实现 stack)


正是因为有了Iterator,算法才和容器分开了.

容器
(Container) 是能够保存其他类型的对象的类。容器形成了 STL 的关键部件。当书写任何类型软件的时候,把特定类型的元素集聚起来都是很至关重要的任务。

       STL 中有顺序容器 (Sequence Container) 和关联容器 (Associative Container)

STL 中支持的容器总结如下:

顺序容器 (Sequence Container)

向量 (Vector)

 

双向队列 (Deque)

 

线性表 (List)

关联容器 (Associative Container)

集合 (Set)

 

多集合 (MultiSet)

 

映射 (Map)

 

多映射 (MultiSet)


迭代器
(Iterator) 是指针 (pointer) 的泛化,它允许程序员以相同的方式处理不同的数据结构 ( 容器 ) STL 中有 5
中类型的迭代器,它们分别满足一定的要求。不同的迭代器要求定义的操作不一样。
输入和输出迭代器
向前迭代器
双向迭代器
任意存取迭代器

算法

STL 库中的算法都以迭代器类型为参数,这就和数据结果的具体实现分离开了。基于此,这些算法被称作基本算法 (generic algorithm)
如“寻找(Find)”、“邻居寻找(Adjacent find)”、“计数(Count)”、“不匹配(Mismatch)”、“相等(Equal)”、“搜索(Search)
拷贝(Copy)”、“交换(Swap)”、“变换(Transform)”、“替换(Replace)、“填充(Fill)、“产生(Generate)、“迁移(Remove)、“唯一(Unique)、“翻转(Reverse)、“旋转(Rotate)、“任意洗牌(Random shuffle)、“分区(Partitions)

适应器
(Adaptor) 是提供接口映射的模板类 (Adaptors are template classes that provide interface mappings)
。适应器基于其他类来实现新的功能,成员函数可以被添加、隐藏,也可合并以得到新的功能。

(Stack)

       栈可以用向量 (vector) 、线性表 (list) 或双向队列 (deque) 来实现:

stack<vector<int>>       s1;

stack<list<int>       >     s2;

stack<deque<int>>s3;

队列 (Queue)

       队列可以用线性表 (list) 或双向队列 (deque) 来实现 ( 注意 vector container 不能用来实现 queue
因为
vector 没有成员函数 pop_front! )

queue<list<int>>    q1;

queue<deque<int>>       q2;

优先级队列 (Priority Queue)

       优先级队列可以用向量 (vector) 或双向队列 (deque) 来实现 ( 注意 list container 不能用来实现 queue
因为
list 的迭代器不是任意存取 iterator ,而 pop 中用到堆排序时是要求 random access iterator ! )

priority_queue<vector<int>, less<int>>        pq1;        // 使用递增 less<int> 函数对象排序

priority_queue<deque<int>, greater<int>>    pq2;       // 使用递减 greater<int> 函数对象排序

迭代适应器

逆向迭代器 (Reverse Iterator)

       顾名思义,逆向迭代器的递增是朝反方向前进的。对于顺序容器 (vector, list deque) ,其成员函数 rbegin() rend() 都返回了相应的逆向迭代器:

list<int> l;

for (int i = 1; i < 5; i++)

       l.push_back(i);

copy(l.rbegin(), l.rend(), ostream_iterator<int> (cout, “ “));

输出结果是: 4 3 2 1

 

插入迭代器 (Insert Iterator)

       插入迭代器简化了向容器中插入元素的工作。插入迭代器指定了向容器中插入元素的位置。 STL 中有三种插入迭代器:

·向后插入 (back_insert_iterator) ,在容器尾部插入

·向前插入 (front_insert_iterator) ,在容器头部插入

·插入 (insert_iterator) ,在容器中任一位置

STL 中提供了三个函数分别构造相应的插入迭代器:

· back_inserter

· front_inserter

· inserter

 

原始存储迭代器 (Raw Storage Iterator)

       该迭代器允许算法将其结果保存进没有初始化的内存中。

函数适应器

否认者 (Negator)

       有两个否认者 not1 not2 分别是一元和二元函数,它们分别使用一元和二元的谓词 (Predicate) ,返回的是谓词的结果的取反。

 

包扎者 (Binder)

       STL 中有两个包扎者函数 bind1st bind2nd ,可以将一些值限定在指定区间中。

 

函数指针的适应器 (Adaptors for pointers to function)

       STL 中的算法和容器一般都需要函数对象 (function object) 作为参数。如果想用到常用的 C++ 函数时,可以用 ptr_fun 把普通函数转换成函数对象。比如 ptr_fun(strcmp) 就把常用的串比较函数 strcmp 包装成一个函数对象,就可用在 STL 算法和容器中了。

posted on 2007-01-04 10:48 木木头 阅读(1506) 评论(2)  编辑 收藏 引用 所属分类: C++特性

评论

# re: C++随笔 之 C++标准库5(原创)--STL 2007-01-04 13:01 pengkuny

看来STL功能很强大,我得好好学一下  回复  更多评论   

# re: C++随笔 之 C++标准库5(原创)--STL 2007-10-11 21:24 ptrrrrr

文中的Stack,Queue和priority_queue举的例子,全都少了一个参数,而且书写有点问题

比如stack<vector<int>> s1;

应该是stack<int, vector<int> > s1;  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2007年10月>
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910

统计

常用链接

留言簿(3)

随笔分类(29)

搜索

最新随笔

最新评论