4.3-list

4.3.2 list的节点

template <class T>
struct __list_node {
  typedef void* void_pointer;
  void_pointer  next;
  void_pointer  prev;
  T             data;
};

list的插入操作和接合操作都不会造成原有的迭代器失效

4.3.3 list的迭代器

template<class T, class Ref, class Ptr>
struct __list_iterator {
    typedef __list_iterator<T, T&, T*>             iterator;
    typedef __list_iterator<T, const T&, const T*> const_iterator;
    typedef __list_iterator<T, Ref, Ptr>           self;

    typedef bidirectional_iterator_tag iterator_category;
    typedef T               value_type;
    typedef Ptr             pointer;
    typedef Ref             reference;
    typedef __list_node<T>* link_type;
    typedef size_t          size_type;
    typedef ptrdiff_t       difference_type;

    link_type node; // 迭代器内部的指针，指向list的节点

    __list_iterator(link_type x) : node(x) {}
    __list_iterator() {}
    __list_iterator(const iterator& x) : node(x.node) {}

    bool operator==(const self& x) const { return node == x.node; }
    bool operator!=(const self& x) const { return node != x.node; }
    reference operator*() const { return (*node).data; }

    pointer operator->() const { return &(operator*()); }

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

4.3.4 list的数据结构

template <class T, class Alloc = alloc>
class list {
protected:
    typedef __list_node<T> list_node;
    typedef simple_alloc<list_node, Alloc> list_node_allocator;	// 分配器
public:      
    typedef T           value_type;
    typedef value_type* pointer;
    typedef value_type& reference;
    typedef list_node*  link_type;
    typedef size_t      size_type;
    typedef ptrdiff_t   difference_type;
};

几个简单的函数

iterator begin() { return (link_type)((*node).next); }
iterator end() { return node; }
bool empty() const { return node->next == node; }
size_type size() const {
    size_type result = 0;
    distance(begin(), end(), result);	// 计算两个迭代器之间的距离
    return result;
}
reference front() { return *begin(); }
reference back() { return *(--end()); }

配置、释放、构造、销毁一个节点

// 配置一个节点并传回
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 destroy_node(link_type p) {
    destroy(&p->data);
    put_node(p);
}

空的list

list() { empty_initialize(); }
void empty_initialize() { 
    node = get_node();
    node->next = node;
    node->prev = node;
}

4.3.6 list的元素操作

push_front和push_back插入元素会调用insert

void push_front(const T& x) { insert(begin(), x); }
void push_back(const T& x) { insert(end(), x); }

// 在迭代器position前面插入一个节点
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;
}

pop_front和pop_back删除元素会调用erase

void pop_front() { erase(begin()); }
void pop_back() { 
    iterator tmp = end();
    erase(--tmp);
}

// 删除迭代器position所指节点
iterator erase(iterator position) {
    link_type next_node = link_type(position.node->next);
    link_type prev_node = link_type(position.node->prev);
    prev_node->next = next_node;
    next_node->prev = prev_node;
    destroy_node(position.node);
    return iterator(next_node);
}

clear清除整个链表

template <class T, class Alloc> 
void list<T, Alloc>::clear() {
    link_type cur = (link_type) node->next;	// node的next就是头结点
    while (cur != node) {
        link_type tmp = cur;
        cur = (link_type) cur->next;
        destroy_node(tmp);
    }
    node->next = node;
    node->prev = node;
}

remove删除值为value的节点

template <class T, class Alloc>
void list<T, Alloc>::remove(const T& value) {
    iterator first = begin();
    iterator last = end();
    while (first != last) {
        iterator next = first;
        ++next;
        if (*first == value) erase(first);
        first = next;
    }
}

unique移除数值相同的连续元素

template <class T, class Alloc>
void list<T, Alloc>::unique() {
    iterator first = begin();
    iterator last = end();
    if (first == last) return;
    iterator next = first;
    while (++next != last) {
        if (*first == *next)
            erase(next);
        else
            first = next;
        next = first;
    }
}

transfer将[first, end)内的所有元素移动到position之前

void transfer(iterator position, iterator first, iterator last) {
    if (position != last) {
        (*(link_type((*last.node).prev))).next = position.node;
        (*(link_type((*first.node).prev))).next = last.node;
        (*(link_type((*position.node).prev))).next = first.node;  
        link_type tmp = link_type((*position.node).prev);
        (*position.node).prev = (*last.node).prev;
        (*last.node).prev = (*first.node).prev; 
        (*first.node).prev = tmp;
    }
}

transfer是内部接口，提供给外部的接口是splice，且有多个版本

// 版本1：将另一个list接到position前面
void splice(iterator position, list& x) {
    if (!x.empty()) 
        transfer(position, x.begin(), x.end());
}

// 版本2：将i所指元素接到position前面，position和i可以指向同一个list
void splice(iterator position, list&, iterator i) {
    iterator j = i;
    ++j;
    if (position == i || position == j) return;
    transfer(position, i, j);
}

// 版本3：将[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);
}

merge合并两个排序list

template <class T, class Alloc>
void list<T, Alloc>::merge(list<T, Alloc>& x) {
    iterator first1 = 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);
}

reverse反转

template <class T, class Alloc>
void list<T, Alloc>::reverse() {
    // 空节点或只要一个节点直接返回
    if (node->next == node || link_type(node->next)->next == node) return;
    iterator first = begin();
    ++first;
    while (first != end()) {
        iterator old = first;
        ++first;
        transfer(begin(), old, first);
    }
} 

sort排序，只能使用list自己的，不能用STL的算法的sort，因为其只接受RandomAccessIterator

template <class T, class Alloc>
void list<T, Alloc>::sort() {
    if (node->next == node || link_type(node->next)->next == node) return;
    list<T, Alloc> carry;
    list<T, Alloc> counter[64];
    int fill = 0;
    while (!empty()) {
        carry.splice(carry.begin(), *this, begin());
        int i = 0;
        while(i < fill && !counter[i].empty()) {
            counter[i].merge(carry);
            carry.swap(counter[i++]);
        }
        carry.swap(counter[i]);         
        if (i == fill) ++fill;
    } 

    for (int i = 1; i < fill; ++i) counter[i].merge(counter[i-1]);
    swap(counter[fill-1]);
}