list是一个线性双向链表结构，它的数据由若干个节点构成，每一个节点都包括一个信息块（即实际存储的数据）、一个前驱指针和一个后驱指针。它无需分配指定的内存大小且可以任意伸缩，这是因为它存储在非连续的内存空间中，并且由指针将有序的元素链接起来。由于其结构的原因，list 随机检索的性能非常的不好，因为它不像vector 那样直接找到元素的地址，而是要从头一个一个的顺序查找，这样目标元素越靠后，它的检索时间就越长。检索时间与目标元素的位置成正比。虽然随机检索的速度不够快，但是它可以迅速地在任何节点进行插入和删除操作。因为list 的每个节点保存着它在链表中的位置，插入或删除一个元素仅对最多三个元素有所影响，不像vector 会对操作点之后的所有元素的存储地址都有所影响，这一点是vector 不可比拟的。
节点跟一般的链表节点一样
//list的节点 template<class T> struct ListNode { typedef ListNode* pointer; pointer prev; pointer next; T data; };list不再能够像vector一样以普通的指针来作为迭代器，因为其节点不保证在存储空间中连续存在。list迭代器必须有能力指向list的节点，并有能力进行正确的递增、递减、取值、成员存取等操作。递增时指向下一个节点，递减的时候指向上一个节点，取值时候取的是节点的数据值，成员取用的是节点的成员。
由于STL list是一个双向链表（double linked-list），迭代器必须具备前移和后移的能力，所有list提供的是Bidirectional iterators；
另外，值得注意的是，插入（insert）和接合操作（splice）都不会造成原有的list迭代器失效。
#ifndef _MYLIST #define _MYLIST //list的节点 template<class T> struct ListNode { typedef ListNode* pointer; pointer prev; pointer next; T data; }; template<class T, class Ref, class Ptr> struct MyListIterator { //迭代器类型 typedef MyListIterator<T, T&, T*> iterator; //跟MyListIterator类型相同 typedef MyListIterator<T, Ref, PTR> self; typedef bidirectional_iterator_tag iterator_category; //数据的类型，如int typedef T value_type; //指向数据的指针，如int* typedef Ptr pointer; //数据的引用，如int& typedef Ref reference; //指向list节点的指针 typedef ListNode<T>* link_type; //大小 typedef size_t size_type; link_type node; //************************************ // Method: MyListIterator // Desc: 构造函数 // Author: // Date: 2019/07/18 // FullName: MyListIterator<T, Ref, Ptr>::MyListIterator // Returns: // Parameter: link_type x： 指向list节点的指针 //************************************ MyListIterator(link_type x) :node(x) { } MyListIterator() { } //************************************ // Method: MyListIterator // Desc: 构造函数 // Author: // Date: 2019/07/18 // FullName: MyListIterator<T, Ref, Ptr>::MyListIterator // Returns: // Parameter: const iterator &x： 另一个迭代器 //************************************ MyListIterator(const iterator &x) const: node(x.node) { } //************************************ // Method: operator== // Desc: 重载==，判断两个迭代器是否相同 // Author: // Date: 2019/07/18 // FullName: MyListIterator<T, Ref, Ptr>::operator== // Returns: bool // Parameter: const self & x :MyListIterator类型的迭代器 //************************************ bool operator==(const self& x) const { return node == x.node; } bool operator!=(const self& x) const { return node != x.node; } //************************************ // Method: operator* // Desc: 对迭代器取值，取的是节点的数据值 // Author: // Date: 2019/07/18 // FullName: MyListIterator<T, Ref, Ptr>::operator* // Returns: reference //************************************ reference operator*() const { return (*node).data; } //************************************ // Method: operator-> // Desc: 对迭代器的成员存取运算子的标准做法 // Author: // Date: 2019/07/18 // FullName: MyListIterator<T, Ref, Ptr>::operator-> // Returns: pointer //************************************ pointer operator->()const { return &(operator*()); } //************************************ // Method: operator++ // Desc: 前置自增 // Author: // Date: 2019/07/18 // FullName: MyListIterator<T, Ref, Ptr>::operator++ // Returns: self&： 自身迭代器 //************************************ self& operator++() { node = node.next; return *this; } //************************************ // Method: operator++ // Desc: 后置自增 // Author: // Date: 2019/07/18 // FullName: MyListIterator<T, Ref, Ptr>::operator++ // Returns: self&： 新的迭代器 // Parameter: int： 无用的 //************************************ self& operator++(int) { self temp = *this; ++(*this); return temp; } self& operator++() { node = node.prev; return *this; } self& operator--(int) { self temp = *this; --(*this); return temp; } }; #endif