目录
1. list类的介绍
list代表的是双向链表，常见的有创建，增，删，改几个接口（功能），对于list类来说，复杂的是它的迭代器，本章则会讲解list类的常见接口实现以及list类的简单实现。
2.list类的常用接口
2.1 list类的常用构造
| 构造函数 | 接口说明 |
| list(size_t n,const T& val=T())(注：T代表模版) | 构造n个val值的元素 |
| list() | 默认构造 |
| list(const list<T>& x) | 拷贝构造 |
| list(InputIterator first, InputIterator last) | 利用迭代器区间构造list |
#include<iostream>
#include<string>
#include<list>
using namespace std;
int main()
{
list<int> l1;//默认构造
list<int> l2(l1);//拷贝构造
list<int> l3(10, 1);//构造n个val值
string s("123456");
list<int> l4(s.begin(), s.end());//利用迭代器区间构造
return 0;
}2.2 list类对象的容量操作
| 函数名称 | 接口说明 |
| empty | 判断list是否为空，是返回true,否则返回false |
| size | 返回list中有效节点个数 |
2.3 list迭代器
| 函数名称 | 接口说明 |
begin+end |
begin返回第一个元素的迭代器
end 返回最后一个元素下一个位置的迭代器
|
| rbegin+rend |
rbegin返回最后一个元素的迭代器
rend 返回第一个元素前一个位置的迭代器
|
#include<iostream>
#include<string>
#include<list>
using namespace std;
int main()
{
list<int> l(10, 1);//构造n个val值
for (auto e : l)
{
cout << e << " ";
}
return 0;
}2.4 list类的常用操作
| 函数名称 | 接口说明 |
| front | 返回list的第一个节点值的引用 |
| back | 返回list的最后一个节点值的引用 |
| push_front | 在list首元素前插入值为val的元素 |
| pop_front | 删除list第一个元素 |
| push_back | 在list尾部插入值为val的元素 |
| pop_back | 删除list最后一个元素 |
| insert | 在list的pos位置中插入值为val的值 |
| erase | 删除list的pos位置的数据 |
| swap |
交换两个 list 中的元素
|
| clear |
清空 list 中的有效元素
|
#include<iostream>
#include<string>
#include<list>
using namespace std;
void Print(const list<int>& l)
{
list<int>::const_iterator it = l.begin();
while (it != l.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
int main()
{
list<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
Print(l1);//打印
cout << endl;
int a = l1.front();
cout << a << endl;
cout << l1.back() << endl;
cout << endl;
l1.push_front(10);
Print(l1);
cout << endl;
l1.pop_front();
Print(l1);
cout << endl;
l1.pop_back();
Print(l1);
cout << endl;
list<int>::iterator it = l1.begin();
++it;
l1.insert(it, 20);
Print(l1);
cout << endl;
l1.erase(it);
Print(l1);
cout << endl;
list<int> l2(10, 1);
l1.swap(l2);
Print(l1);
Print(l2);
cout << endl;
l1.clear();
Print(l1);
return 0;
}
3.list的模拟实现
3.1 list的基本结构
list的基本结构由三个类组成，一个是自己本身，一个是list的每个节点，最后就是有关迭代器的类，由于list中的底层结构是不连续的，因此不能用原本指针去访问，要对list的指针进行一个封装
namespace chuxin
{
template<class T>
struct list_node//链表的节点
{
T _data;
list_node<T>* _prev;
list_node<T>* _next;
};
template<class T>
struct list_iterator//迭代器
{
typedef list_node<T> Node;
typedef list_iterator<T> Self;
Node* _node;
};
template<class T>//链表
class list
{
typedef list_node<T> Node;
public:
typedef list_iterator<T> iterator;
private:
Node* _head;
size_t _size;
};
}3.2 list的构造及析构
对于list来说，三个类都需要构造，但是，析构只有list就够了
namespace chuxin
{
template<class T>
struct list_node//链表的节点
{
T _data;
list_node<T>* _prev;
list_node<T>* _next;
list_node(const T& data = T())//构造
:_data(data)
, _prev(nullptr)
, _next(nullptr)
{}
};
template<class T>
struct list_iterator//迭代器
{
typedef list_node<T> Node;
typedef list_iterator<T> Self;
Node* _node;
list_iterator(Node* node)//构造
:_node(node)
{}
};
template<class T>//链表
class list
{
typedef list_node<T> Node;
public:
typedef list_iterator<T> iterator;
list()//默认构造
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list(const list<T>& lt)//拷贝构造
{
empty();
for (auto& e : lt)
{
push_back(e);
}
}
~list()//析构
{
clear();
delete _head;
_head = nullptr;
}
private:
Node* _head;
size_t _size;
};
}3.3 迭代器
迭代器要进行的操作有++，--，比较，以及使用数据
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;
}
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
bool operator!=(const Self& s)const
{
return s._node != _node;
}
bool operator==(const Self& s)const
{
return s._node == _node;
}
};对于list的迭代器，还要重载一个—>,由于list内每个节点内的数据可能是一个结构体，这时候虽然还能用 . 作用符访问，但是较复杂。
struct AA
{
int _a1 = 1;
int _a2 = 1;
};
void test_list1()
{
list<int> lt;
list<AA> lta;
lta.push_back(AA());
lta.push_back(AA());
lta.push_back(AA());
lta.push_back(AA());
list<AA>::iterator ita = lta.begin();
while (ita != lta.end())
{
//cout << (*ita)._a1 << ":" << (*ita)._a2 << endl;
// 特殊处理，本来应该是两个->才合理，为了可读性，省略了一个->
cout << ita->_a1 << ":" << ita->_a2 << endl;
cout << ita.operator->()->_a1 << ":" << ita.operator->()->_a2 << endl;
++ita;
}
cout << endl;
} 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--()
{
_node = _node->_prev;
return *this;
}
bool operator!=(const Self& s)const
{
return s._node != _node;
}
bool operator==(const Self& s)const
{
return s._node == _node;
}
};对于迭代器，还要实现一个const的版本,如果要实现一个const的版本，发现两个类的结构大多相似，这时候就可以利用模版
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--()
{
_node = _node->_prev;
return *this;
}
bool operator!=(const Self& s)const
{
return s._node != _node;
}
bool operator==(const Self& s)const
{
return s._node == _node;
}
};
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;
list()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list(const list<T>& lt)
{
empty();
for (auto& e : lt)
{
push_back(e);
}
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
private:
Node* _head;
size_t _size;
};
此时利用三个模版参数就可以实现简洁化
3.4 赋值，clear,size,begin,end,front,back,empty
这几个较简单，不做叙述
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;
list()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list(const list<T>& lt)
{
empty();
for (auto& e : lt)
{
push_back(e);
}
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
}
// lt1 = lt3
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;
}
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}
size_t size() const
{
return _size;
}
T& front()
{
return _head->_next->_data;
}
T& back()
{
return _head->_prev->_data;
}
bool empty() const
{
return _size == 0;
}
private:
Node* _head;
size_t _size;
};3.5 insert,erase,push_back,push_front,pop_back,pop_front
对于这些增删查改，可以进行一些复用，insert,erase，这里的插入，删除和链表完全相似，也不做详细叙述
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
prev->_next = newnode;
newnode->_next = cur;
newnode->_prev = prev;
cur->_prev = newnode;
++_size;
return newnode;
}
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
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;
}
void pop_front()
{
erase(begin());
}
void pop_back()
{
iterator it = end();
--it;
erase(it);
}3.5 总代码
List.h
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
namespace chuxin
{
template<class T>
struct list_node//链表的节点
{
T _data;
list_node<T>* _prev;
list_node<T>* _next;
list_node(const T& data = T())
:_data(data)
, _prev(nullptr)
, _next(nullptr)
{}
};
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--()
{
_node = _node->_prev;
return *this;
}
bool operator!=(const Self& s)const
{
return s._node != _node;
}
bool operator==(const Self& s)const
{
return s._node == _node;
}
};
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;
list()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list(const list<T>& lt)
{
empty();
for (auto& e : lt)
{
push_back(e);
}
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
}
// lt1 = lt3
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;
}
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
prev->_next = newnode;
newnode->_next = cur;
newnode->_prev = prev;
cur->_prev = newnode;
++_size;
return newnode;
}
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
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;
}
void pop_front()
{
erase(begin());
}
void pop_back()
{
iterator it = end();
--it;
erase(it);
}
size_t size() const
{
return _size;
}
T& front()
{
return _head->_next->_data;
}
T& back()
{
return _head->_prev->_data;
}
bool empty() const
{
return _size == 0;
}
private:
Node* _head;
size_t _size;
};
}