對于vector而言，list就要復雜得多，list 有2個特點：

• 相較于vector，它的好處是每次插入一個或刪除一個元素，就配置或釋放一個元素空間。所以list對空間不浪費。
• 對于任何位置的元素插入或者元素移除，list永遠是常數(shù)時間。

list結(jié)構(gòu)是雙向循環(huán)鏈表：

list.png

結(jié)點內(nèi)存管理

list node

• 結(jié)點

  struct ListNode {
        ListNode *_prev;
        ListNode *_next;
        T _data;
    };
  

構(gòu)造結(jié)點

• 第1個版本為構(gòu)造有數(shù)據(jù)域結(jié)點
• 第2個版本構(gòu)造沒有數(shù)據(jù)域結(jié)點

template<typename T>
typename List<T>::nodePtr List<T>::createListNode(const T &value) {
    nodePtr ptrTmp = nodeAlloc::allocate();
    ptrTmp->_prev = nullptr;
    ptrTmp->_next = nullptr;
    allocator<T>::construct(&(ptrTmp->_data), value);

    return ptrTmp;
}

template<typename T>
typename List<T>::nodePtr List<T>::createListNode() {
    nodePtr ptrTmp = nodeAlloc::allocate();
    ptrTmp->_prev = nullptr;
    ptrTmp->_next = nullptr;

    return ptrTmp;
}

銷毀結(jié)點

template<typename T>
    void List<T>::deleteNode(nodePtr p) {
    allocator<T>::destroy(&(p->_data));
    nodeAlloc::deallocate(p);
}

迭代器

list不再能夠像vecctor一樣以普通指針作為迭代器，因為其節(jié)點不保證在存儲空間中連續(xù)存在。所以list迭代器必須有能力指向list的節(jié)點，并有能力進行正確的遞增，遞減，取值，成員存取等操作。

并且list是一個雙向鏈表，迭代器必須具備前移，后移的能力。，所以List提供的是一個Bidirectional iterators。

由于是鏈表，一個重要性質(zhì)就是：插入操作和節(jié)后操作都不會造成原有的list迭代器失效

struct ListIterator : public iterator<bidirectional_iterator_tag, T> {
    ......
    typedef ListNode<T> *nodePtr;
    
    nodePtr p;
}

插入元素

void push_back(const T &value)

void List<T>::push_back(const T &value){
    if (empty()) {
        nodePtr ptrTmp = createListNode(value);
        ptrTmp->_prev = nullptr;
        _end.p->_prev = ptrTmp;
        ptrTmp->_next = _end.p;
        _begin.p = ptrTmp;
    } else {
        nodePtr ptrTmp = createListNode(value);
        nodePtr oldEndPrevNode = _end.p->_prev;

        oldEndPrevNode->_next = ptrTmp;
        ptrTmp->_prev = oldEndPrevNode;
        ptrTmp->_next = _end.p;
        _end.p->_prev = ptrTmp;
    }
}

• 空list插入第一個節(jié)點

  
  
  空list插入第一個節(jié)點.png

• 非空list插入節(jié)點

  
  
  非空list插入節(jié)點.png

void push_front(const T& value)

void List<T>::push_front(const T &value) {
    auto ptrTmp = createListNode(value);
    auto oldStartNode = _begin.p;
    oldStartNode->_prev = ptrTmp;

    ptrTmp->_prev = nullptr;
    ptrTmp->_next = oldStartNode;

    _begin.p = ptrTmp;
}

push_front.png

iterator insert(iterator position, const T& val)

• 3種情況：
  • position == _begin
    push_front(val)
  • position == _end
    push_back(val)
  • position 等于中間節(jié)點

if (position == begin()) {
    push_front(val);
    return begin();
} 
else if (position == end()) {
    auto ret = position;
    push_back(val);
    return ret;
}
auto node = createListNode(val);
(position.p->_prev)->_next = node;
node->_next = position.p;
node->_prev = (position.p)->_prev;
(position.p)->_prev = node;

return iterator(node);

position 等于中間節(jié)點.png

void insert(iterator position, size_type n, const T& value)

void List<T>::insert(iterator position, size_type n, const T& value)
{
    for (auto i = n; i != 0; --i)
        position = insert(position, value);
}

void insert(iterator position, InputIterator first, InputIterator last)

void List<T>::insert(iterator position, InputIterator first, InputIterator last) 
{
    for (; first != last; first++)           
        position = insert(position, *first);
}

刪除節(jié)點

void pop_front()

if (empty())
    throw std::out_of_range("pop_front() on empty List");
auto oldNode = _begin.p;
_begin.p = oldNode->_next;
_begin.p->_prev = nullptr;
deleteNode(oldNode);

pop_front.png

void pop_back()

if (empty())
    throw std::out_of_range("pop_back() on empty List");

auto new_end_p = _end.p->_prev;
new_end_p->_next = nullptr;
allocator<T>::destroy(&(new_end_p->_data));     // 析構(gòu)元素

nodeAlloc::deallocate(_end.p);  // 釋放原_end.p內(nèi)存
_end.p = new_end_p;

iterator erase(iterator position)

• 分為3種情況：
  • 刪除_begin
  • 刪除_end
  • 刪除中間節(jié)點

if (position == _begin) {
    pop_front();
    return _begin;
}
else if (position == _end) {
    pop_back();
    return _end;
}
else {
    auto prevNode = position.p->_prev;
    auto nextNode = position.p->_next;

    prevNode->_next = nextNode;
    nextNode->_prev = prevNode;
    deleteNode(position.p);
            
    return iterator(nextNode);
}

反轉(zhuǎn)list

void reverse()

去重

void unique()