在设计时，需要以下四个类：
1. List 类本身，它包含连接到链表两端的链、表的大小，以及一些方法。
2. Node 类，它是一个私有的内嵌类。一个节点包含数据和指向前后两个节点的两个指针，以及一些适当的构造函数。
3.const_iterator 类，它抽象了位置的概念，而且是一个共有的内嵌类，该const_iterator 存储一个指向“当前”节点的指针，并提供基本迭代器操作的实现，所有的操作，像=、==、！=、和++ 等，均以重载运算符的形式出现。
4、iterator 类、它抽象了位置的概念，而且是一个共有的内嵌类，该IT而按投入有着与const_iterator 相同的功能，但operator* 返回的是所指的引用，而不是对该项的常量引用。一个重要的问题是，IT而按投入可以用在任何需要const_iterator 的例程中，但反之不可以。
List.h
#pragma once #include <iostream> namespace myspace1 { template<typename Object> class List { private: struct Node { Object data; Node *prev; Node *next; Node(const Object & d = Object(), Node *p = nullptr, Node *n = nullptr) :data(d), prev(p), next(n) { } Node(Object &&d, Node *p = nullptr, Node *n = nullptr) : data(std::move(d)), prev(p), next(n) { } }; public: class const_iterator { public: const_iterator() :current(nullptr) {} const Object & operator * () const { return retrieve(); } const_iterator &operator ++() { current = current->next; return *this; } const_iterator operator++(int ) { const_iterator old = *this; ++(*this); return old; } protected: Node *current; Object & retrieve() const { return current->data; } const_iterator(Node *p) : current(p) {} friend class List<Object>; }; class iterator : public const_iterator { public: iterator() {} Object & operator*() { return const_iterator::retrieve(); } const Object & operator* () const { return const_iterator::operator*(); } iterator & operator++() { this->current = this->current->next; return *this; } iterator operator++(int) { iterator old = *this; ++(*this); return old; } protected: iterator(Node *p) :const_iterator(p) {} friend class List<Object>; }; public: List(); List(const List & rhs); ~List(); List<Object> & operator =(const List & rhs); List(List && rhs); List<Object> & operator =(List && rhs); iterator begin() { return head->next; } const_iterator begin() const { return head->next; } iterator end() { return tail; } const_iterator end() const { return tail; } int size() const { return the size; } bool empty() const { return size() == 0; } void clear() { while (!empty()) pop_front(); } Object & front() { return *begin(); } const Object &front() const { return *begin(); } Object & back() { return *--end(); } const Object &back() const { return *--end(); } void push_front(const Object &x) { insert(begin(), x); } void push_front(Object &&x) { insert(begin(), std::move(x)); } void push_back(const Object &x) { insert(end(), x); } void push_back(Object &&x) { insert(end(), std::move(x)); } void pop_front() { erase(begin()); } void pop_back() { erase(--end()); } iterator insert(iterator itr, const Object &x) { Node *p = itr.current; theSize++; return p->prev = p->prev->next = new Node(x, p->prev, p); } iterator insert(iterator itr, Object &&x) { Node *p = itr.current; theSize++; return p->prev = p->prev->next = Node(std::move(x), p->prev, p); } iterator erase(iterator itr) { Node *p = itr.current; iterator retVal(p->next); p->prev->next = p->next; p->next->prev = p->prev; delete p; theSize--; return retVal; } iterator erase(iterator from, iterator to) { for (iterator itr = from; itr != to;) itr = erase(itr); return to; } private: int theSize; Node *head; Node *tail; void init() { theSize = 0; head = new Node; tail = new Node; head->next = tail; tail->prev = head; } }; }
List.cpp #include "List.h" using namespace myspace1; template<typename Object> List<Object>::List() { init(); } template<typename Object> List<Object>::List(const List & rhs) { init(); for (auto &x : rhs) push_back(x); } template<typename Object> List<Object>::~List() { clear(); delete head; delete tail; } template<typename Object> List<Object> & List<Object>::operator=(const List & rhs) { List copy = rhs; std::swap(*this, copy); return *this; } template<typename Object> List<Object>::List(List && rhs) :theSize(rhs.theSize), head(rhs.head), tail(rhs.tail) { rhs.theSize = 0; rhs.head = nullptr; rhs.taill = nullptr; } template<typename Object> List<Object> & List<Object>::operator = (List && rhs) { std::swap(theSize, rhs.theSize); std::swap(head, rhs.head); std::swap(tail, rhs.tail); return *this; }
