当前位置：首页 > article >正文

STL序列式容器之slist

article 2024/11/23 3:35:01

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源码剖析--侯捷》

查看全文

http://www.kler.cn/a/403235.html