list

list的模拟实现

#pragma once
namespace chy
{
    //结点结构体
    template<class T>
    stuct list_node    
    {
        T _data;
        list_node<T>* _prev;
        list_node<T>* _next;
        //list_node的构造函数
        list_node(const T& x= T() )  //用T类型的匿名对象初始化
            :_data(x)                //T是什么类型就去调什么类型的构造函数
            ,_prev(nullptr)
            ,_next(nullptr)
        {}                            
    };

    //链表
    template<class T>
    class List
    {
        typedef list_node<T> Node;
    public:
        //构造函数
        List()
        {
            _head= new Node;
            _head->_next=_head;
            _head->_prev=_head;
        }
        //功能函数
        // ....
    private:
        Node* _head; 
    };
    
    //迭代器
    //{...}
}

迭代器的模拟实现

template class<T>
//迭代器像指针一样
struct list_iterator
{
    typedef list_node<T> Node;
    Node* _node;
    typedef list_iterator<T> iterator;
    iterator(Node* node)
        :_node(node)
    {}
    
    //实现迭代器功能
    // 遍历 
    //++it
    iterator operator++()
    {
        _node=_node->next;
        return *this;
    }
    //it ++
    iterator operator++(int) //无需传参 只是区分
    {
       iterator tmp(*this);//创建一个迭代器类型的tmp
        _node=_node->next;
        return tmp;
    }
    //--it 和 it-- 同理
    
    //解引用
    T& operator*()
    {
        return _node->_data;
    }
    // -> 返回指针类型 即返回结点的地址
    T* operator->()
    {
        return &(operator*());// _data是结构体的成员 他的地址就是结构体的地址
    }
}

->重载的意义

这里为了理解创建一个自定义类

struct pos
{
    int _row;
    int _column;
    pos(int row=0, int column=0)
        :_row(row)
        ,_column(column)
    {}
};

	void test_list2()
	{
		list<Pos> lt;
		lt.push_back(Pos(10, 20));
		lt.push_back(Pos(10, 21));

		list<Pos>::iterator it = lt.begin();
		while (it != lt.end())
		{
			//cout << (*it)._a1 << ":" << (*it)._a2 << endl; *it是pos结构体
			
            cout << it->_a1 << ":" << it->_a2 << endl;
			++it;
		}
		cout << endl;
	}

上述迭代器有权限放大问题。

l是被const修饰的，而l.begin()是可读可写的。这就需要实现一个const迭代器，而const迭代器的解引用操作符 ->操作符的重载仅是返回值不同：

T* operator->()?????????? ????? const T* operator->()

T& operator*()? ????????????????const T& operator*()? 二者仅返回值不同，不能构成函数重载。

	void Func(const list<int>& l)
	{
		list<int>::iterator it = l.begin();
		while (it != l.end())
		{
			//*it = 10;

			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

迭代器和const迭代器

使用实例化以区分

#pragma once
namespace chy
{
    //迭代器
	template<class T, class Ref, class Ptr>
	struct list_iterator
    {
		typedef list_node<T> Node;
		typedef list_iterator<T, Ref, Ptr> iterator;       
		Node* _node;

		list_iterator(Node* node)
			:_node(node)
		{}
    
        bool operator!=(const iterator& x)
        {
            return _node!=x._node;
        }
        bool operator==(const iterator& x)
        {
            return _node==x._node;
        }
    
    	Ref operator*()
		{
			return _node->_data;
		}

		//T* operator->() 
		Ptr operator->()
		{ 
			return &(operator*());
		}
    };  

    //链表
    template<class T>
    class List
    {
        //...
	public:
		typedef list_iterator<T, T&, T*> iterator;
		typedef list_iterator<T, const T&, const T*> const_iterator;
        //相当于 调用const_iterator时 Ref 就是 const T&
                                   //Ptr 就是 conts T*  
        iterator begin()
        {
            //iterator it=_head->next;
            //return it;
            return iterator(_head->next);//匿名对象
        }
        const_iterator begin() const
        {
            return const_iterator(_head->next);
        }
        iterator end()
        {
            return iterator(_head->prev);
        }
        const_iterator end() const
        {
            return const_iterator(_head->prev);
        }
    }; 
}

list的功能实现

析构拷贝构造插入删除

template<class T>	
class list
{
	typedef list_node<T> Node;
public:
	typedef __list_iterator<T, T&, T*> iterator;
	typedef __list_iterator<T, const T&, const T*> const_iterator;

    //无参构造如上 
    stack()
    {
        empty_init();
    }
    void empty_init()
    {
        _head=new Node;
        _head->next=_head;
        _head->prev=_head;
    }
    
    //构造
    template <class Inputiterator>
    stack(Inputiterator begin,Inputiterator end) //这里使用不了初始化列表 
    {                                            //但push会访问而造成报错
        empty_nit();//这个函数需要实现头结点的初始化
        while(begin!=end)
        {
            push(begin);
            begin++;
        }
    }

    //析构
    ~stack()
    {
        //这里复用clear()函数
        //但需要删除头结点
        clear();
        delete _head;
        _head=nullptr;
    }
    
    //清空
    void clear()
    {
        iterator it=begin();
        while(it!=end())
        {
            it=earse(it);//利用删除函数 返回删除位置的下一个位置的迭代器
        }
    }
    
    //拷贝构造 现代写法 需要迭代器支持的构造
    //lt2(lt1)
    list (const list<T>& lt)
    {
        empty_init();
        list<T> tmp=(lt.begin(),it.end())
        std::swap(tmp);
    }

    //赋值运算符重载
    list<T>& operator=(list<T> lt)
    {
        std::swap(lt);
        return *this;   
    }
    

    void push_back(const T& x)
    {
        Node* tail=_head->prev;
        Node* newnode=new Node(x);
        //head tail newnode
        tail->_next=newnode;
        newnode->_prev=tail;
        newnode->_next=_head;
        _head->_prev=newnode;
    }
    void push_front(const T& x)
    {
        insert(begin(),x);
    }
    iterator insert(iterator pos, const T& x)
    {
        Node* cur=pos._node;//pos是迭代器结构体 用.
        Node* prev=cur->_next;
        Node* newnode=new Node(x);
        //cur newnode prev
        cur->_next=newnode;
        newnode-_>prev=cur;
        newnode->_next=prev;
        prev->_prev=newnode;
        return iterator(newnode);
    }
    void pop_back()
    {
        earse(--end());
    }
    void pop_front()
    {
        earse(begin());
    }
    iterator erase(iterator pos)
    {
        assert(pos!=begin());//不删头节点
        Node*cur=pos._node;
        Node*prev=cur->_prev;
        Node*next=cur->_next;
        // prev cur next
        prev->_next=next;
        next->_prev=prev;
        delete cur;
        return iterator(next);
    }
private:
    Node* _head;
};