双向链表的类模板的实现

全部代码加详细注释
List.hpp写法1----将迭代器类，节点类和链表类分开写，变量不统一，书写较麻烦

/***************Node结点的定义************/
template<class T>
struct Node
{
    T data;
    Node<T>* prev, * next;
    Node(T d = 0, Node<T>* p = NULL, Node<T>* n = NULL) :data(d), prev(p), next(n) {}
};

/***************迭代器的定义************/
//类做友元，要声明
template<class T> class List;

template<class T>
class const_iterator
{
protected:
    Node<T>* current;
    T& retrive()const { return current->data; }//常函数不能更改成员变量的值，这里不能更改指针指向，但是可以更改指针指向地址上存储的值
    //转换构造---让当前迭代器的成员变量current指向p位置，间接相当于迭代器可以操作当前位置
    const_iterator(Node<T>* p) :current(p) {}
    friend class List<T>;
public:
    //默认迭代器指向内容为空
    const_iterator() :current(NULL) {}
    //const迭代器解引用得到的值不能进行修改，这里是常迭代器
    //这里前置const规定了返回值不能修改，这里返回的值是指针指向的地址的值，因此这里不能修改指针的指向和指向的值
    const T& operator*()const { return retrive(); }
    //前置++
    const_iterator& operator++()
    {
        current = current->next;
        return *this;
    }
    //后置++
    const_iterator operator++(int)
    {
        //保留旧值
        const_iterator old = *this;
        //新值后移
        ++(*this);
        return old;
    }
    //前置--
    const_iterator& operator--()
    {
        current = current->prev;
        return *this;
    }
    //后置--
    const_iterator operator--(int)
    {
        //保留旧值
        const_iterator old = *this;
        //新值前移
        --(*this);
        return old;
    }
    //==
    bool operator==(const const_iterator& rhs)const
    {
        return current == rhs.current;
    }
    //!=
    bool operator!=(const const_iterator& rhs)const
    {
        return current != rhs.current;
    }
};

//List类模板做友元函数要在前面添加类模板声明
template<class T> class List;

template<class T>
class iterator : public const_iterator<T>
{
protected:
    //转换构造---让当前迭代器的成员变量current指向p位置，间接相当于迭代器可以操作当前位置
    iterator(Node<T>* p) :const_iterator<T>(p) {}
    friend class List<T>;
public:
    iterator() {};
    //用普通迭代器可以修改当前迭代器指向位置的值
    T& operator*()
    {
        return const_iterator<T>::retrive();
    }
    //常对象调用----前置const不能作为重载条件，后置const可以
    const T& operator*()const
    {
        return const_iterator<T>::operator*();
    }
    //************************************************************************
    //前++
    iterator& operator++()
    {
        const_iterator<T>::current = const_iterator<T>::current->next;
        return *this;
    }
    //后置++
    iterator operator++(int)
    {
        //保留旧值
        iterator old = (*this);
        //新值后移
        ++(*this);
        return old;
    }
    //前置--
    iterator& operator--()
    {
        const_iterator<T>::current = const_iterator<T>::current->prev;
        return *this;
    }
    //后置--
    iterator operator--(int)
    {
        //保留旧值
        iterator old = *this;
        --(*this);
        return old;
    }
    //*******************************************************************
};

/***************链表类模板的定义************/
template<class T>
class List//有头链表
{
private:
    Node<T>* head;// 头节点指针
    Node<T>* tail;//尾节点指针
    int size;//节点个数
    //初始化函数
    void init()
    {
        head = new Node<T>;//自动调用Node类的默认构造函数
        tail = new Node<T>;
        size = 0;
        //头和尾都需要创建一个节点，用来维护指针域，而不是数据域
        head->next = tail;
        tail->prev = head;
    }
public:
    //默认构造函数
    List() { init(); }
    //复制构造函数
    List(const List<T>& l)
    {
        //先初始化
        init();
        //再调用赋值运算符重载
        operator=(l);
    }
    //赋值运算符重载
    const List& operator=(const List& L);
    //迭代器中的转换构造是在begin和end函数里面使用的
    //开始迭代器---返回的迭代器已经可以间接操作head->next即第一个有效节点的位置

    //注意这里返回的都是临时匿名迭代器对象
    iterator<T> Begin() { return iterator<T>(head->next); }
    const_iterator<T> Begin()const { return const_iterator<T>(head->next); }
    //结束迭代器---返回的迭代器已经可以间接操作tail即最后一个有效节点的后一个位置
    iterator<T> End() { return iterator<T>(tail); }
    const_iterator<T> End()const { return const_iterator<T>(tail); }
    //返回首元素引用---我们在迭代器的函数里面重载了*，因此解引用迭代器返回的是当前迭代器的current指针指向的data数据域
    T& front() { return *Begin(); }
    const T& front() const { return *Begin(); }
    //返回尾元素引用---我们在迭代器的函数里面重载了*，因此解引用迭代器返回的是当前迭代器的current指针指向的data数据域
    //但注意返回的应该是end迭代器前一个，即最后一个位置的有效元素
    //这里迭代器重载了--运算符，因此迭代器--,就等于current指针前移
    T& back() { return *(--End()); }
    const T& back()const { return *(--End()); }
    //头插---begin迭代器指向的是第一个有效位置，因此这里插入到第一个有效元素前
    void push_front(const T& item)
    {
        Insert(Begin(), item);
    }
    //尾插函数---end迭代器指向最后一个有效元素后面一个位置，因此这里插入end迭代器之前，相当于插入的新元素成为了最后一个有效的元素
    void push_back(const T& item)
    {
        Insert(End(), item);
    }
    //删除首节点---删除begin迭代器指向的第一个有效节点
    void pop_front()
    {
        Erase(Begin());
    }
    //删除尾节点--删除end迭代器前面一个节点，因此end迭代器指向最后一个有效元素后面一个位置
    void pop_back()
    {
        Erase(--End());//这里--end相当于current指针前移一位
    }
    //删除指定位置的函数
    iterator<T> Erase(iterator<T> itr);
    //插入节点的函数
    iterator<T> Insert(iterator<T> itr, const T& item);
    //获取节点个数
    int Size()const { return size; }
    //判空函数
    bool empty()const { return size == 0; }
    //清空----如果不为空，就一直进行头删操作
    void clear() { while (!empty()) { pop_front(); } }
};
//插入节点的函数---插入指定迭代器位置之前
template<class T>
iterator<T> List<T>::Insert(iterator<T> itr, const T& item)
{
    //这里需要用p指向当前迭代器的current指针
    Node<T>* p = itr.current;
    p->prev->next = new Node<T>(item, p->prev, p);
    p->prev = p->prev->next;
    size++;
    //插入到当前节点之前---返回已经指向当前新插入值位置的迭代器
    return iterator<T>(p->prev);
}

//删除指定位置的函数--返回删除当前迭代器的下一个位置
template<class T>
iterator<T> List<T>::Erase(iterator<T> itr)
{
    //p用来临时保存，方便一会delete
    Node<T>* p = itr.current;
    iterator<T> re(p->next);//当前迭代器的下一个位置的迭代器
    p->prev->next = p->next;
    p->next->prev = p->prev;
    delete p;
    size--;
    return re;
}

//赋值运算符重载
template<class T>
const List<T>& List<T>::operator=(const List<T>& L)
{
    //清表
    clear();
    //逐个节点进行复制操作
    for (const_iterator<T> itr = L.Begin(); itr != L.End(); ++itr)
    {
        push_back(*itr);
    }
    return *this;
}

List.hpp第二种写法—迭代器类和节点类都嵌套到list类中，模板变量参数统一化，便于书写

#pragma once
#include<cstdlib>
#include<iostream>
using namespace std;
/***************链表类模板的定义************/
template<class T>
class List//有头链表
{
private:
    struct Node
    {
        T data;
        Node* prev, * next;
        Node(T d = 0, Node* p = NULL, Node* n = NULL) :data(d), prev(p), next(n) {}
    };
    Node* head;// 头节点指针
    Node* tail;//尾节点指针
    int size;//节点个数
    //初始化函数
    void init()
    {
        head = new Node;
        tail = new Node;
        size = 0;
        //头和尾都需要创建一个节点，用来维护指针域，而不是数据域
        head->next = tail;
        tail->prev = head;
    }
public:

    class const_iterator
    {
    protected:
        Node* current;
        T& retrive()const { return current->data; }
        //转换构造---让当前迭代器的成员变量current指向p位置，间接相当于迭代器可以操作当前位置
        explicit const_iterator(Node* p) :current(p) {}
        friend class List<T>;
    public:
        //默认迭代器指向内容为空
        explicit const_iterator() :current(NULL) {}
        //const迭代器解引用得到的值不能进行修改，这里是常迭代器
     const T& operator*()const { return retrive(); }
        //前置++
        const_iterator& operator++()
        {
            current = current->next;
            return *this;
        }
        //后置++
        const_iterator operator++(int)
        {
            //保留旧值
            const_iterator old = *this;
            //新值后移
            ++(*this);
            return old;
        }
        //前置--
        const_iterator& operator--()
        {
            current = current->prev;
            return *this;
        }
        //后置--
        const_iterator operator--(int)
        {
            //保留旧值
            const_iterator old = *this;
            //新值前移
            --(*this);
            return old;
        }
        //==
        bool operator==(const const_iterator& rhs)const
        {
            return current == rhs.current;
        }
        //!=
        bool operator!=(const const_iterator& rhs)const
        {
            return current != rhs.current;
        }
    };

    class iterator : public const_iterator
    {
    protected:
        //转换构造---让当前迭代器的成员变量current指向p位置，间接相当于迭代器可以操作当前位置
        explicit  iterator(Node* p) :const_iterator(p) {}
        friend class List<T>;
    public:
        explicit iterator() {};
        //用普通迭代器可以修改当前迭代器指向位置的值
        T& operator*()
        {
            return  const_iterator::retrive();
        }
        //常对象调用----前置const不能作为重载条件，后置const可以
        const T& operator*()const
        {
            return const_iterator::operator*();
        }
        //前++
            iterator& operator++()
            {
                const_iterator::current = const_iterator::current->next;
                return *this;
            }
           // 后置++
            iterator operator++(int)
            {
                //保留旧值
                iterator old = (*this);
                //新值后移
                ++(*this);
                return old;
            }
         //   前置--
            iterator& operator--()
            {
                const_iterator::current = const_iterator::current->prev;
                return *this;
            }
           // 后置--
            iterator operator--(int)
            {
                //保留旧值
                iterator old = *this;
                --(*this);
                return old;
            }

        //*******************************************************************
    };



    //默认构造函数
    List() { init(); }
    //复制构造函数
    List(const List<T>& l)
    {
        //先初始化
        init();
        //再调用赋值运算符重载
        operator=(l);
    }
    //赋值运算符重载
    const List& operator=(const List& L);
    //迭代器中的转换构造是在begin和end函数里面使用的
    //开始迭代器---返回的迭代器已经可以间接操作head->next即第一个有效节点的位置

    //注意这里返回的都是临时匿名迭代器对象
    iterator Begin() { return iterator(head->next); }
    const_iterator Begin()const { return const_iterator(head->next); }
    //结束迭代器---返回的迭代器已经可以间接操作tail即最后一个有效节点的后一个位置
     iterator End() { return iterator(tail); }
   const_iterator End()const { return const_iterator(tail); }
    //返回首元素引用---我们在迭代器的函数里面重载了*，因此解引用迭代器返回的是当前迭代器的current指针指向的data数据域
    T& front() { return *Begin(); }
    const T& front() const { return *Begin(); }
    //返回尾元素引用---我们在迭代器的函数里面重载了*，因此解引用迭代器返回的是当前迭代器的current指针指向的data数据域
    //但注意返回的应该是end迭代器前一个，即最后一个位置的有效元素
    //这里迭代器重载了--运算符，因此迭代器--,就等于current指针前移
    T& back() { return *(--End()); }
    const T& back()const { return *(--End()); }
    //头插---begin迭代器指向的是第一个有效位置，因此这里插入到第一个有效元素前
    void push_front(const T& item)
    {
        Insert(Begin(), item);
    }
    //尾插函数---end迭代器指向最后一个有效元素后面一个位置，因此这里插入end迭代器之前，相当于插入的新元素成为了最后一个有效的元素
    void push_back(const T& item)
    {
        Insert(End(), item);
    }
    //删除首节点---删除begin迭代器指向的第一个有效节点
    void pop_front()
    {
        Erase(Begin());
    }
    //删除尾节点--删除end迭代器前面一个节点，因此end迭代器指向最后一个有效元素后面一个位置
    void pop_back()
    {
        Erase(--End());//这里--end相当于current指针前移一位
    }
    //删除指定位置的函数
    iterator Erase(iterator itr);
    //插入节点的函数
    iterator Insert(iterator itr, const T& item);
    //获取节点个数
    int Size()const { return size; }
    //判空函数
    bool empty()const { return size == 0; }
    //清空----如果不为空，就一直进行头删操作
    void clear() { while (!empty()) { pop_front(); } }
};

//插入节点的函数---插入指定迭代器位置之前
template<class T>
typename List<T>::iterator List<T>::Insert(iterator itr, const T& item)
{
    //这里需要用p指向当前迭代器的current指针
    Node* p = itr.current;
    p->prev->next = new Node(item, p->prev, p);
    p->prev = p->prev->next;
    size++;
    //插入到当前节点之前---返回已经指向当前新插入值位置的迭代器
    return iterator(p->prev);
}

//删除指定位置的函数--返回删除当前迭代器的下一个位置
template<class T>
typename List<T>::iterator List<T>::Erase(iterator itr)
{
    //p用来临时保存，方便一会delete
    Node* p = itr.current;
    iterator re(p->next);//当前迭代器的下一个位置的迭代器
    p->prev->next = p->next;
    p->next->prev = p->prev;
    delete p;
    size--;
    return re;
}

//赋值运算符重载
template<class T>
const List<T>& List<T>::operator=(const List<T>& L)
{
    //清表
    clear();
    //逐个节点进行复制操作
    for (const_iterator itr = L.Begin(); itr != L.End(); ++itr)
    {
        push_back(*itr);
    }
    return *this;
}

main.cpp

#include <iostream>
#include"List.hpp"		//用户头文件
using namespace std;

template<class Iterator>	//在指定范围内输出元素
void display(Iterator first, Iterator last)
{
	for (; first != last; ++first)
		cout << *first << ' ';
	cout << endl;
}
//交换两个节点的值
template<class Iterator,class T>
void swap(Iterator L1, Iterator L2,T temp)
{
	temp = *L1;
	*L1 = *L2;
	*L2 = temp;
}
//选择排序
template<class Iterator>
void select_sort(Iterator first, Iterator last)
{
	Iterator i, j, min;
	for (i = first; i != last; ++i)
	{
		min = i;
		//注意这里不能直接写j=i+1---->因为iterator我们没有重载+运算符
		for (j =i,++j; j != last; ++j)
		{
			if ((*j) < (*min))//解引用迭代器得到的就是当前迭代器的指针域指向的data
				min = j;
		}
		//交换节点存储的data值，而非改变指针指向，完成交换
		if (i != min)
		{
			swap(i, min, *i);
		}
		//错误写法---因此temp=i,相当于temp的current指针和i的current指针指向同一块内存,当这块内存的值发生变化的时候，temp的指针指向的内容随之改变
		//我们要的是用temp来保留一份i的current指向的data数据域的值
		//if (i != min)
		//{
		//	Iterator temp = i;
		//	*i = *min;
		//	*min = *temp;
		//}
	}
}
int main()
{
	List<int> L;
	for (int i = 0; i < 10; i++)
	{
		L.Insert(L.Begin(), i + 100);
	}
	display(L.Begin(), L.End());
	L.Erase(L.Begin());
	display(L.Begin(), L.End());
	List<int> L2;
	L2 = L;
	display(L2.Begin(), L2.End());
	for (int i = 0; i < 20; i++)
	{
		L2.Insert(L2.Begin(), i * 2);
	}
	display(L2.Begin(), L2.End());
	L.Erase(L2.Begin());
	display(L2.Begin(), L2.End());

	const List<int> L3(L2);
	display(L2.Begin(), L2.End());

	cout << "未排序前: " << endl;
	List<int> L5;
	L5.push_back(2);
	L5.push_back(5);
	L5.push_back(3);
	L5.push_back(6);
	L5.push_back(8);
	L5.push_back(10);
	display(L5.Begin(), L5.End());
	cout << "选择排序后:" << endl;
	select_sort(L5.Begin(), L5.End());
	display(L5.Begin(), L5.End());
	List<int> L6 = L5;
	cout << "L6= " << endl;
	display(L6.Begin(), L6.End());
	return 0;
}

总结:

• 如果类型是依赖于模板参数的限定名，那么在它之前必须加typename(除非是基类列表，或者在类的初始化成员列表中)
• 上面部分讲解有误，详细typename用法详情，可以参考下面这篇大佬写的文章
  typename详细用法