STL序列式容器之slist
slist概述
STL list是个双向链表（double linked list）。SGI STL另提供了一个单向链表（single linked list），名为slist。
slist和list的主要差别在于，前者的迭代器属于单向的ForwardIterator，后者的迭代器属于双向的BidrectionalIterator。为此，slist的功能自然也就受到许多限制。不过，单向链表所耗用的空间更小，某些操作更快，不失为另一种选择。
slist和list共同具有的相同特色是，他们的插入（insert），移除（erase），结合（splice）等操作并不会造成原有的迭代器失效。
注意，根据STL的习惯，插入操作会将新元素插入指定位置之前，而非之后，然后作为一个单向链表，slist没有办法可以直接回头定出前一个位置。因此它必须从头找起。换句话说，除了slist起点处附近的区域外，在其他位置上采用insert和erase操作函数，将花费线性时间，对迭代器进行遍历，而后才能完成操作，事件性能损耗较大。这便是slist相较于list下的大缺点。为此，slist提供了insert_after()和erase_after()供灵活运用。
基于同样的（时间效率）考虑，slist不提供push_back(),只提供push_front(),因此slist的元素次序和元素插入进来的次序相反。
slist的节点
slist节点和其迭代器的设计，架构上比list复杂许多，运用了继承关系，因此在型别上有复杂的表现。下图概述了slist节点和其迭代器的设计。
代码如下
struct __slist_node_base
{
__slist_node_base *next;
};
template <class T>
struct __slist_node : public __slist_node_base {
T data;
};
inline __slist_node_base* __list_make_link(
__slist_node_base* prev_node,
__slist_node_base* new_node)
) {
new_node->next = prev_node->next;
prev_node->next = new_node;
return new_node;
}
inline size_t __slist_size(__slist_node_base* node) {
size_t result = 0;
for(;node !=0; node = node->next)
result ++;
return result;
}slist的迭代器
slist的迭代器可以以下图表示
实际构造代码如下：
struct __slit_iterator_base
{
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef forward_iterator_tag iterator_category; // 单向
__slist_node_base * node;
__slist_iterator_base(__slist_node_base*x): node(x) {}
void incr() {node = node->next;}
bool operator==(const __slist_iterator_base& x) const {
return node == x.node;
}
bool operator != (const __slist_iterator_base&x) const {
return node != x.node;
}
};
template <class T, class Ref, class Ptr>
struct __slist_iterator: public __Slist_iterator_base
{
typedef __slist_iterator<T, T&, T*> iterator;
typedef __slist_iterator<T, const T&, const T*> const_iterator;
typedef __slist_iterator<T, Ref, Ptr> self;
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef __slist_node<T> list_node;
__slist_iterator(list_node*x) : __slist_iterator_base(x) {}
__slist_iterator() : __slist_iterator_base(0) {}
__slist_iterator(const iterator&x): __slist_iterator_base(x.node) {}
reference operator*() const {return ((list_node*)node)->data;}
pointer operator->() const {return &(operator*());}
self& operator++() {
incr();
return *this;
}
self operator++(int) {
self tmp = *this;
incr();
return tmp;
}
};slist的数据结构
下面是slist的源码摘要，我们把重点放在“单向列表之形成”的一些关键点上。
template<class T, class Alloc = alloc>
class slist
{
public:
typedef T value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type& reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef __slist_iterator<T, T&, T*> iterator;
typedef __slist_iterator<T, const T&, const T*>const_iterator;
private:
typedef __slist_node<T> list_node;
typedef __slist_node_base list_node_base;
typedef __slist_iterator_base iterator_base;
typedef simple_alloc<list_node, Alloc> list_node_allocator;
static list_node* create_node(const value&x) {
list_node *node = list_node_allocator::allocate();
__STL_TRY {
construct(&node->data, x);
node->next = 0;
}
__STL_UNWIND(list_node_allocator::deallocate(node));
return node;
}
private:
list_node_base head;
public :
slist() {head.next = 0;}
~slist() {clear();}
iterator begin() { return iterator((list_node*)head.next); }
iterator end() { return iterator(0); }
size_type size() const { return __slist_size(head.next); }
bool empty() const { return head.next == 0; }
void swap(slist& L) {
list_node_base* tmp = head.next;
head.next = L.head.next;
L.head.next = tmp;
}
public:
reference front() { return ((list_node*)head.next)->data;}
push_front(const value&x) {
__slist_make_link(&head, create_node(x));
}
void pop_front() {
list_node* node = (list_node*)head.next;
head.next = node.next;
destroy_node(node);
}
...
}从以上的定义可以，slist的结构几乎和单向链表是差别不大的；只是当中用到了Iterator_base,及node_base作为基类；而后将数据存放在node中，Iterator中定义一些与data相关取值及迭代器前进的运算符。
参考文档《STL源码剖析--侯捷》
原文地址：https://blog.csdn.net/chnming1987/article/details/143829177
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！