目录

节点

迭代器

整体框架

构造函数

empty_init

拷贝构造

赋值重载

析构函数

clear

insert

erase

push_back和push_front

pop_back和push_front

size

empty

Print_Container

节点

对于链表节点，我们需要一个数据、一个前驱指针、一个后继指针来维护，并且将其封装成一个类。

<code>template<class T>

struct list_node

{

T _data;

list_node<T>* _next;

list_node<T>* _prev;

list_node(const T& data = T())

:_data(data)

,_next(nullptr)

,_prev(nullptr)

{}

};

使用struct的原因是因为，struct默认的域作用限定符是public，方便后续使用，不用走友元的那一套。

迭代器

我们知道迭代器提供访问容器的方法，之前实现vector和string时，迭代器用的就是数据类型的指针，但是list不可以直接用。因为vector和string的数据在内存的存放都是连续的，如果想找下一个数据的指针（迭代器），直接（迭代器）指针++就可以了；但是list的数据存放在内存不是连续的，如果直接把指针当成迭代器，迭代器++是找不到下一个数据的迭代器。

所以综上所述，我们应该用类对链表数据类型的指针封装成迭代器，在类里重载操作符让其达到我们想要的效果。

当然，我们实现的迭代器应该有两个版本，普通版本和const版本。

//普通迭代器

template<class T>

struct list_iterator

{

typedef list_node<T> Node;

typedef list_iterator<T> Self;

Node* _node;

list_iterator(Node* node)

:_node(node)

{}

T& operator*()

{

return _node->_data;

}

T* operator->()

{

return &_node->_data;

}

//前置++

Self& operator++()

{

_node = _node->_next;

return *this;

}

//后置++

Self operator++(int)

{

Self tmp(*this);

_node = _node->_next;

return tmp;

}

//前置--

Self& operator--()

{

_node = _node->_prev;

return *this;

}

//后置--

Self operator--(int)

{

Self tmp(*this);

_node = _node->_prev;

return tmp;

}

bool operator!=(const Self& it) const

{

return _node != it._node;

}

bool operator==(const Self& it) const

{

return _node == it._node;

}

};

​//const迭代器

template<class T>

struct list_const_iterator

{

typedef list_node<T> Node;

typedef list_const_iterator<T> Self;

Node* _node;

list_const_iterator(Node* node)

:_node(node)

{}

const T& operator*()

{

return _node->_data;

}

const T* operator->()

{

return &_node->_data;

}

Self& operator++()

{

_node = _node->_next;

return *this;

}

Self operator++(int)

{

Self tmp(*this);

_node = _node->_next;

return tmp;

}

Self& operator--()

{

_node = _node->_prev;

return *this;

}

bool operator!=(const Self& it) const

{

return _node != it._node;

}

bool operator==(const Self& it) const

{

return _node == it._node;

}

};

​

我们发现这两份代码，除了重载*和->有所不同，其余代码都是一样的，所以我们可以增加两个模板参数，将这两份代码合二为一。

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)

{}

Ref operator*()

{

return _node->_data;

}

Ptr operator->()

{

return &_node->_data;

}

Self& operator++() //前置++

{

_node = _node->_next;

return *this;

}

Self operator++(int) //

{

Self tmp(*this);

_node = _node->_next;

return tmp;

}

Self& operator--()

{

_node = _node->_prev;

return *this;

}

Self operator--(int)

{

Self tmp(*this);

_node = _node->_prev;

return tmp;

}

bool operator!=(const Self& it) const

{

return _node != it._node;

}

bool operator==(const Self& it) const

{

return _node == it._node;

}

};

 增加Ref和Ptr模板参数，让T*和T&作为参数传入，这就可以解决将两份代码合二为一。

整体框架

​

​

template<class T>

class list

{

typedef list_node<T> Node;

public:

/*typedef list_iterator<T> iterator;

typedef list_const_iterator<T> const_iterator;*/

//将T&和T*作为参数传入

typedef list_iterator<T, T&, T*> iterator;

typedef list_iterator<T, const T&, const T*> const_iterator;

iterator begin()

{

/*iterator it(_head->_next);

return it;*/

//return iterator(_head->_next);

//返回哨兵节点的下一个节点（第一个有效节点）

//隐式类型转换

return _head->_next;

}

iterator end()

{

//最后一个有效节点的下一位置，也就是哨兵节点

return _head;

}

const_iterator begin() const

{

return _head->_next;

}

const_iterator end() const

{

return _head;

}

//实现各种函数......

private:

Node* _head;

size_t _size;

};

​

​

构造函数

empty_init

多种构造函数的代码都有重合，所以把重合部分独立成一个函数。

​

void empty_init()

{

//创造哨兵节点

_head = new Node();

_head->_next = _head;

_head->_prev = _head;

_size = 0;

}

​

普通构造

普通构造就是创造哨兵节点，调用empty_init即可。

//普通构造

list()

{

empty_init();

}

列表构造

C++11的用法，用法例子如下：

list<int> lt1 = { 1,2,3,4,5,6 };

 先创造一个哨兵节点，然后将列表的元素尾插即可。

//列表构造

list(initializer_list<T> il)

{

empty_init();

for (auto& e : il)

{

push_back(e);

}

}

关于列表initializer_list<T>的知识，可以看以下连接。

介绍列表

拷贝构造

创建哨兵节点，将链表元素尾插到待构造的链表就完成拷贝构造了。

//拷贝构造

list(const list<T>& lt)

{

empty_init();

for (auto& e : lt)

{

push_back(e);

}

}

赋值重载

与临时对象lt交换即可，跟string、vector的实现类似。

void swap(list<T>& lt)

{

std::swap(_head, lt._head);

std::swap(_size, lt._size);

}

list<T>& operator=(list<T> lt)

{

swap(lt);

return *this;

}

析构函数

clear

清理除了哨兵节点以外的所有节点。

void clear()

{

auto it = begin();

while (it != end())

{

it = erase(it);

}

}

先将链表clear掉，然后清理哨兵节点。  

~list()

{

clear();

delete _head;

_head = nullptr;

}

insert

在pos（迭代器）位置前插入元素x，插入后_size++，返回新插入元素的迭代器。

iterator insert(iterator pos, const T& x)

{

Node* cur = pos._node; //pos是iterator类的对象，访问里面的成员变量用pos._node，不能用pos->_node

Node* prev = cur->_prev;

Node* newnode = new Node(x);

newnode->_next = cur;

cur->_prev = newnode;

newnode->_prev = prev;

prev->_next = newnode;

++_size;

//隐式类型转换

return newnode;

}

erase

删除pos位置的元素，删除后_size--，返回删除元素的下一元素的迭代器。

iterator erase(iterator pos)

{

assert(pos != end()); //不能删掉哨兵位的节点

Node* prev = pos._node->_prev;

Node* next = pos._node->_next;

prev->_next = next;

next->_prev = prev;

delete pos._node;

--_size;

return next;

}

push_back和push_front

利用insert函数就可以实现尾插和头插。

void push_back(const T& x)

{

/*Node* newnode = new Node(x);

Node* tail = _head->_prev;

tail->_next = newnode;

newnode->_prev = tail;

newnode->_next = _head;

_head->_prev = newnode;

++_size;*/

insert(end(), x);

}

void push_front(const T& x)

{

insert(begin(), x);

}

pop_back和push_front

利用erase函数实现尾删和头删。

void pop_back()

{

erase(--end());

}

void pop_front()

{

erase(begin());

}

size

返回链表有效元素的个数.。

size_t size() const

{

return _size;

}

empty

判断链表是否为空。

bool empty() const

{

return _size == 0;

}

Print_Container

打印容器的函数。

template<class Container>

void Print_Container(const Container& con)

{

//const对象要用const迭代器，这里没实现的话会报错

/*auto it = con.begin();

while (it != con.end())

{

cout << *it << " ";

++it;

}*/

for (auto e : con)

{

cout << e << " ";

}

cout << endl;

}

拜拜，下期再见😏

摸鱼ing😴✨🎞