list不同于vector，每個節點的結構需要自行定義，迭代器屬于雙向迭代器（不是隨即迭代器），也需要自行定義。和通用迭代器一樣，list的迭代器需要實現的操作有：++、--、*、->、==、!=。節點的數據結構命名為list_node，迭代器的數據結構命名為list_iterator。list中對迭代器的操作不應該使用算數運算，如+2、-3這樣的操作，只應該使用++、--來移動迭代器。STI版本的STL使用了一個環形list，list.end()指向一個空白節點（不存放數據）作為尾節點，空白節點的next指針指向第一個節點，空白節點的prev指針指向最后一個節點，這樣就能方便的實現begin()和end()操作，當list為空時，空白節點的next和prev均指向自己。這樣的設計是很巧妙的，省去了很多插入、刪除操作時需要考慮的邊界條件。 ~~~ #ifndef __MYLIST_H__ #define __MYLIST_H__ // list節點 template <class Type> class list_node { public: list_node<Type> *prev; list_node<Type> *next; Type data; }; // list迭代器 template <class Type> class list_iterator { public: // 迭代器必須定義的五個相應類型 typedef Type value_type; typedef Type* pointer; typedef Type& reference; typedef size_t difference_type; typedef std::bidirectional_iterator_tag iterator_category; list_iterator() : node(NULL) {} list_iterator(list_node<Type> *x) : node(x) {} list_iterator(const list_iterator<Type> &x) : node(x.node) {} // 成員函數盡量加const bool operator== (const list_iterator<Type> &rhs) const { return node == rhs.node; } bool operator!= (const list_iterator<Type> &rhs) const { return !(operator==(rhs)); // 調用現有函數，好的策略 } // 對迭代器接引用返回指向數據的引用 reference operator* () const { return node->data; } pointer operator-> () const { return &(operator*()); // 調用現有函數，好的策略 } list_iterator& operator++ () { node = node->next; return *this; } list_iterator operator++ (int) { list_iterator<Type> old = *this; ++(*this); return old; } list_iterator& operator-- () { node = node->prev; return *this; } list_iterator operator-- (int) { list_iterator<Type> old = *this; --(*this); return old; } // 迭代器通過這個指針與某個節點相聯系 list_node<Type> *node; }; // list數據結構，SGI中的list是一個環形鏈表，這里相同 // list內部使用list_node訪問每一個保存數據的節點，對外則返回給用戶一個list_iterator迭代器，這是需要注意的 template <class Type> class List { public: typedef list_iterator<Type> iterator; // iterator類型是每個容器必備的，應該盡早定義它 typedef size_t size_type; // 構造函數 List() { node = get_node(); // 前后指針都指向自己，表示此list為空 node->next = node; node->prev = node; } iterator begin() { return (list_iterator<Type>)node->next; } iterator end() { return (list_iterator<Type>)node; } bool empty() { return node->next == node; // 參見默認構造函數 } size_type size() { size_type len = 0; distance(begin(), end(), len); return len; } Type& front() { return *begin(); } Type& back() { return *(--end()); } // 插入操作 iterator insert(iterator position, const Type &value) { list_node<Type> *newNode = create_node(value); newNode->next = position.node; newNode->prev = position.node->prev; position.node->prev->next = newNode; position.node->prev = newNode; return (iterator)newNode; // 顯示類型轉換 } void push_back(const Type &value) { insert(end(), value); } void push_front(const Type &value) { insert(begin(), value); } // 刪除操作 iterator erase(iterator position) { list_node<Type> *next = position.node->next; list_node<Type> *prev = position.node->prev; prev->next = next; next->prev = prev; destroy_node(position.node); return (iterator)next; } void pop_back() { iterator tmp = end(); erase(--tmp); } void pop_front() { erase(begin()); } // 清除所有節點 void clear() { list_node<Type> *pnode = node->next; while (pnode != node) { list_node<Type> *tmp = pnode->next; destroy_node(pnode); pnode = tmp; } node->next = node; node->prev = node; } // 刪除值為value的所有節點 void remove(const Type &value) { // 為了使用上面的erase，這里定義iterator而不是list_node iterator first = begin(); iterator last = end(); while (first != last) { iterator next = first; ++next; if (*first == value) erase(first); first = next; } } private: // 分配一個節點 list_node<Type>* get_node() { return alloc.allocate(1); } // 釋放一個節點 void put_node(list_node<Type> *p) { alloc.deallocate(p, 1); } // 分配并構造一個節點 list_node<Type>* create_node(const Type &value) { list_node<Type> *p = get_node(); alloc.construct(&(p->data), value); return p; } // 析構并釋放一個節點 void destroy_node(list_node<Type> *p) { alloc.destroy(&(p->data)); put_node(p); } private: list_node<Type> *node; // 空白節點，指向list.end() static std::allocator< list_node<Type> > alloc; // 空間配置器 }; // 類中的靜態成員一定要記得在類外定義，否則鏈接時會出錯 template <class Type> std::allocator< list_node<Type> > List<Type>::alloc; #endif ~~~ 析構函數忘記寫了，這里補上： ~~~ ~List() { clear(); if (node != NULL) delete node; } ~~~ 測試代碼： ~~~ int main() { List<int> l; l.push_back(1); l.push_back(2); l.push_back(3); l.push_back(4); l.push_back(5); copy(l.begin(), l.end(), ostream_iterator<int>(cout, " ")); cout << endl; // 1 2 3 4 5 List<int>::iterator iter = find(l.begin(), l.end(), 3); iter = l.erase(iter); copy(l.begin(), l.end(), ostream_iterator<int>(cout, " ")); cout << endl; // 1 2 4 5 l.insert(iter, 123); copy(l.begin(), l.end(), ostream_iterator<int>(cout, " ")); cout << endl; // 1 2 123 4 5 l.push_front(0); copy(l.begin(), l.end(), ostream_iterator<int>(cout, " ")); cout << endl; // 0 1 2 123 4 5 l.pop_back(); copy(l.begin(), l.end(), ostream_iterator<int>(cout, " ")); cout << endl; // 0 1 2 123 4 l.pop_front(); copy(l.begin(), l.end(), ostream_iterator<int>(cout, " ")); cout << endl; // 1 2 123 4 l.clear(); copy(l.begin(), l.end(), ostream_iterator<int>(cout, " ")); cout << endl; // null l.push_back(1); l.push_back(2); l.push_back(3); l.push_front(4); l.push_front(5); l.push_front(6); l.remove(1); l.remove(2); l.remove(3); l.remove(5); copy(l.begin(), l.end(), ostream_iterator<int>(cout, " ")); cout << endl; system("pause"); return 0; } ~~~ 運行結果：  參考： 《STL源碼剖析》