数据结构利器之私房STL（上）

数据结构利器之私房STL（下）

索引

这篇文章 http://www.cnblogs.com/daoluanxiaozi/archive/2012/12/02/confidential-stl.html 由于严重违反了『博客园首页』的相关规则，因此笔者改将《私房STL》系列的每一篇都整合到博客园中，取消外链的做法。另，考虑篇幅的问题，此系列文章将分为上、中、下。此篇为《数据结构利器之私房STL（下）》，最后一篇。喜欢就顶下:-)

此系列的文章适合初学有意剖析STL和欲复习STL的同学们。

私房STL之左值和右值
私房STL之函数对象
私房STL之函数配接器
私房STL之迭代器

私房STL之左值和右值

左值和右值并不专属于STL里的内容，是在接触STL的过程发现了笔者C/C++的知识规则漏洞。

左值右值

左值（LValue）即等号左边的值，右值（RValue）即等号右边的值，右值必须放在等号右边，但左值既可以在左边也可以放在右边。那么数值（等式），字符串，常量，只能作为右值，右值决不能放置等号左边。

变量，引用（reference）作为左值，既可以在等式左边，又可以在等式右边。
函数对象的使用
函数对象直接应用的地方较少，但了为了配合接下来配接器（下一篇博文）的内容，简单测试下：
展示一段代码：
这里不单独描述迭代器，它个单不是一独的个体，放在其所属的大框架中，更能体现它的作用和执行机制。
STL中会定义迭代器：
iterator_op
从中看出，迭代器不包含数据实体，它只是能表现和操作数据实体。因为上述container_iterator操控的的实现，因此当手头有一container_iterator的时候，你可以“*ite”来获得数据元的引用，可以“ite->”获得数据元的指针，“++”可以另ite自动前进一步，“--”可以另ite后退一步。。。
通过模板，迭代器可以为任何数据元服务。一个有趣的地方便是迭代器的构造函数：
container_iterator(link_type x):node(x){}
在container（以下展示）的元素操作当中，很多时候会直截返回指向数据元的指针，这时可能此操作的函数可能需要返回的是container_iterator类型，而不是返回一个指向数据元的指针（这种做法不上道，太龌龊），于是会临时构造（调用迭代器的构造函数）一个迭代器作为返回值。
意即：
class Node  {  public:  Node(int nAge = 0)  {  m_nAge = nAge;  }  ......private:  int m_nAge;  };  Node foo(int i){return i;/*直截返回一个int，但Node有Node(int)构造函数，因此会临时构造一个Node对象返回。*/}int main(){Node i = foo(2);return 0;}
下面是container：
template <class _Ty,class alloc>/*T：节点元素类型。*/class container{/*container数据结构*/typedef container_iterator<_Ty> iterator;typedef const container_iterator<_Ty> const_iterator;typedef Node<_Ty>* link_type;typedef _Ty value_type;typedef Node<_Ty>* link_type;typedef size_t size_type;typedef ptrdiff_t difference_type;private:link_type head;/*头指针。*/link_type tail;/*为指针。*/iterator begin();iterator end();bool empty();size_type size()const ;....../*元素的操作。push_front,push_back,pop_front,pop_back,insert,earse等根据容器的不同各取所需。*/iterator insert(const _Ty& x);iterator earse(iterator position);void push_back(const _Ty& x);void push_front(const _Ty& x);void pop_back();void pop_front();......};
container内部实现的大多数是元素的操作函数，它们有充分利用container_iterator，包括container_iterator内部实现的各种元素的操控（++，--，*，->等等）。
container和container_iterator就是这样结合起来的。还剩下一STL中的镇库之宝：算法。通用的的算法中，少不了迭代器。如何能做到通用？不同的容器对应不同的迭代器，那是否对于一个算法，要实现多个迭代器的版本？不，不需要，这就是泛化编程的好处，根据传入的迭代器（一般的STL算法会以迭代器作为参数）来推导出相应的迭代器类型。以最为简单的find()算法为例：会通过_InIt _First来推导出迭代器的类型，推导出迭代器的类型，也就推导出了相应的容器。
/*摘自c++ standard library。*/template<class _InIt, class _Ty>inline_InIt find(_InIt _First, _InIt _Last, const _Ty& _Val){// find first matching _Val_ASSIGN_FROM_BASE(_First,_Find(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Val));return (_First);}template<class _InIt, class _Ty>inline_InIt _Find(_InIt _First, _InIt _Last, const _Ty& _Val){// find first matching _Val_DEBUG_RANGE(_First, _Last);for (; _First != _Last; ++_First)if (*_First == _Val)break;return (_First);}
我们看到，迭代器在算法中的表现，++，--，==。。。。
故迭代器和算法模块结合了。STL中迭代器，容器，算法三足鼎立，整体上通力合作，细微之处不乏各司其职。妙哉！妙哉！
本文完 2012-10-28
捣乱小子 http://www.daoluan.net/