STL list 模拟实现

因为本学期要学数据结构，心血来潮打算看看 STL 的源码
参考的是侯捷先生《STL源码剖析》中推荐的 SGI STL 版本（也从网上参考了很多不同的实现方式）
模拟实现的时候去掉了 空间配置器（allocator） 的实现部分（因为看不明白）
因为时间不多所以只能简单的贴上代码，等有时间再来完善

模拟实现

#include <assert.h>

#include <type_traits>

namespace ximo {
// 链表节点
template <class T>
struct _List_node {
    _List_node<T> *_next;  // 后驱指针
    _List_node<T> *_prev;  // 前驱指针
    T _data;               // 数据域

    // 构造函数
    _List_node(const T &x = T()) : _next(0), _prev(0), _data(x) {}
};

// 链表迭代器
// list 是一个链表, 在空间上不是连续的, 因此原生指针无法进行
// list 迭代器的各项操作(++、--、* 等), 想要满足 list 迭代器的需求
// 就必须对指针进行封装和重载, 单独提供一个类

// 常规写法, 分别实现一个普通迭代器和 const 迭代器, 但是会造成代码极度冗余
// const 迭代器和普通迭代器的实现只有类型名称和返回值不一样
/*template <class T>
struct _List_iterator {
    ...
};
template <class T>
struct _List_const_iterator {
    ...
};*/
// STL 实现, 在定义 template 模板时增加模板参数 Ref 和 Ptr

// 关于为什么需要实现 const_iterator 可参考
// https://www.cnblogs.com/yyehl/p/yyehl.html
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 Ptr pointer;
    typedef Ref reference;
    typedef _List_node<T> Node;

    // _List_iterator 有一个 list 节点的指针, 但不需要做深拷贝和析构
    // 因为这个节点是属于 list 的, 而不是迭代器的
    Node *_node;  // 迭代器内部指针, 指向 list 节点

    // 默认构造函数
    _List_iterator() {}
    // 构造函数
    _List_iterator(Node *x) : _node(x) {}
    // 复制构造函数 (注: 不能为 const_iterator &x)
    _List_iterator(const iterator &x) : _node(x._node) {}

    // 注: 不能为 const iterator &x
    bool operator==(const_iterator &x) const { return _node == x._node; }
    // 注: 不能为 const iterator &x
    bool operator!=(const_iterator &x) const { return _node != x._node; }

    reference operator*() const { return _node->_data; }

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

    // 后置 ++
    Self &operator++() {
        _node = _node->_next;
        return *this;
    }
    // 前置 ++
    Self operator++(int) {
        Self tmp = *this;
        _node = _node->_next;
        return tmp;
    }

    // 后置 --
    Self &operator--() {
        _node = _node->_prev;
        return *this;
    }
    // 前置 --
    Self operator--(int) {
        Self tmp = *this;
        _node = _node->_prev;
        return tmp;
    }
};

template <class T>
class list {
public:
    typedef T value_type;
    typedef value_type *pointer;
    typedef const value_type *const_pointer;
    typedef value_type &reference;
    typedef const value_type &const_reference;
    typedef size_t size_type;
    typedef _List_node<T> Node;

    typedef _List_iterator<T, T &, T *> iterator;
    typedef _List_iterator<T, const T &, const T *> const_iterator;

private:
    // 只需要一个指针, 便可以表示整个双向循环链表
    Node *_node;  // 指向置于尾端的一个空白节点

public:
    // 默认构造函数, 配置并构造一个空白节点
    list() { _empty_initialize(); }
    // 填充构造函数, 先配置并构造一个空白节点
    // 再插入 n 个元素值为 val (如果提供) 的节点
    list(size_type n, const T &val = T()) {
        _empty_initialize();
        insert(begin(), n, val);
    }
    // 范围构造函数, 先配置并构造一个空白节点, 再构造一个与 range[first, last)
    // 元素数量相同的容器, 每个元素的值都为该范围中对应位置元素的值
    // 如果 InputIterator 是整数类型, 那么该构造函数需要避免和填充构造函数
    // list(static_cast<size_type>(first), static_cast<value_type>(last))
    // 的歧义 (first => n, last => val)
    // 具体见 insert 实现
    template <class InputIterator>
    list(InputIterator first, InputIterator last) {
        _empty_initialize();
        insert(begin(), first, last);
    }
    // 复制构造函数, 先配置并构造一个空白节点, 再利用 insert 复制
    list(const list<T> &x) {
        _empty_initialize();
        insert(begin(), x.begin(), x.end());
    }

private:
    void _empty_initialize() {
        _node = new Node();
        _node->_next = _node;
        _node->_prev = _node;
    }

public:
    // 析构函数
    ~list() {
        clear();
        delete _node;
        _node = nullptr;
    }

    // =运算符重载
    list<T> &operator=(const list<T> &x) {
        if (this != &x) {
            iterator first1 = begin();
            iterator last1 = end();
            const_iterator first2 = x.begin();
            const_iterator last2 = x.end();
            while (first1 != last1 && first2 != last2) {
                *first1++ = *first2++;
            }
            if (first2 == last2) {
                erase(first1, last1);
            } else {
                insert(last1, first2, last2);
            }
        }
        return *this;
    }

    // 填充重新赋值
    // 新内容是 n 个元素, 元素值均为 val
    void assign(size_type n, const T &val) { _fill_assign(n, val); }
    // 范围重新赋值
    // 新内容是 range[first, last) 中相同顺序的元素
    template <class InputIterator>
    void assign(InputIterator first, InputIterator last) {
        // 如果 InputIterator 是整数类型
        // 那么该重新赋值函数需要避免和填充重新赋值函数
        // assign(static_cast<size_type>(first),
        // static_cast<value_type>(last))
        // 的歧义 (first => n, last => val)
        typedef typename std::is_integral<InputIterator> Integral;
        _assign_dispatch(first, last, Integral());
    }

private:
    template <class Integer>
    void _assign_dispatch(Integer n, Integer val, std::true_type) {
        _fill_assign((size_type)n, (T)val);
    }

    template <class InputIterator>
    void _assign_dispatch(InputIterator first2, InputIterator last2,
                          std::false_type) {
        iterator first1 = begin();
        iterator last1 = end();
        for (; first1 != last1 && first2 != last2; ++first1, ++first2) {
            *first1 = *first2;
        }
        if (first2 == last2) {
            erase(first1, last1);
        } else {
            insert(last1, first2, last2);
        }
    }

    void _fill_assign(size_type n, const T &val) {
        iterator i = begin();
        for (; i != end() && n > 0; ++i, --n) {
            *i = val;
        }
        if (n > 0) {
            insert(end(), n, val);
        } else {
            erase(i, end());
        }
    }

public:
    // 返回第一个元素的引用
    reference front() { return *begin(); }
    const_reference front() const { return *begin(); }

    // 返回最后一个元素的引用
    reference back() { return *(--end()); }
    const_reference back() const { return *(--end()); }

    // 返回指向容器中第一个元素的迭代器
    iterator begin() { return _node->_next; }
    const_iterator begin() const { return _node->_next; }

    // 返回指向容器最后一个元素所在位置后一个位置的迭代器
    iterator end() { return _node; }
    const_iterator end() const { return _node; }

    // 判断容器是否为空
    bool empty() const { return _node->_next == _node; }

    // 返回实际元素个数
    size_type size() const {
        const_iterator first = begin();
        const_iterator last = end();
        size_type n = 0;
        while (first != last) {
            ++first;
            ++n;
        }
        return n;
    }

    // 返回可以容纳的最大元素个数
    size_type max_size() const { return size_type(-1); }

    // 移除所有元素(仅保留空白节点)
    void clear() {
        Node *cur = _node->_next;
        while (cur != _node) {
            Node *tmp = cur;
            cur = cur->_next;
            delete tmp;
        }
        _node->_next = _node;
        _node->_prev = _node;
    }

    // 在指定位置插入一个元素, 返回新节点位置(即插入位置)的迭代器
    iterator insert(iterator position, const T &val = T()) {
        assert(position >= begin() && position <= end());

        Node *tmp = new Node(val);
        tmp->_next = position._node;
        tmp->_prev = position._node->_prev;
        position._node->_prev->_next = tmp;
        position._node->_prev = tmp;
        return tmp;
    }
    // 填充插入
    // 在指定位置插入 n 个元素, 元素值均为 val
    void insert(iterator position, size_type n, const T &val) {
        _fill_insert(position, n, val);
    }
    // 范围插入
    // 在指定位置插入 range[first, last) 中相同顺序的元素
    template <class InputIterator>
    void insert(iterator position, InputIterator first, InputIterator last) {
        // 如果 InputIterator 是整数类型, 那么该插入函数需要避免和填充插入函数
        // insert(iterator position, static_cast<size_type>(first),
        // static_cast<value_type>(last))
        // 的歧义 (first => n, last => val)
        typedef typename std::is_integral<InputIterator> Integral;
        _insert_dispatch(position, first, last, Integral());
    }

private:
    template <class Integer>
    void _insert_dispatch(iterator position, Integer n, Integer x,
                          std::true_type) {
        _fill_insert(position, (size_type)n, (T)x);
    }

    template <class InputIterator>
    void _insert_dispatch(iterator position, InputIterator first,
                          InputIterator last, std::false_type) {
        assert(first <= last);

        for (; first != last; ++first) {
            insert(position, *first);
        }
    }

    void _fill_insert(iterator position, size_type n, const T &x) {
        while (n--) {
            insert(position, x);
        }
    }

public:
    // 移除一个元素, 移除后 position 位置的迭代器失效
    // 返回被删除节点的下一个节点的迭代器
    iterator erase(iterator position) {
        assert(position >= begin() && position < end());

        Node *next_node = position._node->_next;
        Node *prev_node = position._node->_prev;
        prev_node->_next = next_node;
        next_node->_prev = prev_node;
        delete position._node;
        return iterator(next_node);
    }
    // 移除一段元素, 移除后 [first, last) 范围内的迭代器失效
    // 返回被删除段的下一个节点的迭代器
    iterator erase(iterator first, iterator last) {
        assert(first <= last);

        while (first != last) {
            erase(first++);
        }
        return last;
    }

    // 将元素添加到容器末尾
    void push_back(const T &val = T()) { insert(end(), val); }

    // 将容器末尾的元素移除
    void pop_back() {
        iterator tmp = end();
        erase(--tmp);
    }
    // 将元素添加到容器起始
    void push_front(const T &val = T()) { insert(begin(), val); }

    // 将容器起始的元素移除
    void pop_front() { erase(begin()); }

    // 改变实际元素的个数
    // 如果 n 小于当前实际元素的个数, 则将内容缩减为其前 n 个元素
    // 如果 n 大于当前容实际元素的个数, 则通过在末尾插入足够多的元素来扩展内容
    // 以达到 n 的大小
    void resize(size_type new_size, const T &x = T()) {
        iterator i = begin();
        size_type len = 0;
        while (i != end() && len < new_size) {
            ++i;
            ++len;
        }
        if (len == new_size) {
            erase(i, end());
        } else {
            insert(end(), new_size - len, x);
        }
    }

    // 交换两个容器的所有元素
    void swap(list<T> &x) { std::swap(_node, x._node); }

private:
    // 将 [first, last) 范围内的元素迁移到 position 之前
    // 可以是不同的 list, 也可以是同一个 list
    void transfer(iterator position, iterator first, iterator last) {
        assert(position >= begin() && position <= end() && first <= last);

        if (position != last) {
            last._node->_prev->_next = position._node;
            first._node->_prev->_next = last._node;
            position._node->_prev->_next = first._node;

            Node *tmp = position._node->_prev;
            position._node->_prev = last._node->_prev;
            last._node->_prev = first._node->_prev;
            first._node->_prev = tmp;
        }
    }

public:
    // 升序合并两个升序 list (另一个 list 中的所有元素都会迁移到当前 list)
    void merge(list &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);
        }
    }
    // 根据 comp 比较函数对象合并两个有序 list
    // 另一个 list 中的所有元素都会迁移到当前 list
    template <class StrictWeakOrdering>
    void merge(list<T> &x, StrictWeakOrdering comp) {
        iterator first1 = begin();
        iterator last1 = end();
        iterator first2 = x.begin();
        iterator last2 = x.end();
        while (first1 != last1 && first2 != last2)
            if (comp(*first2, *first1)) {
                iterator next = first2;
                transfer(first1, first2, ++next);
                first2 = next;
            } else {
                ++first1;
            }
        if (first2 != last2) {
            transfer(last1, first2, last2);
        }
    }

    // 将另一个 list 的所有元素迁移到当前 list 的 position 前
    void splice(iterator position, list &x) {
        if (!x.empty()) {
            this->transfer(position, x.begin(), x.end());
        }
    }
    // 将另一个 list 中 i 位置的元素迁移到当前 list 的 position 前
    void splice(iterator position, list &, iterator i) {
        iterator j = i;
        ++j;
        if (position == i || position == j) {
            return;
        }
        this->transfer(position, i, j);
    }
    // 将另一个 list [first, last) 范围内的元素迁移到当前 list 的 position 前
    void splice(iterator position, list &, iterator first, iterator last) {
        if (first != last) {
            this->transfer(position, first, last);
        }
    }

    // 移除所有值为 val 的元素
    void remove(const T &val) {
        iterator first = begin();
        iterator last = end();
        while (first != last) {
            iterator next = first;
            ++next;
            if (*first == val) {
                erase(first);
            };
            first = next;
        }
    }
    // 移除所有满足 pred 条件函数对象的元素
    template <class Predicate>
    void remove_if(Predicate pred) {
        iterator first = begin();
        iterator last = end();
        while (first != last) {
            iterator next = first;
            ++next;
            if (pred(*first)) {
                erase(first);
            }
            first = next;
        }
    }

    // 将 list 中所有元素顺序反转
    void reverse() {
        Node *tmp = _node;
        do {
            std::swap(tmp->_next, tmp->_prev);
            tmp = tmp->_prev;
        } while (tmp != _node);
    }

    //  移除 list 中所有相邻重复元素, 只保留相同元素组的第一个元素
    void 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;
        }
    }
    // 移除 list 中所有满足 binary_pred 条件函数对象的相邻元素
    // 只保留满足条件元素组的第一个元素
    template <class BinaryPredicate>
    void unique(BinaryPredicate binary_pred) {
        iterator first = begin();
        iterator last = end();
        if (first == last) {
            return;
        }
        iterator next = first;
        while (++next != last) {
            if (binary_pred(*first, *next)) {
                erase(next);
            } else {
                first = next;
            }
            next = first;
        }
    }

    // 升序排序
    void sort() {
        if (_node->_next != _node && _node->_next->_next != _node) {
            list<T> carry;
            list<T> 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]);
        }
    }
    // 根据 comp 比较函数对象排序
    template <class StrictWeakOrdering>
    void sort(StrictWeakOrdering comp) {
        if (_node->_next != _node && _node->_next->_next != _node) {
            list<T> carry;
            list<T> 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, comp);
                    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], comp);
            }
            swap(counter[fill - 1]);
        }
    }
};

template <class T>
inline bool operator==(const list<T> &x, const list<T> &y) {
    typedef typename list<T>::const_iterator const_iterator;
    const_iterator end1 = x.end();
    const_iterator end2 = y.end();

    const_iterator i1 = x.begin();
    const_iterator i2 = y.begin();
    while (i1 != end1 && i2 != end2 && *i1 == *i2) {
        ++i1;
        ++i2;
    }
    return i1 == end1 && i2 == end2;
}

template <class T>
inline bool operator!=(const list<T> &x, const list<T> &y) {
    return !(x == y);
}

template <class T>
inline bool operator<(const list<T> &x, const list<T> &y) {
    return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
}

template <class T>
inline bool operator<=(const list<T> &x, const list<T> &y) {
    return !(y < x);
}

template <class T>
inline bool operator>(const list<T> &x, const list<T> &y) {
    return y < x;
}

template <class T>
inline bool operator>=(const list<T> &x, const list<T> &y) {
    return !(x < y);
}

template <class T>
inline void swap(list<T> &x, list<T> &y) {
    x.swap(y);
}
}  // namespace ximo

参考

SGI STL 源码
cppreference
C++ [STL之list模拟实现]
《STL源码剖析》by 侯捷