@TOC
1.list 底层
list为任意位置插入删除的容器,底层为带头双向循环链表
begin() 代表第一个结点,end()代表最后一个结点的下一个
2. list的模拟实现
1. list_node 类设计
template
struct list_node
{
list_node* _next;
list_node* _prev;
T _data;
};
C++中,Listnode作为类名,而next和prev都是类指针,指针引用成员时使用->,而对象引用成员时使用 .
通过显示实例化,将两个类指针指定类型为T
2. list类如何调用类型
Listnode 代表类型
Listnode 代表类名 + 模板参数 才是类型
而_head 以及创建新节点前都需加上类型
3 .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;
}
当我们想要创建一个节点时,需要调用node的构造函数
typedef list_node node ,node是由 list_node 类提供的
list_node(const T& x=T())//list类的构造函数
:_next(nullptr)
, _prev(nullptr)
, _data(x)
{
}
最好在构造函数处提供全缺省,对于内置类型int可以使用0,但对于自定义类型来说就不可以,所以为了满足泛型的要求,使用匿名对象调用默认构造函数
4. 迭代器的实现
若在数组上有一个int类型的指针,解引用是int类型的数据,再++可以加载下一个位置,因为物理空间是连续的
同样若在链表上,解引用类型为 node,再++不能到下一个节点,因为物理空间不连续
所以构造迭代器通过封装节点的指针来进行构造 (后面会讲)
第一个模板参数T
创建一个_list_iterator的类,来实现迭代器功能
template
struct _list_iterator
{
typedef list_node node;
typedef _list_iterator self;
node* _node;
_list_iterator(node* n)
:_node(n)
{
}
T& operator*()//解引用
{
return _node->_data;
}
_list_iterator& operator++()//返回迭代器
{
_node = _node->_next;//指向下一个节点
return *this;
}
bool operator!=(const self&s)
{
return _node != s._node;
}
};
在list类中,调用迭代器实现begin()和end()功能
typedef _list_iterator iterator,
通过typedef 将_list_node类模板定义为iterator
iterator begin()
{
return iterator(_head->_next);//通过匿名对象访问第一个数据
}
iterator end()
{
return iterator(_head);//通过匿名对象访问最后一个数据的下一个
}
在list类中实现begin()和end(),内部调用_list_node类的构造函数
const迭代器
假设第一个代表的是T * ,而第二个代表的 T * const,保护迭代器本身不可以被修改,而我们想要保护迭代器指向的内容不可被修改即 const T*
复制_list_iterator类中的内容,并将名字修改为const_list_iterator
只需修改*operator类型为cosnt T& ,说明解引用后的数据返回不能被修改
template
struct _list_const_iterator
{
typedef list_node node;
typedef _list_const_iterator self;
node* _node;
_list_const_iterator(node* n)
:_node(n)
{
}
const T& operator*()//解引用
{
return _node->_data;
}
self& operator++()//前置++
{
_node = _node->_next;//指向下一个节点
return *this;
}
self& operator++(int)//后置++
{
self ret = *this;
_node = _node->_next;
return ret;
}
self& operator--()//前置--
{
_node = _node->_prev;
return *this;
}
self& operator--(int)//后置--
{
self ret = *this;
_node = _node->_prev;
return ret;
}
bool operator!=(const self& s)//!=
{
return _node != s._node;
}
bool operator==(const self& s)//==
{
return _node == s._node;
}
};
第二个模板参数Ref
迭代器和const迭代器只有 *operator 的返回值不同,
只需在模板中添加一个参数即可使用一个迭代器实现迭代器和const 迭代器的功能
第三个模板参数Ptr
对于内置类型int使用解引用找到对应数据,而自定义类型需使用->寻找下一个节点
AA作为自定义类型,想要找到下一个节点需要使用->,在迭代器中 重载 – >
it->_a1,实际上是 it->->_a1,
it->返回值为AA* ,再通过这个指针使用->指向_a1
但是为了增强可读性,省略了一个->
it->_a1 实际上为 it.operator->()->._a1
对list封装的理解
在不考虑封装的情况下,两者等价
从物理空间上来看,it与pnode都是指向1的地址
pnode作为一个原生指针,解引用指针就会拿到这个地址,找到这个地址指向空间的内容
++pnode,找到下一个节点的地址,但是下一个节点不一定是要的节点
*it 识别成为自定义类型就会调用函数
5. insert
void insert(iterator pos,const T&x)//在pos位置前插入x
{
node* cur = pos._node;
node* prev = cur->_prev;
node* newnode = new node(x);
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
}
6.push_back与 push_front(复用)
两者都可以通过复用 insert的方式实现
void push_back(const T&x)//尾插
{
/*node* tail = _head->_prev;
node* newnode = new node(x);
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;*/
insert(end(), x);
}
void push_front(const T&x)//头插
{
insert(begin(), x);
}
7. erase
void erase(iterator pos)//删除pos位置
{
//头节点不可以删除
assert(pos != end());
node* cur = pos._node;
node* prev = cur->_prev;
node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
}
由于头节点不可以删除,所以使用assert断言的方式
8. pop_back与pop_front (复用)
void pop_back()//尾删
{
erase(--end());
}
void pop_front()//头删
{
erase(begin());
}
9. clear 清空数据
void clear()//清空数据
//但是要注意不要把head清掉
{
iterator it = begin();
while (it != end())
{
it=erase(it);//为了防止迭代器失效设置返回值
//返回值为当前节点的下一个
}
}
迭代器失效是指迭代器所指向的节点失效 即节点被删除了
erase函数执行后,it所指向的节点被删除,因此it无效,在下一次使用it时,必须先给it赋值
为了防止迭代器失效所以使erase设置返回值,返回值为当前节点的下一个
10. 迭代器区间构造
void empty_init()
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
}
template
list(Iterator first, Iterator last)
{
empty_init();
while (first != last)
{
push_back(*first);
++first;
}
}
想要尾插的前提时,需要有头节点的存在,所以设置一个函数对头节点初始化
12. 拷贝构造
传统写法
void empty_init()
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
}
list(const list& It)//拷贝构造 传统写法
{
empty_init();//初始化头节点
for (auto e : It)
{
push_back(e);
}
}
现代写法
void swap(list& tmp)
{
std::swap(_head, tmp._head);
}
list(const list& It)//拷贝构造现代写法
{
empty_init();//将头节点初始化
list tmp(It.begin(), It.end());
swap(tmp);
}
通过调用std中的swap来达到交换的目的
13. 赋值
void swap(list& tmp)
{
std::swap(_head, tmp._head);
}
list& operator=(list It)
{
swap(It);
return *this;
}
参数不可以使用 list &,虽然可以达到赋值的目的,但是It的值也会发生改变
3.完整代码
#include
#include
#include
using namespace std;
namespace yzq
{
template
struct list_node
{
list_node* _next;
list_node* _prev;
T _data;
list_node(const T& x=T())//构造函数
:_next(nullptr)
, _prev(nullptr)
, _data(x)
{
}
};
//迭代器
template
struct _list_iterator
{
typedef list_node node;
typedef _list_iterator 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 ret = *this;
_node = _node->_next;
return ret;
}
self& operator--()//前置--
{
_node = _node->_prev;
return *this;
}
self& operator--(int)//后置--
{
self ret = *this;
_node = _node->_prev;
return ret;
}
bool operator!=(const self&s)//!=
{
return _node != s._node;
}
bool operator==(const self& s)//==
{
return _node == s._node;
}
};
//const迭代器
//template
//struct _list_const_iterator
//{
// typedef list_node node;
// typedef _list_const_iterator self;
// node* _node;
// _list_const_iterator(node* n)
// :_node(n)
// {
// }
// const T& operator*()//解引用
// {
// return _node->_data;
// }
// self& operator++()//前置++
// {
// _node = _node->_next;//指向下一个节点
// return *this;
// }
// self& operator++(int)//后置++
// {
// self ret = *this;
// _node = _node->_next;
// return ret;
// }
// self& operator--()//前置--
// {
// _node = _node->_prev;
// return *this;
// }
// self& operator--(int)//后置--
// {
// self ret = *this;
// _node = _node->_prev;
// return ret;
// }
// bool operator!=(const self& s)//!=
// {
// return _node != s._node;
// }
// bool operator==(const self& s)//==
// {
// return _node == s._node;
// }
//};
template
class list
{
typedef list_node node;
public:
typedef _list_iterator iterator;
typedef _list_iterator const_iterator;//const迭代器
//typedef _list_const_iterator const_iterator;
void empty_init()
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
}
list()//构造函数
{
empty_init();
}
template
list(Iterator first, Iterator last)
{
empty_init();
while (first != last)
{
push_back(*first);
++first;
}
}
//list(const list& It)//拷贝构造
//{
// empty_init();//初始化头节点
// for (auto e : It)
// {
// push_back(e);
// }
//}
void swap(list& tmp)
{
std::swap(_head, tmp._head);
}
list(const list& It)//拷贝构造现代写法
{
empty_init();//将头节点初始化
list tmp(It.begin(), It.end());
swap(tmp);
}
list& operator=(list It)//赋值
{
swap(It);
return *this;
}
~list()//析构函数
{
//将头节点也要释放掉
clear();
delete _head;
_head = nullptr;
}
void clear()//清空数据
//但是要注意不要把head清掉
{
iterator it = begin();
while (it != end())
{
it=erase(it);//为了防止迭代器失效设置返回值
//返回值为当前节点的下一个
}
}
void push_back(const T&x)//尾插
{
/*node* tail = _head->_prev;
node* newnode = new node(x);
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;*/
insert(end(), x);
}
void push_front(const T&x)//头插
{
insert(begin(), x);
}
void insert(iterator pos,const T&x)//在pos位置前插入x
{
node* cur = pos._node;
node* prev = cur->_prev;
node* newnode = new node(x);
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
}
iterator erase(iterator pos)//删除pos位置
{
//头节点不可以删除
assert(pos != end());
node* cur = pos._node;
node* prev = cur->_prev;
node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
return iterator(next);
}
void pop_back()//尾删
{
erase(--end());
}
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);
}
private:
node* _head;
};
/*void test(const list&e)
{
list::const_iterator it = e.begin();
while (it != e.end())
{
cout v;
test(v);
}*/
//void test1()
//{
// list v;
// v.push_back(1);
// v.push_back(2);
// v.push_back(3);
// v.push_back(4);
// list::iterator it= v.begin();
// while (it != v.end())
// {
// cout v;
v.push_back(AA(1, 1));
v.push_back(AA(2, 2));
v.push_back(AA(3, 3));
list::iterator it = v.begin();
while (it != v.end())
{
cout _a1 _a2 v;
// v.push_back(1);
// v.push_back(2);
// v.push_back(3);
// v.push_back(4);// 1 2 3 4
// for (auto e : v)
// {
// cout v;
// v.push_back(1);
// v.push_back(2);
// v.push_back(3);
// v.push_back(4);// 1 2 3 4
// for (auto e : v)
// {
// cout v2(v);
// for (auto e : v2)// 1 2 3 4
// {
// cout v;
v.push_back(1);
v.push_back(2);//v1 = 1 2
list v2;
v2.push_back(5);
v2.push_back(6);//v2=5 6
v2 = v;
for (auto e : v2)// v2=1 2
{
cout
服务器租用托管,机房租用托管,主机租用托管,https://www.e1idc.com