slist属于单链表,不在标准规格之内,是SGI STL特有的一种顺序容器。由于slist的迭代器属于前向迭代器,不能往前走,所以插入操作和list有所不同。根据STL的习惯,插入操作会将新元素插入于指定位置之前,但slist无法记录前驱节点(需要从头遍历找出前驱节点),所以插入操作提供了insert_after()和erase_after()版本。
slist节点和迭代器的设计比list要复杂许多,它运用了继承关系:
- __slist_node_base作为节点基本结构,派生出__slist_node
- __slist_iterator_base作为迭代器基本结构,派生出__slist_iterator
__slist_iterator_base类中的有一个指向__slist_node_base节点的指针,名叫node,以此来关联迭代器和节点。slist将__slist_iterator作为它的迭代器。至于为什么要搞这么复杂,还没有弄清楚,源码剖析中说是为了更大的弹性。
参考:
《STL源码剖析》 P186.
- 前言
- 顺序容器 — heap
- 关联容器 — 红黑树
- 关联容器 — set
- 关联容器 — map
- 关联容器 — hashtable
- 关联容器 — hash_set
- 关联容器 — hash_map
- 算法 — copy
- 顺序容器 — stack
- 顺序容器 — queue
- 顺序容器 — priority_queue
- 顺序容器 — slist
- construct()和destroy()
- 空间配置器
- 函数适配器
- 迭代器以及“特性萃取机”iterator_traits
- 算法 — partial_sort
- 算法 — sort
- 仿函数
- 适配器(adapters)
- C++简易vector
- C++简易list
- STL算法实现
- C++模板Queue