【C++】list的使用 | 模拟实现
文章目录
- 一、list的使用
- 1. 构造函数
- 2. 迭代器
- 3. 增删查改
- 4. 其他成员函数
- 二、list的模拟实现
- 1. 节点的创建
- 2. push_back和push_front
- 3. 普通迭代器
- 4. const迭代器
- 5. 增删查改(insert、erase、pop_back、pop_front)
- 7. 构造和析构
- 三、list模拟实现整体源码
- 四、vector和list的区别
一、list的使用
前面我们在数据结构阶段讲过：【双向带头循环链表】，其实我们前面所讲过的双向带头循环链表就是基于STL中的list所实现的。双向带头循环链表的整体结构如下：
对于list，我们需要注意以下几点：
- list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
- list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
- list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
- 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
- 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)
1. 构造函数
int main()
{
//默认构造
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
//拷贝构造
list<int> lt2(lt);
//迭代器区间构造
list<int> lt3(lt.begin(), lt.end());
//构造n个val
list<int> lt4(5, 1);
return 0;
}
2. 迭代器
此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。
注意:
- begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
- rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动。
3. 增删查改
这里我们需要注意的是：由于list是一个链表，它的物理地址是不连续的，所以list不支持[]访问，list的空间是使用一个开辟一个，所以他也是不支持reserve操作的。
4. 其他成员函数
sort——链表排序
我们知道算法库中是有一个sort函数的，但由于list中节点的空间是不连续的，所以不能使用算法库中的sort函数，所以list自己提供了一个sort函数，但是这个接口我们一般也不会使用，因为链表排序的效率实在是太低了。
unique——链表去重
我们在使用链表去重之前需要保证链表有序，否则就会导致去重不完全。
remove——移除链表中的指定元素
remove用来移除链表中的指定元素，如果元素不存在，则此接口什么都不会做。
merge——归并两个有序链表
这里我们需要注意的是，两个链表必须有序才能够调用这个函数来进行归并，而且归并之后，被归并的一方的元素将会消失，相当于把一方中的元素转移到了另一方中，而且，归并后的链表依然保持有序。
二、list的模拟实现
1. 节点的创建
//节点的封装
template<class T>
struct list_node
{
list_node<T>* _prev;
list_node<T>* _next;
T _val;
//构造函数
list_node(const T& val = T())
:_prev(nullptr)
,_next(nullptr)
,_val(val)
{}
};
首先，由于节点存储的数据可能是任意类型，所以我们需要将将节点定义为模板类。这里我们需要写一个给缺省值的默认构造函数，便于之后在主类中new一个新节点时直接初始化，同时将两个指针置为空，将数据写入数据域中。这里还有一点需要注意的是：在类内，不管是否存在模板，类名都可以作为类型，但是为了避免混淆我们不建议这样使用。
2. push_back和push_front
由于我们需要在list类中的成员变量需要定义一个list_node<T>*类型的指针，而且我们在后面会经常用到list_node这种类型。所以在这里我们直接将这个类型typedef一下。
💕 list类的整体框架：
class list{
public:
typedef list_node<T> node;
//成员方法...
private:
node* _head;
}
//尾插
void push_back(const T& x) const
{
node* new_node = new node(x);
node* tail = _head->_prev;
//链接节点之间的关系
tail->_next = new_node;
new_node->_prev = tail;
new_node->_next = _head;
_head->_prev = new_node;
}
//头插
void push_front(const T& x)
{
node* head = _head->_next;
node* new_node = new node(x);
_head->_next = new_node;
new_node->_prev = _head;
new_node->_next = head;
head->_prev = new_node;
}
这里的头插和尾插也很简单，因为和我们之前在数据结构时候的双向循环链表是一样的，只需要找到头或者尾，然后链接四个节点间的关系即可。
3. 普通迭代器
因为迭代器是类似于指针的存在，迭代器要实现指针相关的全部或者部分操作，+、-、++、- -、*、我们之前的string和vector使用的就是原生指针，所以他天然就支持上述的所有操作，但是list就不一样了。
因为list的节点是一个结构体，同时list的每一个节点的物理地址是不连续的，所以如果我们直接使用普通的原生指针来作为list的迭代器的话就不能够进行，解引用、++、–等操作，所以我们需要将迭代器封装为一个类，在类中实现这些操作的运算符重载才能够得到最终的结果。
template<class T>
struct __list_iterator
{
typedef list_node<T> node;
typedef __list_iterator<T> self;
//构造函数
__list_iterator(node* n)
:_node(n)
{}
node* _node;
//重载*运算符
T& operator*()
{
return _node->_val;
}
//重载前置++运算符
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& s)
{
return _node != s._node;
}
//重载==运算符
bool operator==(const self& s)
{
return _node == s._node;
}
};
我们实现一个简单的正向迭代器是很容易的，使用一个模板参数T表示类型，当然这里我们可以将__list_iterator<T>来typedef一下，方便后续使用。最后将这些运算符都重载一遍即可。
普通迭代器封装好了之后，我们需要在list类中来实现它的begin()和end()方法。由于迭代器的名字一般都是iterator，而且对于范围for来说，也只能通过iterator来转换为迭代器进行遍历。所以这里我们将其typedef为iterator。
typedef __list_iterator<T> iterator;
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
4. const迭代器
const迭代器与普通迭代器的区别在于const迭代器指向的内容是不能修改的，但是它的指向是可以修改的，但在这里有些人可能会投机取巧用以下的方式来实现const迭代器：
typedef const iterator const_iterator;
const_iterator begin() const
{
return const_iterator(_head->_next);
}
const_iterator end() const
{
return const_iterator(_head);
}
这里我们千万要注意这种方式是不行的。因为const修饰的是iterator的返回值，即iterator的指向是不能修改的，如果我们这样写的话那么迭代器就不能++和–操作了，而解引用后的内容依旧是可以修改的。
在这里我们最好的做法就是在__list_iterator的类模板中的添加一个模板参数，然后再list类中typedef两份分别将第二个参数分别改成T&和const T&的类型，本质上就是让编译器根据传入的Ref的不同来自动示例化出const迭代器类，具体的解决做法如下：
template<class T,class Ref>
struct __list_iterator
{
typedef list_node<T> node;
typedef __list_iterator<T,Ref> self;
//构造函数
__list_iterator(node* n)
:_node(n)
{}
node* _node;
//重载*运算符
Ref operator*()
{
return _node->_val;
}
//...
};
//list类中typedef两份
typedef __list_iterator<T, T&> iterator;
typedef __list_iterator<T, const T&> const_iterator;
这里还有一个问题就是：如果我们需要重载一个->运算符，因为list中可能存储的是自定义类型，这个自定义类型如果要是有多个成员变量的话，我们就需要使用->来解引用访问成员变量。这里又出现问题了，因为又有普通迭代器和const迭代器的区分，所以为了解决同样的问题，我们同样选择多添加一个模板参数来解决这个问题。
template<class T,class Ref,class Ptr>
struct __list_iterator
{
typedef list_node<T> node;
typedef __list_iterator<T,Ref,Ptr> self;
//构造函数
__list_iterator(node* n)
:_node(n)
{}
node* _node;
//重载*运算符
Ref operator*()
{
return _node->_val;
}
//重载->
Ptr operator->()
{
return &_node->_val;
}
//...
};
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&,const T*> const_iterator;
下面我们来总结一下完整版的list迭代器的实现：
template<class T,class Ref,class Ptr>
struct __list_iterator
{
typedef list_node<T> node;
typedef __list_iterator<T,Ref,Ptr> self;
//构造函数
__list_iterator(node* n)
:_node(n)
{}
node* _node;
//重载*运算符
Ref operator*()
{
return _node->_val;
}
//重载->
Ptr operator->()
{
return &_node->_val;
}
//重载前置++运算符
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& s)
{
return _node != s._node;
}
//重载==运算符
bool operator==(const self& s)
{
return _node == s._node;
}
};
//list类内
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&,const T*> const_iterator;
iterator begin()
{
return iterator(_head->_next);
}
const_iterator begin() const
{
return const_iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
const_iterator end() const
{
return const_iterator(_head);
}
5. 增删查改(insert、erase、pop_back、pop_front)
//指定位置插入
void insert(iterator pos,const T& x)
{
node* cur = pos._node;
node* prev = cur->_prev;
node* new_node = new node(x);
prev->_next = new_node;
new_node->_prev = prev;
new_node->_next = cur;
cur->_prev = new_node;
}
//指定位置删除
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;
return iterator(next);
}
//尾删
void pop_back()
{
erase(--end());
}
//头删
void pop_front()
{
erase(begin());
}
7. 构造和析构
默认构造
由于我们将来在构造新的对象的时候会经常用到创建一个头结点的操作，所以这里我们在写默认无参构造的时候直接将它写成一个函数，以便于后面的调用。
list()
{
empty_Init();
}
void empty_Init()
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
}
拷贝构造
//拷贝构造传统写法
list(const list<T>& lt)
{
empty_Init();
for (auto e : lt)
{
push_back(e);
}
}
//拷贝构造现代写法
list(const list<T>& lt)
{
empty_Init();
list<T> tmp(lt.begin(), lt.end());
swap(tmp);
}
迭代器区间构造
template <class Iterator>
list(Iterator first, Iterator last)
{
empty_Init();
while (first != last)
{
push_back(*first);
first++;
}
}
//交换函数
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
}
用n个val来构造对象
//用n个val构造对象
list(int n, const T& val = T())
{
empty_Init();
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
赋值运算符重载
//赋值运算符重载——传统写法
list<T>& operator=(const list<T>& lt)
{
if (this != <)
{
clear();
for (const auto& e : lt)
{
push_back(e);
}
}
return *this;
}
//赋值运算符重载
list<T>& operator=(list<T> lt)//注意这里不能用引用
{
swap(lt);
return *this;
}
析构函数
//clear函数的实现
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
//erase(it++); 这种写法也是可以的
}
}
//析构函数
~list()
{
clear();
delete _head;
_head = nullptr;
}
size 和 empty
//size()
size_t size() const
{
iterator it = begin();
size_t Size = 0;
while (it != end())
{
++Size;
++it;
}
return Size;
}
//empty
bool empty() const
{
return _head->_next == _head
&& _head->_prev == _head;
}
三、list模拟实现整体源码
namespace cjl
{
//节点的封装
template<class T>
struct list_node
{
list_node<T>* _prev;
list_node<T>* _next;
T _val;
//构造函数
list_node(const T& val = T())
:_prev(nullptr)
,_next(nullptr)
,_val(val)
{}
};
//迭代器的封装——普通迭代器
//迭代器可能是原生指针，也可能是自定义类型对原生指针的封装，模拟指针的行为
template<class T,class Ref,class Ptr>
struct __list_iterator
{
typedef list_node<T> node;
typedef __list_iterator<T,Ref,Ptr> self;
//构造函数
__list_iterator(node* n)
:_node(n)
{}
node* _node;
//重载*运算符
Ref operator*()
{
return _node->_val;
}
//重载->
Ptr operator->()
{
return &_node->_val;
}
//重载前置++运算符
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& s)
{
return _node != s._node;
}
//重载==运算符
bool operator==(const self& s)
{
return _node == s._node;
}
};
//迭代器的封装——const迭代器——这样写造成了严重的代码冗余
//template<class T>
//struct __list_const_iterator
//{
// typedef list_node<T> node;
// typedef __list_const_iterator<T> self;
// //构造函数
// __list_const_iterator(node* n)
// :_node(n)
// {}
// node* _node;
// //重载*运算符
// const T& operator*()
// {
// return _node->_val;
// }
// //重载前置++运算符
// self& operator++()
// {
// _node = _node->_next;
// return *this;
// }
// //重载!=运算符
// bool operator!=(const self& s)
// {
// return _node != s._node;
// }
//};
template<class T>
class list
{
public:
typedef list_node<T> node;
typedef __list_iterator<T, T&, T*> iterator;
//typedef __list_const_iterator<T> const_iterator;
typedef __list_iterator<T, const T&,const T*> const_iterator;
iterator begin()
{
return iterator(_head->_next);
}
const_iterator begin() const
{
return const_iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
const_iterator end() const
{
return const_iterator(_head);
}
//默认的无参构造
list()
{
empty_Init();
}
void empty_Init()
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
}
//用n个val构造对象
list(int n, const T& val = T())
{
empty_Init();
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
//析构函数
~list()
{
clear();
delete _head;
_head = nullptr;
}
//拷贝构造
/*list(const list<T>& lt)
{
empty_Init();
for (auto e : lt)
{
push_back(e);
}
}*/
//拷贝构造——现代写法
list(const list<T>& lt)
{
empty_Init();
list<T> tmp(lt.begin(), lt.end());
swap(tmp);
}
//迭代器区间构造
template <class Iterator>
list(Iterator first, Iterator last)
{
empty_Init();
while (first != last)
{
push_back(*first);
first++;
}
}
赋值运算符重载——传统写法
//list<T>& operator=(const list<T>& lt)
//{
// if (this != <)
// {
// clear();
// for (const auto& e : lt)
// {
// push_back(e);
// }
// }
// return *this;
//}
//赋值运算符重载
list<T>& operator=(list<T> lt)//注意这里不能用引用
{
swap(lt);
return *this;
}
//交换函数
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
}
//尾插
void push_back(const T& x) const
{
node* new_node = new node(x);
node* tail = _head->_prev;
//链接节点之间的关系
tail->_next = new_node;
new_node->_prev = tail;
new_node->_next = _head;
_head->_prev = new_node;
}
//尾删
void pop_back()
{
erase(--end());
}
//头插
void push_front(const T& x)
{
node* head = _head->_next;
node* new_node = new node(x);
_head->_next = new_node;
new_node->_prev = _head;
new_node->_next = head;
head->_prev = new_node;
//insert(begin(), x);
}
//头删
void pop_front()
{
erase(begin());
}
//指定位置插入
void insert(iterator pos,const T& x)
{
node* cur = pos._node;
node* prev = cur->_prev;
node* new_node = new node(x);
prev->_next = new_node;
new_node->_prev = prev;
new_node->_next = cur;
cur->_prev = new_node;
}
//指定位置删除
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;
return iterator(next);
}
//clear函数的实现
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
//erase(it++); 这种写法也是可以的
}
}
//size()
size_t size() const
{
iterator it = begin();
size_t Size = 0;
while (it != end())
{
++Size;
++it;
}
return Size;
}
//empty
bool empty() const
{
return _head->_next == _head
&& _head->_prev == _head;
}
private:
node* _head;
};
}
四、vector和list的区别
