STL—list

前面我們分析了vector，這篇介紹STL中另一個重要的容器list

list的設計

list由三部分構成：list節點、list迭代器、list本身

list節點

list是一個雙向鏈表，所以其list節點中有前後兩個指針。如下：

// list節點
template <typename T>
struct __list_node
{
        typedef void* void_pointer;
        void_pointer prev; // 指向前一個節點
        void_pointer next; // 指向下一個節點
        T data; // 節點的值
};

list迭代器

前面我們說過vector是利用其記憶體分配類型成員給vector分配一大塊記憶體，而其迭代器是原始指針，所以其迭代器的移動就是指針的移動，vector那樣通過指針的移動就能得到下一個元素，不需要特別設計。而list是鏈表結構，鏈表中每個節點的記憶體不連續，list的迭代器就是對外隱藏了從一個節點是如何移動到下一個節點的具體細節，使得外部只要將迭代器自增或自減就能得到相鄰的節點。

list迭代器只有一個指向鏈表節點的指針數據成員。如下：

        typedef __list_node<T>* link_type;

        link_type node;  // point to __list_node

下麵是迭代器的前置自增和前置自減運算符的源碼，可以看到是通過節點的前向和後向指針來完成從一個節點移動到另一個節點：

        self& operator++() { node = (link_type)(*node).next; return *this;}
        self& operator--() { node = (link_type)(*node).prev; return *this;}

list

和vector一樣，list也有個空間配置器的類型成員，通過該類型來為list的每個節點分配記憶體，並且通過該類型成員將外部指定的節點數目轉換為相應節點所需的記憶體。所以list的記憶體模型是每個鏈表節點分配一塊單獨的記憶體，然後將每個節點連接起來。而vector的記憶體模型是分配一大塊連續的記憶體。如下：

          // 空間配置器
          typedef simple_alloc<list_node, alloc> list_node_allocator;

實際上，list不僅是一個雙向鏈表，而且還是一個環狀的雙向鏈表。為了設計的方便，在list中放置一個node指針，該指針指向一個空白節點，該空白節點的下一個節點是鏈表中起始節點，而鏈表的尾節點的下一個節點為該空白節點。雖然list底層是一個環狀雙向鏈表，但通過這樣設計後對外就表現出一個普通的雙向鏈表，符合一般習慣。這樣設計還有很多好處，比如快速得到鏈表的首尾節點。如下。

private:
        //指向空白節點
        link_type               node;
public:
        // 通過空白節點node完成
        iterator begin() const { return (link_type)(*node).next; }
        iterator end() const { return node;}
        bool empty() const { return node->next == node; }

下麵我們看list內部是如何構造一個鏈表的。以我們對list的常用使用方法 list<int> lis(10)為例：

首先調用構造函數

        explicit list(size_type n)
        {
                empty_initialize();
                insert(begin(), n, T());
        }

該構造函數會先調用empty_initialize()為list分配一個空白節點，並設置前向後向指針

        void empty_initialize()
        {
                node = get_node();
                node->next = node;
                node->prev = node;
        }
        link_type get_node() { return list_node_allocator::allocate(1);}

然後構造函數會迴圈以插入相應個數的鏈表節點，每次插入時會分配一個節點大小的記憶體，然後對這塊記憶體初始化，註意插入位置是在指定位置之前插入。由於list的記憶體模型和vector記憶體模型的區別，vector每次插入時由於可能會造成記憶體的重新配置，會造成原先所有的迭代器失效。而list的插入只是為新節點分配記憶體，並將其添加到鏈表中，對鏈表中其他節點的記憶體不會造成影響，所以list的插入則不會引起迭代器失效。如下。

template <typename T>
void
list<T>::insert(iterator position, size_type n, const T& x)
{
        for (; n > 0; --n)
                insert(position, x);
}

template <typename T>
void
list<T>::insert(iterator position, const T& x)//posiiton之前插入
{
        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;
}

link_type create_node(const T& x)
{
        link_type p = get_node();
        construct(&p->data, x);
        return p;
}

link_type get_node() { return list_node_allocator::allocate(1);}

（全文完）