迭代器的类型大体上分成下面几类:
1、Input Iterator
2、Output Iterator
3、Forward Iterator 单向迭代器
4、Bidirectional Iterator 双向迭代器
5、Random Access Iterator 随机迭代器
并且他们满足继承关系:Input Iterator <- Forward Iterator <- Bidirectional Iterator <- Random Access Iterator
容器中的迭代器类型
-
序列式容器(sequence)
1、vector: 双向迭代器 Random Access Iterator
2、list: 双向迭代器 Bidirectional Iterator
3、deque: 随机迭代器 Random Access Iterator(但是与vector的指针有所不同,并不是普通的指针)
4、stack:默认以deque作为底层容器(也可以采用list作为底层容器,stack<int, list >),所以应该叫做adapter配接器,stack没有迭代器
5、queue: 默认以deque作为底层容器(也可以采用list作为底层容器,queue<int, list >),所以应该叫做adapter配接器,queue没有迭代器
6、priority_queue: 默认以vector作为底层容器,以binary max heap 作为底层处理机制,所以应该叫做adapter配接器,因为heap的所有元素都必须遵循特别的(complete binary tree)排列规
则,所以priority_queue 不提供遍历功能,也不提供迭代器
7、slist:单向链表,单向迭代器 Forward Iterator 并且是双层迭代器结构(与双层节点结构对应)
-
关联式容器(associative)
1、RB-tree(非公开):双向迭代器 Bidirectional Iterator,并且是双层迭代器结构(与双层节点结构对应)
2、set:以RB-tree作为底层机制,并且set::iterator被定义为RB-tree的const_iterator,杜绝写入操作(即不能通过set的迭代器改变set的元素值)
3、map:以RB-tree作为底层机制,而与set不同的是,map iterators既不是一种constant iterators,也不是一种mutable iterators。原因在于:map虽然不能修改key值,但是可以修改value值
4、multiset:与set完全相同,唯一的差别在于它允许key重复(插入操作调用的是insert_equal()而不是insert_unique())
5、multimap:参考mutiset对于set,同理
6、hashtable: hashtable的迭代器维系着整个"buckets vector",记录目前所指的节点,尝试从目前节点出发,通过next指针实现前进操作,没有后退操作(operator--()),没有所谓的逆向迭代
器,所以是Forward Iterator
7、hash_set:以hashtable作为底层结构
8、hash_map:以hashtable作为底层结构
9、hash_multiset:以hashtable作为底层结构,允许key重复
10、hash_multimap:以hashtable作为底层结构,允许key重复