相较于vector的连续线性空间，list就显得复杂许多，它的好处是每次插入或删除一个元素，就配置或释放一个元素空间。因此，list对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素移除，，list永远是常数时间。
list 内部为双向链表，内部元素互相以link串接起来，每个元素都知道其前一个元素以及下一个元素的位置。
template <class T>struct __list_node { typedef void* void_pointer; void_pointer next; void_pointer prev; T data;};
list节点并不一定在连续空间上，所以不能像vector一样用原生指针做迭代器，其迭代器必须实现前移、后移、取值等操作。 list插入操作和接合操作都不会造成原有的list迭代器失效，这在vector是不成立的。因为vector的插入操作可能造成内存重新配置，导致原有的迭代器全部失效。甚至list的元素删除操作（erase），也只有“指向被删除元素”的那个迭代器失效，其他迭代器不受任何影响。
来看源码：
template<class T, class Ref, class Ptr>struct __list_iterator { typedef __list_iterator<T, T&, T*>iterator; typedef __list_iterator<T, const T&, const T*> const_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结点 __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; } 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 __list_iterator<T, T&, T*>iterator; typedef __list_iterator<T, const T&, const T*> const_iterator;protected: link_type node;protected: 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();__STL_TRY {construct(&p->data, x);}__STL_UNWIND(put_node(p));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)); }protected: //将[first,last)内元素迁移到position处 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()); } public: list() { empty_initialize(); } iterator begin() { return (link_type)((*node).next); } const_iterator begin() const { return (link_type)((*node).next); } iterator end() { return node; } const_iterator end() const { 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(); } const_reference front() const { return *begin(); } reference back() { return *(–end()); } const_reference back() const { return *(–end()); } void swap(list<T, Alloc>& x) { __STD::swap(node, x.node); } 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 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); } void pop_front() { erase(begin()); } void pop_back() {iterator tmp = end();erase(–tmp); } };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);}<class T, class Alloc>void list<T, Alloc>::sort() { if (node->next == node || link_type(node->next)->next == node) return; list<T, Alloc> carry; list<T, Alloc> counter[64]; int fill = 0; while (!empty()) {carry.splice(carry.begin(), *this, begin()); //将begin处的元素从list取下，insert到carry中int i = 0;while(i < fill && !counter[i].empty()) {counter[i].merge(carry);carry.swap(counter[i++]);}carry.swap(counter[i]);if (i == fill) ++fill; }for (int i = 1; i < fill; ++i) counter[i].merge(counter[i-1]); swap(counter[fill-1]);}template <class T, class Alloc> template <class Predicate>void list<T, Alloc>::remove_if(Predicate pred) { iterator first = begin(); iterator last = end(); while (first != last) {iterator next = first;++next;if (pred(*first)) erase(first);first = next; }}
敏而好学，不耻下问。
