自己实现list与迭代器

一、list实现代码

包括push_back、push_front、pop_back、pop_front函数，迭代器获取函数begin()、cbegin()、end()、cend()

迭代器：const_iterator、iterator。

迭代器函数：前缀++、后缀++、*、->、==、！=

如果你想理解操作符重载、标准库实现、链表数据结构、迭代器实现，请看下去^_^。

#include

#include

using namespace std;

 

#ifndef NULL

#define NULL 0

#endif

 

template <typename T>

class mylist

{

public:

    mylist():p_head(new Node()){}

    ~mylist()

    {

        clear();

        delete p_head;

        p_head = NULL;

    }

   

    void push_back(const T& value)

    {

        Node* tp_node = new Node(value);

        Node* cur_node = p_head;

        while(cur_node->next)

            cur_node = cur_node->next;

        Node& last_node = *cur_node;

        last_node.next = tp_node;

    }

    void pop_back()

    {

        if(p_head->next == NULL)return;

        Node* cur_node = p_head;

        while(cur_node->next->next!=NULL)

            cur_node = cur_node->next;

        delete cur_node->next;

        cur_node->next = NULL;

    }

    void push_front(const T& value)

    {

        Node* tp_node = new Node(value);

        tp_node->next = p_head->next;

        p_head->next = tp_node;

    }

    void pop_front()

    {

        Node* rm_node = p_head->next;

        p_head->next = rm_node->next;

        delete rm_node;

        rm_node = NULL;

    }

    void clear()

    {

        while(p_head->next!=NULL)

            pop_front();

    }

   

    struct Node{

        T m_value;

        Node* next;

        Node(T value = T()):m_value(value),next(NULL){}

    };

    class iterator{

    public:

        iterator(Node* p_node = NULL):cur_node(p_node){}

        T* operator->(){return &(cur_node->m_value);}

        T& operator*(){return cur_node->m_value;}

        //前缀++

        T& operator++(){cur_node=cur_node->next;return operator*();}

        //后缀++

        T operator++(int){Node* ret_node = cur_node;cur_node = cur_node->next;return ret_node->m_value;}

        bool operator==(const iterator& r_value){return cur_node==r_value.cur_node;}

        bool operator!=(const iterator& r_value){return !operator==(r_value);}

    private:

        Node* cur_node;

    };

    class const_iterator{

    public:

        //覆盖，只是对iterator的函数封装，这样的目的是，操作改变,只需要修改一个地方

        const_iterator(Node* p_node = NULL):m_iterator(p_node){}

        const T* operator->(){return m_iterator.operator->();}

        const T& operator*(){return m_iterator.operator*();}

        const T*& operator++(){return m_iterator.operator++();}

        const T operator++(int){return m_iterator.operator++(0);}

        bool operator==(const const_iterator& r_value){return m_iterator==r_value.m_iterator;}

        bool operator!=(const const_iterator& r_value){return m_iterator!=r_value.m_iterator;}

    private:

        iterator m_iterator;

    }; 

    iterator begin(){return iterator(p_head->next);}

    iterator end(){return iterator(NULL);}

    const_iterator cbegin(){return const_iterator(p_head->next);}

    const_iterator cend(){return const_iterator(NULL);}

private:

    Node* p_head;

    //禁用复制构造函数 赋值函数

    mylist(const mylist&){}

    void operator=(const mylist&){}

};

 

二、测试部分

struct Student{

    char m_name[20];

    int m_id;

    Student(){}

    Student(const char name[],int id):m_id(id)

    {

        strcpy(m_name,name);

    }

};

 

//测试函数

void Show(mylist<Student>& ilist)

{

    cout << "----Show----" << endl;

    mylist<Student>::iterator begin = ilist.begin();

    while(begin != ilist.end())

    {

        cout << begin->m_name << ':' << (*begin).m_id << endl;

        ++begin;

    }

    cout << endl;

}

void ConstShow(mylist<Student>& ilist)

{

    cout << "----ConstShow----" << endl;

    mylist<Student>::const_iterator cbegin = ilist.cbegin();

    while(cbegin != ilist.cend())

    {

        cout << cbegin->m_name << ':' << (*cbegin).m_id << endl;

        cbegin++;

    }

    cout << endl;

}

 

int main()

{

   

    mylist<Student> ilist;

    ilist.push_back( Student("Curry",1) );

    ilist.push_back( Student("jams",2) );

    ilist.push_back( Student("kobe",3) );

    ilist.push_back( Student("rose",4) );

   

    Show(ilist);

    ilist.pop_front();

    ConstShow(ilist);

    ilist.pop_back();

    Show(ilist);

    ilist.push_front(Student("Curry",0));

    ConstShow(ilist);

       

    return 0;

}

 

三、测试结果

----Show----

Curry:1

jams:2

kobe:3

rose:4

 

----ConstShow----

jams:2

kobe:3

rose:4

 

----Show----

jams:2

kobe:3

 

----ConstShow----

Curry:0

jams:2

kobe:3