牵着老婆满街逛

严以律己,宽以待人. 三思而后行.
GMail/GTalk: yanglinbo#google.com;
MSN/Email: tx7do#yahoo.com.cn;
QQ: 3 0 3 3 9 6 9 2 0 .

求STL容器的两个iterator的距离

什么是Iterator?
        iterator的概念源自于对遍历一个线性容器工具的抽象,即如何你能访问这个容器的某个元素。对于最简单的数组,当然可以用数组的索引值,因为数组是连续存放在内存中的;但对于链表,就必须用指针。除此之外,还有还有很多种数据结构需要提供一个方便的工具来访问其中的元素,方法有ID,关键字等等。为了统一所有的容器的这种工具的使用,一般提供一整套容器的开发者就会用一种方式来表示各种容器的访问工具。例如C++   STL就是使用iterator。MFC自己的容器使用position。C#和java也有自己的方法,但方法是不变的。   
        iterator的用法可以被统一,但不同的底层容器实现其iterator的原理是不一样的。例如iterator++你可以理解为移动到容器的下一个元素,如果底层如果是数组,把索引值加一就行;如果底层是链表,就得执行类似于m_pCurrent   =   m_pCurrent->pNext;的操作。因此每种容器都有自己的iterator实现方法。

Iterator的类型
1、Input Interator :只允许作为输入,也就是只读(Read Only)
2、Output Interator :只允许作为输出,也就是只写(Write Only)
3、Forward Interator :允许读写,但只能做前向移动
4、Bidirectional Interator :允许读写,可以做双向移动
5、Random Access Interator :允许读写,可以任意移动


实现Distance()
        由上可知,从容器特性来划分是具有两种iterator的,一种是线性容器的iterator(数组,vector等);一种是非线性容器的iterator(链表等),因此求两个容器的距离自然也是有两种方法的。

非线性容器:
int distance(InputIterator p1, InputIterator p2)
{
  size_t n 
= 0;
  
while ( p1 != p2 )
  
{
     
++p1;
     
++n;   
  }

  
return n;
}
 


线性容器:
int distance(RandomAccessIterator p1, RandomAccessIterator p2)
{
 
return p2-p1;
}
 


std::distance()实现了以上两种Iterator的算法,并根据传入的Iterator类型进行适配。
具体可以参考侯捷翻译的《STL源码剖析》一书,当中有详细的讲解。

posted on 2009-01-08 19:17 杨粼波 阅读(1170) 评论(3)  编辑 收藏 引用

评论

# re: 求STL容器的两个iterator的距离[未登录] 2009-01-25 10:31 Felicia

有问题吧……
非线性容器才需要用循环一个一个加的,比如map  回复  更多评论   

# re: 求STL容器的两个iterator的距离 2009-01-26 12:34 杨粼波

非常抱歉,笔误了....
也就是vector和数组是线形的,
STL里面,map是基于list实现的,都是非线形的.  回复  更多评论   

# re: 求STL容器的两个iterator的距离 2009-07-28 09:19 要输姓名?

vc6 中自带的 STL 中 map 是用 红黑树实现的,vc2003(好像)之后的版本使用哈希树,gcc libstd++ 不太清楚,反正不可能是线性表结构。

线性表结构搜索一个元素复杂度为 O(N)。不适合搜索。
AVL-树搜索一个元素复杂度为 O(log2 N)。

map 查找元素速度还是很快的。  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理