對(duì)于vector而言，list就要復(fù)雜得多济赎，list 有2個(gè)特點(diǎn)：

• 相較于vector记某，它的好處是每次插入一個(gè)或刪除一個(gè)元素，就配置或釋放一個(gè)元素空間壳猜。所以list對(duì)空間不浪費(fèi)滑凉。
• 對(duì)于任何位置的元素插入或者元素移除，list永遠(yuǎn)是常數(shù)時(shí)間畅姊。

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

list.png

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

list node

• 結(jié)點(diǎn)

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

構(gòu)造結(jié)點(diǎn)

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

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é)點(diǎn)

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

迭代器

list不再能夠像vecctor一樣以普通指針作為迭代器朱嘴，因?yàn)槠涔?jié)點(diǎn)不保證在存儲(chǔ)空間中連續(xù)存在粗合。所以list迭代器必須有能力指向list的節(jié)點(diǎn)乌昔，并有能力進(jìn)行正確的遞增帚湘，遞減，取值，成員存取等操作资柔。

并且list是一個(gè)雙向鏈表撵割，迭代器必須具備前移，后移的能力羹与。庶灿，所以List提供的是一個(gè)Bidirectional iterators。

由于是鏈表往踢，一個(gè)重要性質(zhì)就是：插入操作和節(jié)后操作都不會(huì)造成原有的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;
    }
}

• 空l(shuí)ist插入第一個(gè)節(jié)點(diǎn)

  
  
  空l(shuí)ist插入第一個(gè)節(jié)點(diǎn).png

• 非空l(shuí)ist插入節(jié)點(diǎn)

  
  
  非空l(shuí)ist插入節(jié)點(diǎn).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é)點(diǎn)

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é)點(diǎn).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é)點(diǎn)

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é)點(diǎn)

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()