相较于vector的连续线性空间，list就显得复杂许多，它的好处是每次插入或删除一个元素，就配置或释放一个元素空间。因此，list对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素移除，list永远是常数时间。
list不仅是一个双向链表，而且还是一个环状双向链表。另外，还有一个重要性质，插入操作和接合操作都不会造成原有的list迭代器失效，这在vector是不成立的。因为vector的插入操作可能造成记忆体重新配置，导致原有的迭代器全部失效。甚至list的元素删除操作（erase），也只有“指向被删除元素”的那个迭代器失效，其他迭代器不受任何影响。
以下是list的节点、迭代器数据结构设计以及list的源码剖析：
-
-
-
-
-
-
-
-
-
-
-
-
- template <class T>
- struct __list_node
- {
- typedef void* void_pointer;
- void_pointer next;
- void_pointer prev;
- T data;
- };
-
-
-
- template<class T, class Ref, class Ptr>
- struct __list_iterator
- {
- typedef __list_iterator<T, T&, T*> iterator;
- typedef __list_iterator<T, Ref, Ptr> self;
-
- typedef bidirectional_iterator_tag iterator_category;
- typedef T value_type;
- typedef Ptr pointer;
- typedef Ref reference;
- typedef __list_node<T>* 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; }
-
-
- pointer operator->() const { return &(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;
- }
- };
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- template <class T, class Alloc = alloc>
- class list
- {
- protected:
- typedef void* void_pointer;
- typedef __list_node<T> list_node;
-
-
- typedef simple_alloc<list_node, Alloc> list_node_allocator;
-
- public:
- typedef T value_type;
- typedef value_type* pointer;
- typedef value_type& reference;
- typedef list_node* link_type;
- typedef size_t size_type;
- typedef ptrdiff_t difference_type;
-
- typedef __list_iterator<T, T&, T*> iterator;
-
- protected:
- link_type node ;
-
-
- link_type get_node() { return list_node_allocator::allocate(); }
-
-
- void put_node(link_type p) { list_node_allocator::deallocate(p); }
-
-
-
- link_type create_node(const T& x)
- {
- link_type p = get_node();
- construct(&p->data, x);
- return p;
- }
-
-
- void destroy_node(link_type p)
- {
- destroy(&p->data);
- put_node(p);
- }
-
- protected:
-
- void empty_initialize()
- {
- node = get_node();
- node->next = node;
- node->prev = node;
- }
-
-
-
- void fill_initialize(size_type n, const T& value)
- {
- empty_initialize();
- __STL_TRY
- {
-
- insert(begin(), n, value);
- }
- __STL_UNWIND(clear(); put_node(node));
- }
-
-
- public:
- list() { empty_initialize(); }
-
- iterator begin() { return (link_type)((*node).next); }
-
-
- iterator end() { return node; }
-
-
- bool empty() const { return node->next == node; }
-
-
- size_type size() const
- {
- size_type result = 0;
- distance(begin(), end(), result);
- return result;
- }
-
- size_type max_size() const { return size_type(-1); }
- reference front() { return *begin(); }
- reference back() { return *(--end()); }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- iterator insert(iterator position, const T& x)
- {
- link_type tmp = create_node(x);
-
- tmp->next = position.node;
- tmp->prev = position.node->prev;
- (link_type(position.node->prev))->next = tmp;
- position.node->prev = tmp;
- return tmp;
- }
-
-
- void insert(iterator pos, size_type n, const T& x);
- void insert(iterator pos, int n, const T& x)
- {
- insert(pos, (size_type)n, x);
- }
- void insert(iterator pos, long n, const T& x)
- {
- insert(pos, (size_type)n, x);
- }
-
-
- void push_front(const T& x) { insert(begin(), x); }
-
- void push_back(const T& x) { insert(end(), x); }
-
-
- iterator erase(iterator position)
- {
- link_type next_node = link_type(position.node->next);
- link_type prev_node = link_type(position.node->prev);
- prev_node->next = next_node;
- next_node->prev = prev_node;
- destroy_node(position.node);
- return iterator(next_node);
- }
-
-
- iterator erase(iterator first, iterator last);
-
- void resize(size_type new_size, const T& x);
- void resize(size_type new_size) { resize(new_size, T()); }
- void clear();
-
-
- void pop_front() { erase(begin()); }
-
- void pop_back()
- {
- iterator tmp = end();
- erase(--tmp);
- }
-
- list(size_type n, const T& value) { fill_initialize(n, value); }
- list(int n, const T& value) { fill_initialize(n, value); }
- list(long n, const T& value) { fill_initialize(n, value); }
-
- ~list()
- {
-
- size_type size() const
- {
- size_type result = 0;
- distance(begin(), end(), result);
- return result;
- }
- clear();
-
- put_node(node);
- }
-
- list<T, Alloc>& operator=(const list<T, Alloc>& x);
-
- protected:
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- void transfer(iterator position, iterator first, iterator last)
- {
- if (position != last)
- {
- (*(link_type((*last.node).prev))).next = position.node;
- (*(link_type((*first.node).prev))).next = last.node;
- (*(link_type((*position.node).prev))).next = first.node;
- link_type tmp = link_type((*position.node).prev);
- (*position.node).prev = (*last.node).prev;
- (*last.node).prev = (*first.node).prev;
- (*first.node).prev = tmp;
- }
- }
-
- public:
-
- void splice(iterator position, list& x)
- {
- if (!x.empty())
- transfer(position, x.begin(), x.end());
- }
-
-
- void splice(iterator position, list&, iterator i)
- {
- iterator j = i;
- ++j;
- if (position == i || position == j) return;
- transfer(position, i, j);
- }
-
-
- void splice(iterator position, list&, iterator first, iterator last)
- {
- if (first != last)
- transfer(position, first, last);
- }
-
- void remove(const T& value);
- void unique();
- void merge(list& x);
- void reverse();
- void sort();
-
- };
-
-
- template <class T, class Alloc>
- void list<T, Alloc>::clear()
- {
- link_type cur = (link_type) node->next;
- while (cur != node)
- {
- link_type tmp = cur;
- cur = (link_type) cur->next;
- destroy_node(tmp);
- }
-
- node->next = node;
- node->prev = node;
- }
-
-
-
-
- template <class T, class Alloc>
- list<T, Alloc>& list<T, Alloc>::operator=(const list<T, Alloc>& x)
- {
- if (this != &x)
- {
- iterator first1 = begin();
- iterator last1 = end();
- const_iterator first2 = x.begin();
- const_iterator last2 = x.end();
- while (first1 != last1 && first2 != last2) *first1++ = *first2++;
- if (first2 == last2)
- erase(first1, last1);
- else
- insert(last1, first2, last2);
- }
- return *this;
- }
-
-
-
-
-
- template <class T, class Alloc>
- void list<T, Alloc>::unique()
- {
- iterator first = begin();
- iterator last = end();
- if (first == last) return;
- iterator next = first;
- while (++next != last)
- {
- if (*first == *next)
- erase(next);
- else
- first = next;
- next = first;
- }
- }
-
-
- template <class T, class Alloc>
- void list<T, Alloc>::merge(list<T, Alloc>& x)
- {
- iterator first1 = begin();
- iterator last1 = end();
- iterator first2 = x.begin();
- iterator last2 = x.end();
-
-
- while (first1 != last1 && first2 != last2)
- if (*first2 < *first1)
- {
- iterator next = first2;
- transfer(first1, first2, ++next);
- first2 = next;
- }
- else
- ++first1;
- if (first2 != last2)
- transfer(last1, first2, last2);
- }
STL源码分析--list
原文：http://blog.csdn.net/yusiguyuan/article/details/38875711
