我要评论目录
list的pop_back() push_front() pop_front()
list模拟实现
list节点
首先看节点：list底层是一个带头双向循环链表
template <class t>
class list_node{
public:
t _data;
list_node<t>* _prev;
list_node<t>* _next;
list_node(const t& data)
:_data(data),
_prev(nullptr),
_next(nullptr)
{
}
};template <class t>
class list{
public:
typedef list_node<t> node;
list(){
_head = new node(t());//不能使用0初始化，因为类型不确定
_head->_next = _head;
_head->_prev = _head;
}
private:
node* _head;
};
}list的push_back()函数
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;
//insert(end(), x);
}list的迭代器操作（非const）
list在物理上空间不是连续的，因此不可以像vector一样使用
typedef node* iterator
node* 不符合遍历的行为
list_iterator封装node*
再通过重载运算符控制它的行为
因此这里我们可以使用一个类来封装使用
template <class t>
class list_iterator{
public:
typedef list_node<t> node;
typedef list_iterator self;
//不需要写析构函数，这个节点又不是这个类的
//一个类一般不写析构，也就不需要显示写深拷贝
list_iterator(node* node)
:_node(node)
{
}
//日期类返回一个日期，那么迭代器返回一个迭代器
//++it
self& operator++(){
_node = _node->_next;
return *this;
}
//--it
self& operator--(){
_node = _node->_prev;
return *this;
}
//it++
self operator++(int)//加参数 区分前置后置
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
//it--
self operator--(int){
self tmp(*this);
_node = _node->_prev;
return tmp;
}
t& operator*(){
return _node->_data;
}
bool operator!=(const self& it){
return _node != it._node;
}
bool operator==(const self& it){
return _node == it._node;
}
t* operator->(){
return &(_node->_data);
}
private:
node* _node;
};
注意： t* operator->()的意义，比如下面的例子
struct pos{
int _x;
int _y;
pos(int x = 0,int y = 0)
:_x(x),
_y(y)
{
}
};
nanyi::list<pos> ls2;
ls2.push_back(pos(100,200));
ls2.push_back(pos(300,400));
ls2.push_back(pos(500,600));
nanyi::list<pos>::iterator it1 = ls2.begin();
while (it1 != ls2.end()) {
//cout << (*it1)._x << ":" << (*it1)._y << endl;
// 为了可读性，省略了一个->
cout << it1->_x << ":" << it1->_y << endl;
//cout << it1.operator->()->_row << ":" << it1.operator->()->_col << endl;
++it1;
}
cout << endl;
return 0;list类中
iterator begin(){
//iterator it(_head->_next);
//return it;
return iterator(_head->_next);
}
iterator end(){
return iterator(_head);
}list的迭代器操作（const）
const迭代器不能在普通迭代器前加const修饰，比如这种情况
const迭代器的目标是 迭代器本身可以修改，指定的内容不能修改，类似const t* p
一旦加了不可以使用++it
因此我们重新写一个const类进行封装，我们只需改变解引用即可，使得指向内容不能修改
template <class t>
class const_list_iterator{
public:
typedef list_node<t> node;
typedef const_list_iterator self;
//不需要写析构函数，这个节点又不是这个类的
//一个类一般不写析构，也就不需要显示写深拷贝
const_list_iterator(node* node)
:_node(node)
{
}
//日期类返回一个日期，那么迭代器返回一个迭代器
//++it
self& operator++(){
_node = _node->_next;
return *this;
}
//--it
self& operator--(){
_node = _node->_prev;
return *this;
}
//it++
self operator++(int)//加参数 区分前置后置
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
//it--
self operator--(int){
self tmp(*this);
_node = _node->_prev;
return tmp;
}
const t& operator*(){
return _node->_data;
}
bool operator!=(const self& it){
return _node != it._node;
}
bool operator==(const self& it){
return _node == it._node;
}
const t* operator->(){
return &(_node->_data);
}
private:
node* _node;
}; list类中
const_iterator begin()const
{
return const_iterator(_head->_next);
}
const_iterator end() const
{
return const_iterator(_head);
}代码是没有问题的，但是我们也可以发现，这样非常的冗余 有些函数是没有变化的，确多写了一遍，有没有什么办法能解决这种冗余呢？
他们的区别主要是返回参数不同，返回是否有const对象
因此我们可以增加模版参数，让编译器完成任务
list迭代器const 非const优化
template <class t,class ref,class ptr>
class list_iterator{
public:
typedef list_node<t> node;
typedef list_iterator self;
//不需要写析构函数，这个节点又不是这个类的
//一个类一般不写析构，也就不需要显示写深拷贝
list_iterator(node* node)
:_node(node)
{
}
//日期类返回一个日期，那么迭代器返回一个迭代器
//++it
self& operator++(){
_node = _node->_next;
return *this;
}
//--it
self& operator--(){
_node = _node->_prev;
return *this;
}
//it++
self operator++(int)//加参数 区分前置后置
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
//it--
self operator--(int){
self tmp(*this);
_node = _node->_prev;
return tmp;
}
ref operator*(){
return _node->_data;
}
bool operator!=(const self& it){
return _node != it._node;
}
bool operator==(const self& it){
return _node == it._node;
}
ptr operator->(){
return &(_node->_data);
}
private:
node* _node;
};list的insert()函数
iterator insert(iterator pos , const t& x){
node* cur = pos._node;
node* newnode = new node(x);
node* prev = cur->_prev;
newnode->_next = cur;
newnode->_prev = prev;
prev->_next = newnode;
cur->_prev = newnode;
return iterator(newnode);
}由于不牵涉扩容问题 这里不存在迭代器失效
list的erase()函数
iterator erase(iterator pos){
assert(pos);
node* cur = pos._node;
node* prev = cur->_prev;
node* next = cur->_next;
// prev cur next
prev->_next = next;
next->_prev = prev;
delete cur;
cur = nullptr;
return iterator(next);
}这里存在迭代器失效，因此我们和库里一样返回下一个节点迭代器
list的pop_back() push_front() pop_front()
void pop_back(){
erase(--end());
}
void push_front(const t& x){
insert(begin(), x);
}
void pop_front(){
erase(begin());
}list的clear()函数
void clear(){
auto it = begin();
while (it != end()) {
it = erase(it);
//不能++it,首先会迭代器失效，其次erase会自动返回下一个位置
}
}list的empty()_init函数与构造函数
由于我们经常使用申请头节点，因此我们把头节点封装成一个函数，便于调用
void empty_init(){
_head = new node(t());//不能使用0初始化，因为类型不确定
_head->_next = _head;
_head->_prev = _head;
}
list(){
empty_init();
}list的拷贝构造
如果我们不显示写拷贝构造 ，那么编译器会默认生成一个浅拷贝
浅拷贝生成的ls2，与ls1的地址相同，对ls1操作也会对ls2有影响
因此我们需要显示的写拷贝构造
//拷贝构造
list(const list<t>& ls){
empty_init();
for (const auto& e : ls) {
//范围for不确定类型，加引用
push_back(e);
}
}
list的析构函数
~list(){
clear();
delete _head;
_head = nullptr;
}list的赋值运算符重载
//ls2 = ls1
list<t>& operator=(list<t> ls){
std::swap(_head, ls._head);
return *this;
}
list的initializer_list
可以将花括号内容，直接赋值给对象
list (initializer_list<t> il){
empty_init();
for (const auto& e : il) {
push_back(e);
}
}项目文件
//
// list.hpp
// list
//
// created by 南毅 on 2024/5/28.
//
#include <iostream>
using namespace std;
namespace nanyi {
template <class t>
class list_node{
public:
t _data;
list_node<t>* _prev;
list_node<t>* _next;
list_node(const t& data)
:_data(data),
_prev(nullptr),
_next(nullptr)
{
}
};
template <class t,class ref,class ptr>
class list_iterator{
public:
typedef list_node<t> node;
typedef list_iterator self;
//不需要写析构函数，这个节点又不是这个类的
//一个类一般不写析构，也就不需要显示写深拷贝
list_iterator(node* node)
:_node(node)
{
}
//日期类返回一个日期，那么迭代器返回一个迭代器
//++it
self& operator++(){
_node = _node->_next;
return *this;
}
//--it
self& operator--(){
_node = _node->_prev;
return *this;
}
//it++
self operator++(int)//加参数 区分前置后置
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
//it--
self operator--(int){
self tmp(*this);
_node = _node->_prev;
return tmp;
}
ref operator*(){
return _node->_data;
}
bool operator!=(const self& it){
return _node != it._node;
}
bool operator==(const self& it){
return _node == it._node;
}
ptr operator->(){
return &(_node->_data);
}
public:
node* _node;
};
//template <class t>
//class const_list_iterator{
//public:
// typedef list_node<t> node;
// typedef const_list_iterator self;
//
// //不需要写析构函数，这个节点又不是这个类的
// //一个类一般不写析构，也就不需要显示写深拷贝
// const_list_iterator(node* node)
// :_node(node)
// {
//
// }
//
// //日期类返回一个日期，那么迭代器返回一个迭代器
// //++it
// self& operator++(){
// _node = _node->_next;
// return *this;
// }
// //--it
// self& operator--(){
// _node = _node->_prev;
// return *this;
// }
// //it++
// self operator++(int)//加参数 区分前置后置
// {
// self tmp(*this);
// _node = _node->_next;
// return tmp;
// }
// //it--
// self operator--(int){
// self tmp(*this);
// _node = _node->_prev;
// return tmp;
// }
//
//
// const t& operator*(){
// return _node->_data;
// }
//
// bool operator!=(const self& it){
// return _node != it._node;
// }
//
// bool operator==(const self& it){
// return _node == it._node;
// }
//
// const t* operator->(){
// return &(_node->_data);
// }
//private:
// node* _node;
//
//};
template <class t>
class list{
public:
typedef list_node<t> node;
typedef list_iterator<t,t&,t*> iterator;
typedef list_iterator<t,const t&,const t*> const_iterator;
//typedef const_list_iterator<t> const_iterator;
void empty_init(){
_head = new node(t());//不能使用0初始化，因为类型不确定
_head->_next = _head;
_head->_prev = _head;
}
list(){
empty_init();
}
void clear(){
auto it = begin();
while (it != end()) {
it = erase(it);
//不能++it,首先会迭代器失效，其次erase会自动返回下一个位置
}
}
//拷贝构造
list(const list<t>& ls){
empty_init();
for (const auto& e : ls) {
push_back(e);
}
}
//析构
~list(){
clear();
delete _head;
_head = nullptr;
}
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;
insert(end(), x);
}
void pop_back(){
erase(--end());
}
void push_front(const t& x){
insert(begin(), x);
}
void pop_front(){
erase(begin());
}
iterator begin(){
return iterator(_head->_next);
}
iterator end(){
return iterator(_head);
}
const_iterator begin()const
{
return const_iterator(_head->_next);
}
const_iterator end() const
{
return const_iterator(_head);
}
iterator insert(iterator pos , const t& x){
node* cur = pos._node;
node* newnode = new node(x);
node* prev = cur->_prev;
newnode->_next = cur;
newnode->_prev = prev;
prev->_next = newnode;
cur->_prev = newnode;
return iterator(newnode);
}
iterator erase(iterator pos){
node* cur = pos._node;
node* prev = cur->_prev;
node* next = cur->_next;
// prev cur next
prev->_next = next;
next->_prev = prev;
delete cur;
cur = nullptr;
return iterator(next);
}
//ls2 = ls1
list<t>& operator=(list<t> ls){
std::swap(_head, ls._head);
return *this;
}
list (initializer_list<t> il){
empty_init();
for (const auto& e : il) {
push_back(e);
}
}
public:
node* _head;
};
}
4.list与vector的对比
vector与list都是stl中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：
发表评论