STL数据结构之List

• 1: List节点结构
• • List迭代器
  • • 三级目录

1: List节点结构

list的总体结构是一个带头循环双向链表

template 
struct __list_node {typedef void* void_pointer;void_pointer next;void_pointer prev;T data;
};

1. 这个是在stl3.0版本下的list的节点的定义。
2. 节点里面有一个前指针，一个后指针，有一个数据data。
3. 这里只能知道他是一个双向链表。
   💚💚💚💚💚💚💚💚💚💚💚💚💚💚💚💚💚
   我们看一下它的构造函数。

class list  --> list() { empty_initialize(); }void empty_initialize() { node = get_node();node->next = node;node->prev = node;}

综上：list的总体结构是一个带头循环双向链表。

List迭代器

迭代器通常是怎么使用的，看一下下面这段代码。

int main()
{list l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);l.push_back(5);l.push_back(6);list::iterator it = l.begin();while (it != l.end()){cout << *it << " ";it++;}cout << endl;return 0;
}

• 我们从list< int >当中定义一个iterator对象，然后让他去访问我们的节点
• 并且他所支持的操作有++，解引用，当然还有 - -

stl3.0当中的迭代器实现：

template
struct __list_iterator {typedef __list_iterator             iterator;typedef __list_iterator const_iterator;typedef __list_iterator           self;typedef bidirectional_iterator_tag iterator_category;typedef T value_type;typedef Ptr pointer;typedef Ref reference;typedef __list_node* link_type;typedef size_t size_type;typedef ptrdiff_t difference_type;link_type node;__list_iterator(link_type x) : node(x) {}__list_iterator() {}__list_iterator(const iterator& x) : node(x.node) {}bool operator==(const self& x) const { return node == x.node; }bool operator!=(const self& x) const { return node != x.node; }reference operator*() const { return (*node).data; }#ifndef __SGI_STL_NO_ARROW_OPERATORpointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */self& operator++() { node = (link_type)((*node).next);return *this;}self operator++(int) { self tmp = *this;++*this;return tmp;}self& operator--() { node = (link_type)((*node).prev);return *this;}self operator--(int) { self tmp = *this;--*this;return tmp;}

三级目录