C++ STL 容器中的迭代器类型

迭代器的类型大体上分成下面几类：

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重复