《STL源码剖析》笔记：list

对于vector而言，list就要复杂得多，list 有2个特点：

• 相较于vector，它的好处是每次插入一个或删除一个元素，就配置或释放一个元素空间。所以list对空间不浪费。
• 对于任何位置的元素插入或者元素移除，list永远是常数时间。

list结构是双向循环链表：

list.png

结点内存管理

list node

• 结点

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

构造结点

• 第1个版本为构造有数据域结点
• 第2个版本构造没有数据域结点

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;
}

销毁结点

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

迭代器

list不再能够像vecctor一样以普通指针作为迭代器，因为其节点不保证在存储空间中连续存在。所以list迭代器必须有能力指向list的节点，并有能力进行正确的递增，递减，取值，成员存取等操作。

并且list是一个双向链表，迭代器必须具备前移，后移的能力。，所以List提供的是一个Bidirectional iterators。

由于是链表，一个重要性质就是：插入操作和节后操作都不会造成原有的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插入第一个节点

  
  空list插入第一个节点.png

• 非空list插入节点

  
  非空list插入节点.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 等于中间节点

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 等于中间节点.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);
}

删除节点

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));     // 析构元素

nodeAlloc::deallocate(_end.p);  // 释放原_end.p内存
_end.p = new_end_p;

iterator erase(iterator position)

• 分为3种情况：
  • 删除_begin
  • 删除_end
  • 删除中间节点

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);
}

反转list

void reverse()

去重

void unique()