hao123网址之家官网,seo专业技术培训,网站开发看书,thinkphp网站开发技术目录 list的基本介绍
list模拟实现
一.创建节点
二.迭代器
1.模版参数
2.迭代器的实现#xff1a;
a. !
b.
c. --
d. *指针
e.引用
整体iterator (与const复用)#xff1a;
三.功能实现
1.模版参数
2.具体功能实现#xff1a;
2.1 构造函数
2.2 begi…目录 list的基本介绍
list模拟实现
一.创建节点
二.迭代器
1.模版参数
2.迭代器的实现
a. !
b.
c. --
d. *指针
e.引用
整体iterator (与const复用)
三.功能实现
1.模版参数
2.具体功能实现
2.1 构造函数
2.2 begin() end()
print_list打印
2.3插入
insert任意位置插入
push_back 尾插 push_front前插
2.4 删除
erase任意位置删除
pop_back 头删 pop_front尾删
2.5 拷贝构造 赋值操作符
2.6 clear() 析构函数
代码示例
Test.cpp
list.h list的基本介绍
list本质上是一个带头双向循环链表列表是一种用于存储一组元素的数据结构元素按照插入的顺序排列。它允许动态地添加和删除元素可以重复存储相同的值。列表提供了对元素的插入、删除、访问和遍历等常用操作。
列表是序列容器允许在序列内的任何位置插入和擦除操作并在两个方向上进行迭代。
列表容器被实现为双链接列表双链接列表可以将它们所包含的每个元素存储在不同的和不相关的存储位置中。顺序通过与前面元素的链接和后面元素的链接的关联在内部保持。
与其他序列容器相比列表和前向列表的主要缺点是它们无法通过位置直接访问元素 例如要访问列表中的第六个元素必须从已知位置如开始或结束迭代到该位置该位置之间的距离需要线性时间。它们还会消耗一些额外的内存来保持与每个元素相关联的链接信息这可能是大量小元素列表的一个重要因素。
若要查看双向循环链表相关知识→数据结构线性表之-循环双向链表(万字详解)_数据结构循环双链表概念-CSDN博客
list模拟实现
一.创建节点
template class T//模版
struct list_node
{list_nodeT *_prev;//前一节点list_nodeT *_next;//后一节点T _data;
// 构造函数创建链表list_node(const T x T()) // 用匿名对象做缺省值(调用默认构造)以存储其他类型的元素: _next(nullptr), _prev(nullptr), _data(x){}
};
二.迭代器
1.模版参数
template class T, class Ref, class Ptr class T:表示元素类型,为了应对要接收不同类型的数据 class Ref:引用类型参数模版Ref用于提供对迭代器所指向元素的引用 class Ptr指针类型参数模版Ptr用于提供对迭代器所指向元素的指针。
后面会提到RefPtr作用请仔细阅读哦
2.迭代器的实现
基本模版
template class T, class Ref, class Ptr
struct __list_iterator
{//重新命名typedef list_nodeT node; typedef __list_iteratorT, Ref, Ptr self;node *_node;//指向列表节点的指针用于追踪迭代器的当前位置。
//构造函数接受一个指向列表节点的指针并将其作为初始位置给 _node。__list_iterator(node *n): _node(n){}
};
这个结构体的作用是提供列表的迭代功能它可以被用于遍历列表中的元素并对元素进行访问和操作。 const T表示迭代器所指向元素的引用类型而const T*表示迭代器所指向元素的指针类型。 这样定义迭代器的目的是为了在const成员函数中使用该迭代器并保证在遍历列表时不会修改列表中的元素
参考
listint::iterator it lt.begin();
//__list_itreator后续被重命名为iterator
a. !
bool operator!(const self s)
{return _node ! s._node;
}
b.
bool operator(const self s)
{return _node s._node;
}
c. --
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;
}
d. *指针
重载了解引用运算符(*)返回 _node-_data 的引用即迭代器所指向的元素
Ref operator*()//加const不能修改数据
{return _node-_data;
}
e.引用
重载了箭头运算符(-)返回 _node-_data 的指针即迭代器所指向元素的指针。
Ptr operator-()
{return (_node-_data); // 取地址
} Ref与Ptr的定义在class list中进行定义 整体iterator (与const复用)
template class T, class Ref, class Ptr
struct __list_iterator
{typedef list_nodeT node;typedef __list_iteratorT, Ref, Ptr self;node *_node;__list_iterator(node *n): _node(n){}Ref operator*(){return _node-_data;}Ptr operator-(){return (_node-_data); // 取地址}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;}
};
三.功能实现
1.模版参数 template class T
class list
{typedef list_nodeT node;public://iterator和const_iterator都是公用接口typedef __list_iteratorT, T , T * iterator;typedef __list_iteratorT, const T , const T * const_iterator;private://头节点node *_head; // ListNodeT是类型 ListNode是类名
};
2.具体功能实现
2.1 构造函数
为了后续操作的方便将初始化链表代码写在另一个函数里
void empty_init()
{_head new node;_head-_next _head;_head-_prev _head;
}
list()
{empty_init();
}
2.2 begin() end()
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);
}
test:通过迭代器依次打印出元素
listint::iterator it lt.begin();
while (it ! lt.end())
{cout *it ;it;
}
cout endl;
我们将迭代器遍历封装到一个函数内
print_list打印
void print_list(const listT lt)
{cout ---list--- endl;// listint::const_iterator it lt.begin();listint::const_iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl ---list--- endl;
}
2.3插入
insert任意位置插入
void insert(iterator pos, const T x)
{node *cur pos._node; // .访问pos内的成员变量_nodenode *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;
}
push_back 尾插 push_front前插
void push_back(const T x)
{insert(end(), x);
}
void push_front(const T x)
{insert(begin(), x);
}
test:
void test_list3()
{listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);
listint::iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;
it lt.begin();listint::iterator pos lt.begin();pos;lt.insert(pos, 20);
lt.print_list(lt);
cout endl;
}
2.4 删除
erase任意位置删除
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);
}
pop_back 头删 pop_front尾删
void pop_back()
{erase(--end());
}
void pop_front()
{erase(begin());
}
test:
void test_list4()
{listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.print_list(lt);cout endl;lt.push_back(100);lt.push_front(99);lt.print_list(lt);cout endl;
lt.pop_back();lt.pop_front();lt.print_list(lt);cout endl;
} 2.5 拷贝构造 赋值操作符
swap交换函数
void swap(listT temp)
{std::swap(_head, temp._head);
}
当调用swap函数时[例子lt2拷贝lt1调用swap时]调用拷贝构造将lt1进行拷贝再交换到lt2
list
list(const listT lt)
{empty_init();//创建头节点listT temp(lt.begin(), lt.end());swap(temp);
}
赋值操作数
// lt3lt2
// 不能使用而是传值调用拷贝构造,拷贝lt2赋值给lt3
listT operator(const listT lt)//const listT lt
{swap(lt);return *this;
}
test:
void test_list6()
{listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.print_list(lt);cout endl;
// listint lt2(lt);// lt2.print_list(lt2);// cout endl;listint lt2 lt;lt2.print_list(lt2);lt.print_list(lt);
}
2.6 clear() 析构函数
clear清除头节点以外的数据
void clear()
{iterator it begin();while (it ! end())it erase(it); // erase(it);//后置返回的是前一个的拷贝不会失效
}
test:
void test_list5()
{listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.print_list(lt);cout endl;
lt.clear();lt.push_back(20);
lt.print_list(lt);
}
析构
~list()
{clear();delete _head;_head nullptr;
}
代码示例
Test.cpp
#include list.hint main()
{wzf::test_list6();return 0;
}
list.h
#pragma once
#include iostream
#include assert.h
using namespace std;namespace wzf
{// 节点template class Tstruct list_node{list_nodeT *_prev;list_nodeT *_next;T _data;// 构造函数创建链表list_node(const T x T()) // 用匿名对象做缺省值(调用默认构造)以存储收其他类型的元素: _next(nullptr), _prev(nullptr), _data(x){}};// 迭代器// // 1.iterator// template class T// struct __list_iterator// {// typedef list_nodeT node;// typedef __list_iteratorT self;// node *_node;// __list_iterator(node *n)// : _node(n)// {// }// T operator*()// {// return _node-_data;// }// 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;// }// };// // 2.const_iterator// template class T// struct __list_const_iterator// {// typedef list_nodeT node;// typedef __list_const_iteratorT self;// node *_node;// __list_const_iterator(node *n)// : _node(n)// {// }// const T operator*() // 与1区别的地方加const不能修改数据// {// return _node-_data;// }// 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;// }// };// template class T,class Ref// struct __list_iterator// {// typedef list_nodeT node;// typedef __list_iteratorT,Ref self;// node *_node;// __list_iterator(node *n)// : _node(n)// {// }// Ref operator*()// {// return _node-_data;// }// 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;// }// };// 迭代器template class T, class Ref, class Ptrstruct __list_iterator{typedef list_nodeT node;typedef __list_iteratorT, Ref, Ptr self;node *_node;__list_iterator(node *n): _node(n){}Ref operator*(){return _node-_data;}Ptr operator-(){return (_node-_data); // 取地址}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 T表示迭代器所指向元素的引用类型而const T*表示迭代器所指向元素的指针类型。这样定义迭代器的目的是为了在const成员函数中使用该迭代器并保证在遍历列表时不会修改列表中的元素*/};template class Tclass list{typedef list_nodeT node;public:typedef __list_iteratorT, T , T * iterator;typedef __list_iteratorT, const T , const T * const_iterator;// typedef __list_const_iteratorT const_iterator;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);}void empty_init(){_head new node;_head-_next _head;_head-_prev _head;}list(){empty_init();}// 构造函数 迭代器区间template class Iteratorlist(const Iterator first, const Iterator last){empty_init(); // 创建头节点for (Iterator it first; it ! last; it)push_back(*it);}void swap(listT temp){std::swap(_head, temp._head);}// 拷贝构造// lt2(lt1)// list(const listT lt)// {// empty_init();// const_iterator it lt.begin();// while (it ! lt.end())// {// push_back(*it);// it;// }// }list(const listT lt){empty_init();listT temp(lt.begin(), lt.end());swap(temp);}// 赋值操作符// lt3lt2// 不能使用而是传值调用拷贝构造,拷贝lt2赋值给lt3listT operator(const listT lt){swap(lt);return *this;}~list(){clear();delete _head;_head nullptr;}// 清除头节点以外的数据void clear(){iterator it begin();while (it ! end())it erase(it); // erase(it);//后置返回的是前一个的拷贝不会失效}// void push_back(const T x)// {// node *tail _head-_prev;// node *new_node new node(x);// tail-_next new_node;// new_node-_prev tail;// new_node-_next _head;// _head-_prev new_node;// }void push_back(const T x){insert(end(), x);}void push_front(const T x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}void print_list(const listT lt){cout ---list--- endl;// listint::const_iterator it lt.begin();listint::const_iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl ---list--- endl;}void insert(iterator pos, const T x){node *cur pos._node; // .访问pos内的成员变量_nodenode *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);}/*在该函数的最后一行返回了一个迭代器对象 iterator(next)。这是因为在 C STL 中通常情况下删除一个元素后我们希望返回删除元素的下一个位置作为新的迭代器。直接返回 next 的话可能会暴露内部实现细节使得用户可以直接操作指针 next可能导致潜在的问题。为了隐藏底层指针的细节通常会将其封装在迭代器对象中返回。因此返回 iterator(next) 的方式可以提供更好的封装性和安全性使用户能够使用迭代器对象来操作返回的下一个位置而不需要直接访问底层的指针。这也符合 C STL 设计的一般原则即通过迭代器提供统一的接口隐藏底层的具体实现细节。*/private:node *_head; // ListNodeT是类型 ListNode是类名};void test_list1(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);listint::iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;lt.print_list(lt);}struct AA{int _a1;int _a2;AA(int a1 0, int a2 0): _a1(a1), _a2(a2){}};void test_list2(){listAA lt;lt.push_back(AA(1, 2));lt.push_back(AA(3, 4));lt.push_back(AA(5, 6));listAA::iterator it lt.begin();while (it ! lt.end()){cout it-_a1 it._node-_data._a2 endl;cout it.operator-()-_a1 it.operator-()-_a2 endl;cout it.operator-() endl endl; // 地址值it;}}void test_list3(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);listint::iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;it lt.begin();listint::iterator pos lt.begin();pos;lt.insert(pos, 20);lt.print_list(lt);cout endl;}void test_list4(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.print_list(lt);cout endl;lt.push_back(100);lt.push_front(99);lt.print_list(lt);cout endl;lt.pop_back();lt.pop_front();lt.print_list(lt);cout endl;}void test_list5(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.print_list(lt);cout endl;lt.clear();lt.push_back(20);lt.print_list(lt);}void test_list6(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.print_list(lt);cout endl;// listint lt2(lt);// lt2.print_list(lt2);// cout endl;listint lt2 lt;lt2.print_list(lt2);lt.print_list(lt);}
}
