《STL 源碼剖析》 list 實作原理

list概述
list疊代器
list資料結構
list 構造與記憶體管理
list 操作實作原理
- list的transfer(前移操作)
- splice實作原理
- merge實作原理
- list.sort 實作原理

list對空間的運用是精準的，不浪費的。對于任何位置的元素插入或元素移除，list永遠是常數時間。

list實作上就是一個雙向循環連結清單，list節點有prev 和 next 兩個指針。

因為list是一個雙向連結清單，他的疊代器就必須具備前移、後移的能力。list提供的是 Bidirectional Iterators。

list性質：插入操作、接合操作，不會造成原有的list疊代器失效，即使删除操作，也隻是被指向删除元素的那個疊代器失效，其他不受影響。(這個和vector 有很大差别)

list是一個環狀雙向連結清單，是以它隻需要一個指針就能夠表現出整個完整連結清單

template <class T, class Alloc = alloc>
class list
{
protected:
    typedef __list_node<T> list_node;
public:
    typedef list_node* link_type;
 
protected:
    link_type node;// 隻要一個指針，就表示整個連結清單
...
};

node指向尾端的一個空白節點，就能符合 ”前閉後開“ 區間的要求。

基本操作：

iterator begin() { return (link_type)((*node).next); }
 
iterator end() { return node; }
 
bool empty() const { return node->next == node; }
 
size_type size() const { // C++11 之前 複雜度線性,11之後複雜度 常數
    size_type result = 0;
    distance(begin(),end(),result); // stl 全局函數
    return result;
}
 
 
reference front() { return *begin(); }
reference back() { return *(--end()); }

class list
{
protected:
    // 專屬的空間配置器，每次配置一個節點大小
    typedef simple_alloc<list_node, Alloc> list_node_allocator;
 
// list_node_allocator(n) 辨別配置n個節點空間
 
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();
        construct(&p->data, x);// 構造工具
        return p;
    }
 
    void destory_node(link_type p) // 析構 并 釋放空間
    {
        destory(&p->data); // 析構
        put_node(p); // 釋放
    }
 
public:
    list() { empty_initialize(); }// 構造空連結清單
    void push_back(const T& x) { insert(end(), x); }
     
    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;
    }
 
 
protected:
    void empty_initialize()
    {
        node = get_node();
        node->next = node;
        node->prev = node;
    }
 
 
...
};

push_front、push_back、erase、pop_front、pop_back 這些操作實作上和通常手寫連結清單的實作相同。

将連續範圍的元素遷移到特定位置之前，實作上就是節點指針的重新連接配接。

transfer 是其他複雜操作的基礎，如splice、sort、merge

transfer 不是公開接口

對于transfer的巧妙運用

void splice(iterator position, list& x) //将 x 拼接到 position位置之前
{
    if(!x.empty())
        transfer(position, x.begin(), x.end());
}
 
void splice(iterator position, list&, iterator i) // 将i的元素拼接到position之前，兩者 可能是同一個list
{
    iterator j = i;
    ++j;
    if(position == i || position == j) return;
    transfer(position, i, j);
}
 
// 将[first, last)的元素接到position位置之前
// position 和 [first, last) 可能會指向同一個list
// 但是 position 不能位于[first,last)
void splice(iterator position, list&, iterator first, iterator last)
{
    if(first != last)
        transfer(position, first, last);
}

前提：兩個已經排好序的連結清單

周遊其中一個連結清單，記錄過程中周遊頭尾指針(周遊過程中進行大小比較)。将其拼接到另一個連結清單上。

實作上和普通連結清單合并是類似的。

template <class T, class Alloc>
void list<T, Alloc>::merge(list<T, Alloc>& x)
{
    iterator firts1 = 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); // 如果末尾還有殘留部分
}

list不能使用STL的sort，是因為 STL 的 sort 隻接受 RamdonAccessIterator (随機通路的疊代器類型)，而list中是 Bidirectional (雙向疊代器類型)
list.sort實作原理，思想非常類似于歸并排序，但源碼實作上卻不太好看出來和歸并類似，需要自己手動模拟才能有所體會。
其具體思想可檢視參考部落格
下圖是對應該部落格描述的步驟和實作源碼

《STL 源碼剖析》 list 實作原理