list类模拟实现¶

//节点结构
template<class T>
struct _list_node
{
    T data;// 数据类型
    _list_node* prev;// 前驱指针
    _list_node* next;// 后继指针

    //节点构造函数
    _list_node(const T& x = T())
        :data(x)
        ,prev(nullptr)
        ,next(nullptr)
    {}
};

//迭代器结构
template<class T>
struct _list_iterator
{
    typedef _list_node<T> Node;
    typedef _list_iterator<T> self;

    Node* _node;//迭代器节点
};

//迭代器构造函数
_list_iterator(Node* node)
    :_node(node)
{}

void test()
{
    sim_list::list<int>::iterator it = ls.begin();
    while (it != ls.end())
    {
        cout << *it << " ";
        ++it;
    }
}

//迭代器前置++运算符重载
self& operator++()
{
    _node = _node->next;
    return *this;
}

//迭代器*运算符重载
T& operator*()
{
    return _node->data;
}

//迭代器!=运算符重载
//注意end()返回值是个临时对象，具有常性，不能忘记const
bool operator!=(const self& cur)
{
    return _node != cur._node;
}

//迭代器前置--运算符重载
self& operator--()
{
    node = node->prev;
    return *this;
}

//迭代器后置--运算符重载
self operator--(int)
{
    Node* cur = node;
    node = node->prev;
    return cur;
}

struct test
{
    int num1;
    int num2;
};

void test_operatorTo()
{
    sim_list::list<struct test> ls;
    sim_list::list<struct test>::iterator it = ls.begin();
    //使用直接访问
    cout << (*it).num1 << " " << (*it).num2 << endl;

    //使用间接访问
    cout << it->num1 << " " << it->num2 << endl;
}

//迭代器->运算符重载
T* operator->()//返回对应类型的指针
{
    return &(node->data);//获取当前数据域的地址
}

cout << it.operator->()->num1 << " " << it.operator->()->num2 << endl;
//其中it.operator->()返回自定义类型变量的地址

template<class T>
struct _list_iterator_const 
{
    typedef _list_node<T> Node;
    typedef _list_iterator_const<T> self;

    Node* node;
};

//构造函数
//同非const版本一样，使用指针构造迭代器
_list_iterator_const(Node* node)
    :_node(node)
{}

//operator++()函数
self& operator++()
{
    _node = _node->next;
    return *this;
}

//operator*()函数
const T& operator*() const
{
    return _node->data;
}

//operator!=()函数
bool operator!=(const self& cur)
{
    return _node != cur._node;
}

//operator++(int)函数
self& operator++(int)
{
    Node* cur = _node;
    _node = _node->next;
    return cur;
}

self& operator--()
{
    _node = _node->prev;
    return *this;
}

//operator--(int)函数
self& operator--(int)
{
    Node* cur = _node;
    _node = _node->prev;
    return cur;
}

//operator==()函数
bool operator==(const self& cur)
{
    return _node = cur._node;
}

void test_const_iterator()
{
    sim_list::list<int> ls;
    ls.push_back(1);
    ls.push_back(2);
    ls.push_back(3);
    ls.push_back(4);
    ls.push_back(5);

    sim_list::list<int>::const_iterator cit = ls.begin();// 编译器无法自动识别const类型的迭代器


    while (cit != ls.end())
    {
        //*cit = 2;
        cout << *cit << " ";
        cit++;
    }
    cout << endl;
}

//迭代器结构——复合版本
template<class T, class Ref, class Ptr>
struct _list_iterator
{
    typedef _list_node<T> Node;
    typedef _list_iterator<T, Ref, Ptr> self;

    Node* _node;//迭代器节点

    //迭代器构造函数
    _list_iterator(Node* node)
        :_node(node)
    {}

    //迭代器前置++运算符重载
    self& operator++()
    {
        _node = _node->next;
        return *this;
    }

    //迭代器前置--运算符重载
    self& operator--()
    {
        _node = _node->prev;
        return *this;
    }

    //迭代器后置++运算符重载
    self operator++(int)
    {
        Node* cur = _node;
        _node = _node->next;
        return cur;
    }

    //迭代器后置--运算符重载
    self operator--(int)
    {
        Node* cur = _node;
        _node = _node->prev;
        return cur;
    }

    //迭代器*运算符重载
    Ref operator*()
    {
        return _node->data;
    }

    //迭代器->运算符重载
    Ptr operator->()
    {
        return &(_node->data);
    }

    //迭代器!=运算符重载
    bool operator!=(const self& cur)
    {
        return _node != cur._node;
    }

    //迭代器==运算符重载
    bool operator==(const self& cur)
    {
        return _node == cur._node;
    }
};

//头节点处理
void empty_init()
{
    _head = new Node;
    _head->prev = _head;
    _head->next = _head;

    _size = 0;
}

//构造函数
list()
{
    empty_init();
}

//析构函数
~list()
{
    clear();

    delete _head;
    _head = nullptr;
}

//拷贝构造函数
list(list<T>& ls)
{
    empty_init();

    for (auto num : ls)
    {
        push_back(num);
    }
}

//赋值运算符重载函数
list<T>& operator=(list<T>& ls)
{
    if (this != &ls)
    {
        for (auto num : ls)
        {
            push_back(num);
        }
    }

    return *this;
}

//begin()函数——非const版本
iterator begin()
{
    return _head->next;//隐式类型转换
}

//begin()函数——const版本
const_iterator begin() const
{
    return _head->next;
}

//end()函数——非const版本
iterator end()
{
    return _head;
}

//end()函数——const版本
const_iterator end() const
{
    return _head;
}

//insert()函数
iterator insert(iterator position, const T& val)
{
    //创建新的节点
    Node* node = new Node(val);
    //改变节点指针指向
    //记录当前position位置的节点
    Node* cur = position._node;
    //改变新节点的指向
    node->next = cur;
    node->prev = cur->prev;
    //改变当前位置节点的前一个节点的后继指针指向
    cur->prev->next = node;
    //改变当前位置节点的前驱指针指向
    cur->prev = node;

    ++_size;

    return position;
}

//push_back()函数
void push_back(const T& val)
{
    //创建新的节点
    Node* node = new Node(val);//调用节点结构构造函数
    //改变节点指针
    //先记录当前最后一个节点
    Node* tail = _head->prev;
    //改变头节点前驱指针为新节点
    _head->prev = node;
    //改变最后一个节点的后继指针指向新节点
    tail->next = node;
    //改变新节点的指针
    node->prev = tail;
    node->next = _head;

    ++_size;
}

//push_front()函数
void push_front(const T& val)
{
    //创建新节点
    Node* node = new Node(val);
    //改变指针指向
    //先记录当前第一个节点
    Node* first = _head->next;
    //改变新节点的指针指向
    node->next = first;
    node->prev = _head;
    //改变头指针后继指针指向
    _head->next = node;
    //改变原始第一个节点的前驱指针指向
    first->prev = node;

    ++_size;
}

//erase()函数
iterator erase(iterator position)
{
    //不可以删除头结点
    assert(position != iterator(_head));

    //记录要删除的节点的后一个节点
    Node* cur = position._node->next;
    //改变要删除的节点的前一个节点的后继指针
    position._node->prev->next = cur;
    //改变要删除的节点的后一个节点的前驱指针
    cur->prev = position._node->prev;

    //删除当前位置的指针
    delete position._node;

    --_size;

    return cur;
}

//pop_back()函数
void pop_back()
{
    erase(--end());
}

//pop_front()函数
void pop_front()
{
    //复用erase()函数
    erase(begin());
}

//clear()函数
void clear()
{
    iterator it = begin();
    while (it != end())
    {
        it = erase(it);
    }
}

//额外补充的函数——标准库中没有
//打印函数
void print_list(const list<int>& ls)
{
    sim_list::list<int>::const_iterator cit = ls.begin();
    while (cit != ls.end())
    {
        cout << *cit << " ";
        cit++;
    }
}

sim_list::list<string> ls;
ls.push_back("111111");
ls.push_back("111111");
ls.push_back("111111");
ls.push_back("111111");

//额外补充的函数——标准库中没有
//打印函数
template<class T>
void print_list(const list<T>& ls)
{
    sim_list::list<T>::const_iterator cit = ls.begin();
    while (cit != ls.end())
    {
        cout << *cit << " ";
        cit++;
    }
}

//额外补充的函数——标准库中没有
//打印函数
template<typename T>
void print_list(const list<T>& ls)
{
    //此处的typename不可以省略，此处的typename是为了告诉编译器这个需要等到模板参数被替换之后再去类中找的变量
    typename sim_list::list<T>::const_iterator cit = ls.begin();
    while (cit != ls.end())
    {
        cout << *cit << " ";
        cit++;
    }
}

//各种容器内容打印
template<typename container>
void print_container(const container& con)
{
    typename container::const_iterator it = con.begin();
    while (it != con.end())
    {
        cout << *it << " ";
        it++;
    }
    cout << endl;
}