【C++】list的介绍及模拟实现-创新互联
目录🌈感谢阅读East-sunrise学习分享——list的介绍及模拟实现
成都创新互联公司是少有的成都网站设计、网站建设、营销型企业网站、重庆小程序开发、手机APP,开发、制作、设计、卖友情链接、推广优化一站式服务网络公司,从2013年成立,坚持透明化,价格低,无套路经营理念。让网页惊喜每一位访客多年来深受用户好评博主水平有限,如有差错,欢迎斧正🙏感谢有你
码字不易,若有收获,期待你的点赞关注💙我们一起进步
今天想分享介绍一下STL的容器之一list,以及进行模拟实现📌
- 一、list的介绍
- 二、list的模拟实现(简易版--过渡)
- 三、迭代器
- 1.迭代器的定义
- 2.迭代器的功能分类
- 3.迭代器失效
- 4.list迭代器的模拟实现
- 1.普通迭代器
- 2.const迭代器
- 5.迭代器operator->的重载
- 6.迭代器的价值
- 四、vector和list的优缺点
- 1.vector
- 2.list
- 五、代码实现
- list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。
- list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。
- list的底层结构即是链表,这里附上博主之前关于【数据结构】链表的博客【数据结构-链表】有助于熟悉list的底层结构
- 关于list的使用并不复杂,相信学到这的兄弟以及拥有了查文档的能力,博主就不再赘述list各种接口的具体用法,附上文档介绍list使用文档
有了之前对数据结构——链表的知识基础,其实list的底层结构也并不神秘了,而list相较于前面的string、vector容器特别的地方就在于其迭代器,今天我们重点放在list的模拟实现及迭代器的介绍
二、list的模拟实现(简易版–过渡)
list底层结构是带头双向链表
templatestruct list_node
{list_node* _next;//指向下一个节点
list_node* _prev;//指向前一个节点
T _data;//节点数据
//构造函数
list_node(const T& x)
:_next(nullptr)
, _prev(nullptr)
, _data(x)
{}
};
定义完list的节点,接下来即是list的主要结构
namespace qdy
{templatestruct list_node
{list_node* _next;
list_node* _prev;
T _data;
list_node(const T& x)
:_next(nullptr)
, _prev(nullptr)
, _data(x)
{}
};
templateclass list
{typedef list_nodenode;
public:
list()
{ _head = new node(T());
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
//尾插
void push_back(const T& x)
{ node* newnode = new node(x);
node* tail = _head->_prev;
// _head tail newnode
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
}
private:
node* _head;//哨兵位的头节点
size_t _size;//记录节点个数
};
以上便是list的结构框架(简易版实现),目前仅有尾插的接口,用于对list容器中添加数据✏️
添加数据后我们想要遍历打印怎么办呢?那就需要用到STL六大组件之一的迭代器🧮
三、迭代器 1.迭代器的定义
iterator的模式定义:“提供一种方法,使之能够依序巡访某个聚合物(容器)所含的各个元素,而又无需暴露该聚合物的内部表述方式。”
——《STL源码剖析》
🎈通俗理解:容器用于存放数据,存放数据便有访问数据读写数据的需求,STL六大组件之一的迭代器,便是给每个容器提供一个便于读取数据的方法
2.迭代器的功能分类- 单向迭代器:只能++,不能–。例如单链表、哈希表
- 双向迭代器:既能++也能–。例如双向链表
- 随机访问迭代器:能+±-,也能+和-。例如vector和string
迭代器是内嵌类型,通常定义为内部类或者直接定义在类中
3.迭代器失效对于list,迭代器在进行insert操作后不失效,在进行erase操作后失效❌
前面说过,此处大家可将迭代器暂时理解成类似于指针,迭代器失效即迭代器所指向的节点无效,即该节点被删除了。因为list的底层结构为带头结点的双向循环链表,因此在list中进行插入时是不会导致list的迭代器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭代器,其他迭代器不会受到影响。
void TestListIterator1()
{int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
listl(array, array+sizeof(array)/sizeof(array[0]));
auto it = l.begin();
while (it != l.end())
{// erase()函数执行后,it所指向的节点已被删除,因此it无效,在下一次使用it时,必须先给其赋值
l.erase(it);
++it;
}
}
// 改正
void TestListIterator()
{int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
listl(array, array+sizeof(array)/sizeof(array[0]));
auto it = l.begin();
while (it != l.end())
{it = l.erase(it);
//为了避免迭代器失效的问题,erase接口提供了返回值可接收,该返回值为删除后的下一节点
}
}
4.list迭代器的模拟实现
1.普通迭代器在对迭代器模拟实现之前,我们要搞清楚list迭代器要有什么功能?
- 支持解引用(读取数据)
- 支持++和–(访问上一个or下一个节点)
回顾之前string和vector迭代器的模拟实现,我们是直接将指针typedef为迭代器使用,因为string和vector的底层结构是顺序表,是一段连续的物理空间,所以通过使用原生指针便能符合其迭代器的需求了✔️
💥但是list的底层结构是链表,链表是按需开辟空间,并不是一段连续的物理空间,每个节点的物理地址并不连续,我们无法直接使用原生指针去+±-来遍历来访问节点。我们回顾刚开始接触C++学习的日期类,日期类中的“日期”是我们自己定义的一种自定义类型,无法使用内置操作符直接对日期进行运算操作(编译器又不认识那么多)所以我们是通过自己再去重定义日期的操作类,去重载操作符来满足需求。
🚩类和对象说:该我上场表演了
既然原生指针已经无法满足list迭代器的需求,那么我们可以自己定义一个迭代器,然后将节点指针封装起来,然后再根据我们具体的需求情况去重载各种运算符实现迭代器功能。
//用类封装迭代器
templatestruct __list_iterator
{typedef list_nodenode;
node* _pnode;//封装一个节点的指针
//用节点指针进行构造
__list_iterator(node* p)
:_pnode(p)
{}
//迭代器运算符的重载
T& operator*()
{return _pnode->_data;
}
__list_iterator& operator++()
{_pnode = _pnode->_next;
return *this;//返回的是迭代器
}
bool operator!=(const __list_iterator& it)
{return _pnode != it._pnode;
}
};
定义完迭代器后便能对我们添加了数据的list进行遍历打印了
1.迭代器遍历 2.范围for遍历(底层也是调用了迭代器)
void test_list1()
{listlt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
list::iterator it = lt.begin();
while (it != lt.end())
{cout<< *it<< " ";
++it;
}
cout<< endl;
for (auto e : lt)
{cout<< e<< " ";
}
cout<< endl;
}
定义完迭代器后,通过迭代器对容器数据进行访问,实际上是一种函数调用
2.const迭代器❌const迭代器的错误写法
typedef __list_iteratoriterator;
const list::iterator cit = lt.begin();
const之前我们修饰指针时有两种方法
const T* p1;
T* const p2;
正确的const迭代器应该是像p1的行为,保护指向的对象不被修改,但是迭代器本身是可以修改的
但是上述的const迭代器写法是保护了迭代器本身不能被修改,那么我们就不能++迭代器了
✔️正确写法:想实现const迭代器,无法对普通迭代器直接加const,需要再写一个const版本迭代器的类
templatestruct __list_const_iterator
{typedef list_nodenode;
node* _pnode;
__list_const_iterator(node* p)
:_pnode(p)
{}
const T& operator*()const
{return _pnode->_data;
}
__list_const_iterator& operator++()
{_pnode = _pnode->_next;
return *this;
}
__list_const_iterator& operator--()
{_pnode = _pnode->_prev;
return *this;
}
bool operator!=(const __list_const_iterator& it)
{return _pnode != it._pnode;
}
};
typedef __list_iteratorconst_iterator;
但是如果像上述一样,写一个普通迭代器再写一个const迭代器,代码看起来就十分的冗长。那么我们可以利用好类模板,类模板即是能根据模板和调用时的参数,根据实参类型推演产生函数的特定类型版本。这样,我们根据传入参数的不同,可以使得一份类模板生成两种类型的迭代器🧮
templatestruct __list_iterator
{typedef list_nodenode;
typedef __list_iteratorSelf;
node* _pnode;
__list_iterator(node* p)
:_pnode(p)
{}
Ref operator*()
{return _pnode->_data;
}
Self& operator++()
{_pnode = _pnode->_next;
return *this;
}
Self& operator--()
{_pnode = _pnode->_prev;
return *this;
}
bool operator!=(const Self& it)
{return _pnode != it._pnode;
}
};
typedef __list_iteratoriterator;
typedef __list_iteratorconst_iterator;
5.迭代器operator->的重载我们调用对象的成员变量成员函数是用.
实现,对指针解引用取其值是用*
实现,而当结构体要解引用是使用->
,再用->
取其成员变量。而假如现在list中就存放的是结构体类型的数据✏️
所以我们有必要对->
也进行重载
T* operator->()
{return &_pnode->_data;
}
重载完之后我们要怎么使用呢❓一共有3种方法
//坐标类
struct Pos
{int _row;
int _col;
Pos(int row = 0, int col = 0)
:_row(row)
,_col(col)
{}
};
void test()
{listlt;
lt.push_back(Pos(1,1));
lt.push_back(Pos(2,2));
lt.push_back(Pos(3,3));
// int* p --->*p
// Pos* p --->p->list::iterator it = lt.begin();
while (it != lt.end())
{cout<< (&(*it))->_row;
//*it取出容器数据(POS类) -- 再取地址访问解引用得到_row
cout<< it.operator->()->_row;
//it.operator->()是显式调用,然后再->解引用得到_row
cout<< it->_row;
//同第二种写法,编译器为了可读性,省略了一个->
++it;
}
}
💥但是当实际使用时,会发现有问题,那就是->的重载返回值为T*,这样一来无论是普通迭代器或const迭代器都能对其值进行修改,所以我们需要将operator->
的返回值改为泛型,然后针对不同的迭代器给不同的返回参数以示区分,如此一来,我们的迭代器模板又得再多一个参数啦📈
templatePtr operator->()
{return &_pnode->_data;
}
typedef __list_iteratoriterator;
typedef __list_iteratorconst_iterator;
6.迭代器的价值- 封装底层实现,不暴露底层实现的细节
- 多种容器提供统一的访问方式,降低容器使用成本
- C语言没有运算符重载和引用等语法,是实现不了迭代器的
四、vector和list的优缺点
vector和list就像左右手一样,是互补配合的关系
vector的优点即是list的缺点,list的优点也是vector的缺点,实际使用时可按照需求择优选用或者结合使用
1.vectorvector的优点
- 支持下标的随机访问
- 尾插尾删效率高(但是扩容的那一次尾插会较慢)
- CPU高速缓存命中高(得益于vector的结构是一段连续的物理空间,数据从缓存加载到CPU时,是会加载连续的一段数据,而不是一个个加载,这样一来在加载vector时高速缓存命中就很高)
🎈综上所述vector的优点都得益于其结构优势
vector的缺点
- 非尾插尾删效率极低O(N)
- 扩容有消耗,还存在一定的空间浪费
🎈迭代器失效
insert和erase均会导致迭代器失效
2.listlist的优点
- 按需申请释放,无需扩容
- 任意位置插入删除效率高O(1)
list的缺点
- 不支持下标的随机访问
- CPU高速缓存命中率低
🎈迭代器失效
insert不失效,erase失效
五、代码实现
namespace qdy
{templatestruct list_node
{list_node* _next;
list_node* _prev;
T _data;
list_node(const T& x)
:_next(nullptr)
,_prev(nullptr)
,_data(x)
{}
};
templatestruct __list_iterator
{typedef list_nodenode;
typedef __list_iteratorSelf;
node* _pnode;
__list_iterator(node* p)
:_pnode(p)
{}
Ptr operator->()
{ return &_pnode->_data;
}
Ref operator*()
{ return _pnode->_data;
}
Self& operator++()
{ _pnode = _pnode->_next;
return *this;
}
Self& operator--()
{ _pnode = _pnode->_prev;
return *this;
}
Self operator--(int)
{ Self tmp(*this);
_pnode = _pnode->_prev;
return tmp;
}
bool operator!=(const Self& it)
{ return _pnode != it._pnode;
}
bool operator==(const Self& it) const
{ return _pnode == it._pnode;
}
};
templateclass list
{typedef list_nodenode;
public:
typedef __list_iteratoriterator;
//typedef __list_const_iteratorconst_iterator;
typedef __list_iteratorconst_iterator;
//构造函数
list()
{ empty_initialize();
}
~list()
{ clear();
delete _head;
_head = nullptr;
}
void clear()
{ iterator it = begin();
while (it != end())
{ it = erase(it);
}
}
const_iterator begin() const
{ return const_iterator(_head->_next);
}
const_iterator end() const
{ return const_iterator(_head);
}
iterator begin()
{ return iterator(_head->_next);
//iterator it(_head->_next);
//return it;
}
iterator end()
{ return iterator(_head);
}
void empty_initialize()
{ _head = new node(T());
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
templatelist(InputIterator first, InputIterator last)
{ empty_initialize();
while (first != last)
{ push_back(*first);
++first;
}
}
void swap(list& lt)
{ std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
// 现代写法
// lt2(lt1)
list(const list& lt)
//list(const list& lt) // 不建议
{ empty_initialize();
listtmp(lt.begin(), lt.end());
swap(tmp);
}
// lt3 = lt1
list& operator=(listlt)
//list& operator=(list lt) // 不建议
{ swap(lt);
return *this;
}
//尾插
void push_back(const T& x)
{ //node* newnode = new node(x);
//node* tail = _head->_prev;
_head tail newnode
//newnode->_prev = tail;
//tail->_next = newnode;
//newnode->_next = _head;
//_head->_prev = newnode;
insert(end(), x);
}
void push_front(const T& x)
{ insert(begin(), x);
}
void pop_back()
{ erase(--end());
}
void pop_front()
{ erase(begin());
}
iterator insert(iterator pos, const T& x)
{ node* newnode = new node(x);
node* cur = pos._pnode;
node* prev = cur->_prev;
//prev newnode cur
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
++_size;
return iterator(newnode);
}
iterator erase(iterator pos)
{ assert(pos != _head);
node* prev = pos._pnode->_prev;
node* next = pos._pnode->_next;
prev->_next = next;
next->_prev = prev;
delete pos._pnode;
--_size;
return iterator(next);
}
size_t size()const
{ return _size;
}
bool empty()const
{ return _size == 0;
}
private:
node* _head;
size_t _size;
};
}
🌈🌈写在最后
我们今天对list的分享就到此结束了
对于这篇博客最精华的部分便是迭代器的实现,迭代器在各种容器中是不可或缺的一部分🚩
🎈感谢能耐心地阅读到此
🎈码字不易,感谢三连
🎈关注博主,我们一起学习、一起进步
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
新闻名称:【C++】list的介绍及模拟实现-创新互联
标题来源:http://hbruida.cn/article/idjgg.html