list模拟实现
一. list的基本框架
template<class T>
struct list_node
{
list_node<T>* _prev;
T _data;
list_node<T>* _next;
};
template<class T>
class list
{
typedef list_node<T> Node;
private:
Node* _head;
}
使用库中的list类需要包含头文件
#inlcude<list>
,并且使用std::
命名空间
list是一个带头结点的双向循环链表
_head
:指向其头结点
二. list_node类
1.构造函数
list_node(const T& val= T())
:_data(val)
,_prev(nullptr)
,_next(nullptr)
{}
每一个结点,创建时
_data
= val,并将_prev
和_next
置空(nullptr)。其中如果没有传val参数,则使用缺省值T():T类型的匿名对象(内置类型,如:int() = 0)
2.其他函数
其他成员函数使用编译器默认生成的函数就行,如:析构函数、拷贝构造、赋值运算符重载……
因为,如
- 拷贝构造:内置类型是按照字节方式直接拷贝的;自定义类型是调用其拷贝构造函数完成拷贝的
- 析构函数:无动态申请空间需要释放
三. 迭代器(iterator)
和string与vector的顺序存储不同,list存储是链式的。
所以
list::iterator
不能直接定义为元素指针,因为++、*(解引用)等对指针的操作在这里会出现问题
我们可以来封装原生指针(节点指针)成一个类,在类中完成运算符重载(operator 运算符),使++、*(解引用)等能完成其功能。此时iterator就变成像指针一样的对象了。
1.结构
template<class T, class Refence, class Pointer>
struct _list_iterator
{
typedef list_node<T> Node;
Node* _node;
};
2. 构造函数
_list_iterator(Node* node = nullptr)
:_node(node)
{}
3. 运算符重载
//为书写方便,typedf
typedef _list_iterator<T, Refence, Pointer> iterator;
bool operator!=(const iterator& it)
{
return _node != it._node;
}
bool operator==(const iterator& it)
{
return _node == it._node;
}
Refence operator*()
{
//返回节点的数据的引用
return _node->_data;
}
Pointer operator->()
{
//返回数据元素的指针
return &(operator*());
}
// ++it
iterator& operator++()
{
//自增1位
_node = _node->_next;
return *this;
}
// it++
//临时变量不能传引用
iterator operator++(int)
{
//后置++,返回+1前的值
iterator tmp(*this);
_node = _node->_next;
return tmp;
}
// --it
iterator& operator--()
{
_node = _node->_prev;
return *this;
}
// it--
//临时变量不能传引用
iterator operator--(int)
{
iterator tmp(*this);
_node = _node->_prev;
return tmp;
}
operator->
->
操作符:类对象指针访问其publibc成员
四.反向迭代器
反向迭代器与正向迭代器的区别主要是:移动方向不同。如:反向迭代器的++操作是向前走的
因此反向迭代器也需要重载运算符(operator 运算符),我们可以沿用正向迭代器的实现方法:将反向迭代器封装成一个类。
同时我们可以使用正向迭代器来适配反向迭代器,即复用正向迭代器的代码
反向迭代器设计时,可以规定和正向迭代器相反:
因此*rbegin的操作应该是先让rbegin向前移动1位再 *(解引用)
1.结构
template<class Iterator, class Refence, class Pointer>
struct _reverse_iterator
{
Iterator _rit;
}
反向迭代器类的成员变量是一个正向迭代器的对象(适配)
2.构造函数
_reverse_iterator(const Iterator& it = Iterator())
:_it(it)
{}
3.运算符重载
//为书写方便,typedf
typedef _reverse_iterator<Iterator, Refence, Pointer> Self;
Refence operator*()
{
Iterator tmp = _it;
return *(--tmp);
}
Pointer operator->()
{
return &(operator*());
}
Self& operator++()
{
--_it;
return *this;
}
Self& operator--()
{
++_it;
return *this;
}
bool operator!=(const Self& s)
{
return _it != s._it;
}
五. list常用方法及实现
1. 默认构造函数
a.empty_init
void empty_init()
{
// 创建并初始化哨兵位头结点
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
list()
{
empty_init();
}
2.迭代器
//正向迭代器
typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;
//反向迭代器
typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
反向迭代器第一个模板参数传入的正向迭代器的类 类型
a. begin
iterator begin()
{
//返回迭代器对象
return iterator(_head->_next);
}
const_iterator begin() const
{
return const_iterator(_head->_next);
}
返回首元素的位置(_head的下一个元素)
b. end
iterator end()
{
return iterator(_head);
}
const_iterator end() const
{
return const_iterator(_head);
}
end()返回,尾元素的下一个位置(即 _head)
c.rbegin
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(cend());
}
d.rend
reverse_iterator rend()
{
return reverse_iterator(begin());
}
const_reverse_iterator rend() const
{
return const_reverse_iterator(cbegin());
}
3.数据访问
a. size
size_t size() const
{
size_t count = 0;
iterator cur = begin();
while (cur != end())
{
++count;
}
return count;
}
遍历计数
b. empty
void empty() const
{
return begin() == end();
}
c. front
T& front()
{
return *begin();
}
const T& front() const
{
return *begin();
}
返回首元素的引用
d. back
T& back()
{
return *(--end());
}
const T& back() const
{
return *(--end());
}
返回尾元素的引用
4.增删操作
a. insert
iterator insert(iterator pos, const T& val)
{
//断言处理,避免pos指向一个空指针
assert(pos._node);
Node* cur = pos._node;
Node* newnode = new Node(val);
Node* prev = cur->_prev;
Node* next = cur;
//|prev| |newnode| |next|
newnode->_prev = prev;
prev->_next = newnode;
newnode->_next = next;
next->_prev = newnode;
return iterator(newnode);
}
在pos前 插入一个值为val的结点
b. push_back
void push_back(const T& val)
{
insert(end(), val);
}
在尾元素的下一个位置前,插入值为val的结点
c. push_front
void push_front(const T& val)
{
insert(begin(), val);
}
在首元素的位置前,插入值为val的结点
d. erase
iterator erase(iterator pos)
{
assert(pos._node);//pos指向的非空指针
assert(pos != end());//删除的不是尾元素的下一个位置
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
//|prev| |cur| |next|
prev->_next = next;
next->_prev = prev;
delete cur;
return iterator(next);
}
删除pos指向的元素,并返回删除位置的下一个位置的迭代器
e. pop_front
void pop_front()
{
erase(begin());
}
删除首元素
f. pop_back
void pop_back()
{
erase(--end());
}
删除尾元素
g.clear
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
迭代释放所有节点空间(除头节点外)
5.初始化和清理
a. 析构函数
~list()
{
clear();
delete _head;
_head = nullptr;
}
释放所有节点空间
b. n个val的构造
list(size_t n, const T& val = T())
{
empty_init();
for (size_t i = 0; i < n; ++i)
push_back(val);
}
c. 迭代器区间构造
template <class InputIterator>
list(InputIterator first, InputIterator last)
{
empty_init();//创建头结点
while (first != last)
{
push_back(*first);
++first;
}
}
d. swap
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
}
e. 拷贝构造
传统写法:
list(const list<T>& lt)
{
empty_init();//创建头结点
for (const auto& e : lt)
{
push_back(e);
}
}
现代写法:
通过一个局部对象,和swap来完成
list(const list<T>& lt)
{
empty_init();//创建头结点
list<T> temp(lt.begin(), lt.end());
swap(temp);
}
通过empty_init,对成员变量_head进行初始化,然后和经迭代器区间构造函数得到的temp对象进行交换内容,完成拷贝构造。该函数执行结束,局部对象temp会自动调用析构函数,并销毁。
f. operator=
传统写法:
list<T>& operator=(const list<T> lt)
{
//如果是自己给自己赋值则不操作
if (lt != this)
{
clear();
for (const auto& e : lt)
{
push_back(e);
}
}
return *this;
}
现代写法:
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
传参时,会调用拷贝构造函数完成对局部对象lt的初始化,然后交换*this和lt的内容,完成对自身对象的赋值。
六.小结
1.代码结构
可以将模拟实现的代码放在自己的命名空间中,避免冲突
#include <iostream>
#include <assert.h>
namespace yyjs
{
template<class T>
struct list_node
{};
template<class T, class Refence, class Pointer>
struct _list_iterator
{};
template<class Iterator, class Ref, class Ptr>
struct Reverse_iterator
{};
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;
typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
};
}
2.迭代器失效
插入元素时不会导致迭代器失效
iterator insert(iterator pos, const T& x);
在pos结点前插入一个元素,pos指向并未改变。
删除时迭代器会失效
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
对于上例中clear()函数中,每次进行删除操作后,it就是失效的迭代器(原先指向的空间被释放了),所以需要重新对it进行赋值(erase函数返回的是下一个位置的迭代器)。
3. 反向迭代器
由于list底层是一个双向链表,因此可以实现反向遍历等操作(–),所有可以实现其反向迭代器。
关于迭代器可以发现,对于客户(使用者)而言,不需要过多的了解使用的某个容器的底层实现原理,对于如string、vector与list,都提供了一个迭代器(iterator),我们甚至不需要考虑iterator具体是什么:是一个指针还是一个类?
在使用时,auto it = lti.begin()
,然后就可以遍历容器的元素,并且他们的操作方法都相同,如it++、*it……文章来源:https://www.toymoban.com/news/detail-488731.html
🦀🦀观看~~文章来源地址https://www.toymoban.com/news/detail-488731.html
到了这里,关于STL之list的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!