list底层实现
list和vector都是容器，只不过他们的存储结构不同，vector实际底层结构是顺序表，支持随机访问。list的底层结构带头双向链表，不支持随机访问。 但list的底层实现不同，因为他是链表的缘故，所它的节点和迭代器必须在外在创建类来嵌套 vector的insert和erase函数都有迭代器失效的问题，而list的只有erase函数有迭代器失效的问题_list_node
首先是一个用来创建节点的类 一个节点有他的前后指针，和他存储的值 此类还有进行初始话的操作 //创建 构造节点的类
struct _list_node
{
_list_node<T>* next;
_list_node<T>* prve;
T _val;
_list_node(const T& val=T())
:next(nullptr)
, prve(nullptr)
,_val(val)
{
}
};
_list_iterator
其次是创建迭代器的类 记住 vector的迭代器本质上可以认为是一个指针，而list的迭代器不同，它是以链表内的节点区分的。跟vector的区别很大 1.创建一个迭代器，必然要知道一个节点 2.因为迭代器分为const和非const的版本 但如果再创建一个数据大部分相同的，但只是加几个const的类，这对复用性非常差，所以我们根据源码来修改 主要思路，就是通过模版类型，和外面的名字不同，传过来的类型就不同。 比如 我用的是非const 那么Ref和Ptr就会传来非const的版本 如果我们用的是const 那么Ref和Ptr就会传来const的版本 3.要用的节点放到函数来赋给能让我们使用的节点 self本质就是为了方便，整个名太长，直接重命名为短的名。 这里记住解释 解引用的 本质将本体传过来，然后返回他里面存储的值，他的值时他的类型，并且需要修改，就是T& 而*是不需要传另外的值的，所以*是不需要参数的 ->符合，本质是传出去它存储的值的地址。 也就是解引用传出来的值，在加上指针。而指针是用指针传出去，而它是模版类型 也就是T* 前置++符号重载，记住这里的++，--他们都是用来对迭代器的向前，后移动，而不是改变他们的值，所以他们的返回值 也是迭代器， 也就是self 后置++符合重载，本质就是返回不先++，而是返回它自己的值后，再++，但函数是不允许return后再进行操作的，所以可以创建一个临时的迭代器，用来存储现在的迭代器，然后返回临时的迭代器。（后置++不用引用的原因，是因为返回的是临时的迭代器，返回后，函数结束，这个临时迭代器的生命周期也结束了，如果你传的是引用，再对这个已经释放的临时迭代器进行操作时，会造成非法访问地址，所以后置++不用引用返回）而本体迭代器直接进行++即可 前置后置++ 都是用next向后移动到下一个节点 前置--和后置--的操作和前置++和后置--的解释是一样的，只不过一个向前一个向后的区别而已。 符号重载：只要这个符合它是对自己本身操作的，那么这个函数是不需要进行传参的！ ！=符合重载，是本身与其他迭代器比较，所以传参的类型也是迭代器类型 传参的本质，是要看它传过来的到底是迭代器还是值还是他的节点！ 操作很简单，就是对它的节点进行比较即可。 ==符合重载也是一样，只不过操作内容相反而已 template<class T , class Ref , class Ptr>//Ref Ptr 是可以很好的区分const与非const版本
//通过重命名 通过不同的命名 传过来的参数是不同的
struct _list_iterator
{
typedef _list_node<T> Node;
//typedef _list_iterator<T, T&, T*> self;//这里要传 Ref 和 Ptr 不然const版本没有函数可以返回
typedef _list_iterator<T, Ref, Ptr> self;//这里要传 Ref 和 Ptr 不然const版本没有函数可以返回
Node* _node;//接收节点
_list_iterator(Node* node)
:_node(node)
{}
Ref operator*()//*重载 不需要传参数
{
return _node->_val;
}
Ptr operator->()
{
//return &(operaotr*());
return &_node->_val;
}
self& operator++()//++后 返回的是迭代器类型 因为node是*类型 所以_list_iterator不能加引用
{
_node = _node->next;
return *this;
}
self operator++(int)//++后 返回的是迭代器类型 因为node是*类型 所以_list_iterator不能加引用
{
self tmp(*this);
_node = _node->next;
return tmp;
}
self& operator--()//++后 返回的是迭代器类型 因为node是*类型 所以_list_iterator不能加引用
{
_node = _node->prve;
return _node;
}
self operator--(int)//++后 返回的是迭代器类型 因为node是*类型 所以_list_iterator不能加引用
{
self tmp(*this);
_node = _node->prve;
return tmp;
}
bool operator!=(const self& it)//传过来的是迭代器类型
{
return _node != it._node;
}
bool operator==(const self& it)
{
return _node == it.node;
}
};
list本体
你要使用上面的两个类（节点，迭代器） 那么必须对他们重命名 即可使用 （本质上也可以不重命名，只不过名字很长，写起来会很麻烦） begin和end的两个版本 const和非const版本。 记住，这是有哨兵位的，所以begin返回的是哨兵的下一个，而end是最后一个节点的下一个，也就是head cbegin和cend是自创，非官方库内，这两个是直接使用const的版本，如果是const_begin它必须用函数传参，让它的节点为const才能使用const （不然编译器会默认稳非const版本）而我的是可以直接使用const版本的 //双向迭代器
//head是哨兵位 头是哨兵位的下一个 位是哨兵位的上一个
//接受是哨兵位
//cbegin和cend 是自创 非官方
const_iterator cbegin() const
{
return const_iterator(head->next);//返回的是迭代器 所以要创建迭代器再返回
}
const_iterator cend() const
{
return const_iterator(head);//返回的是迭代器 所以要创建迭代器再返回
}
const_iterator begin() const
{
return const_iterator(head->next);//返回的是迭代器 所以要创建迭代器再返回
}
const_iterator end() const
{
return const_iterator(head);//返回的是迭代器 所以要创建迭代器再返回
}
iterator begin()
{
return iterator(head->next);//返回的是迭代器 所以要创建迭代器再返回
}
iterator end()
{
return iterator(head);//返回的是迭代器 所以要创建迭代器再返回
}
list的无参构造函数 只需要把当前节点初始化即可（根据穿进来的节点初始化，不是头结点！！）
list()
{
head = new node();
head->next = head;
head->prve = head;
}
list的有参构造，用迭代器范围构造 用迭代器的构造，都是要用模版类型
template<class K>
list(K cur, K end)
{
empty_into();
while (cur != end)
{
push_back(*cur);
++cur;
}
}
empyt_into 用来初始化节点
void empty_into()
{
head = new node();
head->next = head;
head->prve = head;
}
swap 交换函数 这个函数是用来交换的，交换两个链表，实际上只需要交换他的哨兵位，就可以。
void swap(list<T>& lv)//交换数据时 不允许加const！！！
{
std::swap(head, lv.head);
}
拷贝构造 传统写法 初始化后，用范围for一个一个的节点拷贝到当前节点内
////传统写法
//list(const list<T>& lv)
//{
// empty_into();//初始化
// for (auto e : lv)
// {
// push_back(e);
// }
//}
拷贝构造 现代写法 初始化 创建一个对象，也就是新的链表，去复用构造函数，构造出一个新的链表，然后让当前链表与临时对象交换头节点即可
//现代写法
list(const list<T>& lv)
{
empty_into();//初始化
list<T> tmp(lv.begin(), lv.end());
swap(tmp);
}
=符号重载 现代写法 不用引用，直接交换他们的数据，并不改变外面的数据 就可以直接得到外面的数据，返回时，时返回这个节点 就是*this
list<T>& operator=(list<T> lv)
{
swap(lv);
return *this;
}
insert
在某个位置插入某个值
因为这是节点，不存在下标，所以是传迭代器
但这个insert是不存在迭代器失效的问题的
首先创建一个新节点，用来存储要传进来的数据
然后我们用一个新节点记录来存储这个迭代器的位置。
然后用这个节点找到它的前一个节点
接下来就是链接
这个函数为什么不会存在迭代器失效？
因为这个函数是用指针链接，其次他们是没有直接改变pos，pos只是给他们提供位置，内部数据时不会对pos改动的，所以pos不会失效，其次list的结构问题，要插入节点，是创建这个节点的新空间，也就是新地址，不想vector的扩容，是整个顺序表都搬到另一个新空间，所以pos是不存在失效的。本质就是pos并未改动
void insert(iterator pos, const T& val)
{
node* newcapacity = new node(val);
node* cur = pos._node;
node* prve = cur->prve;
//prve newcapacity pos
prve->next = newcapacity;
newcapacity->prve = prve;
newcapacity->next = cur;
cur->prve = newcapacity;
}
erase
它要删除某个位置，list的结构是链表，所以传的也是迭代器，不存在下标。
但pos不能删除end （end就是head哨兵位）
用一个节点接收这个迭代器的位置,然后利用这个号节点找到它的前后，链接
最后删除这个节点 这时候，这节点是被删除的，也就是pos指向的节点，被删除了，那么pos就指向的个随机值，那你下次++时，指向随机值的迭代器的它++，你能确定它++到哪吗？？所以这个迭代器就是失效了，而刚才我们已经有两个节点存储了刚才节点的前后的节点，那么我们的迭代器就更新为删除节点的下一个节点的位置即可，也就是erase删除后，自动++了。
就是返回的是迭代器，因为要对外面的迭代器更新，所以返回值是迭代器类型，但我们存储的是节点啊，所以这个节点要传到迭代器内初始化为迭代器类型，才能返回。
iterator erase(iterator pos)//返回的是迭代器 用于更新迭代器
{
assert(pos != end());
node* poos = pos._node;
node* prve = poos->prve;
node* cur = poos->next;
prve->next = cur;
cur->prve = prve;
delete poos;
return iterator(cur);
}
push_back
实际就是插入到最后的位置，就可以直接复用insert。最后的位置就是head的上一个位置就是最后的位置
void pop_back()
{
erase(head->prve);
}
push_front
在最开始的位置插入，迭代器就是begin的位置 复用insert即可
void push_front(const T& val)
{
insert(begin(), val);
}
pop_back
在最后的位置删除，复用erase即可
void pop_back()
{
erase(head->prve);
}
pop_front
在最前的位置删除，复用erase即可
void pop_front()
{
erase(begin());
}
clear 置空 复用erase全部删除 因为erase删除后，会自动++ 所以不用再外部++ 但没删除时，是需要我们手动++
//置空
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
~list 析构 先复用clear删除全部数据 再删除他的头结点的数据并置空
//析构
~list()
{
clear();
delete[] head;
head = nullptr;
}
源码
#pragma once
#include<list>
#include<iostream>
#include<assert.h>
using namespace std;
namespace moxuan
{
template<class T>
//创建 构造节点的类
struct _list_node
{
_list_node<T>* next;
_list_node<T>* prve;
T _val;
_list_node(const T& val=T())
:next(nullptr)
, prve(nullptr)
,_val(val)
{
}
};
template<class T , class Ref , class Ptr>//Ref Ptr 是可以很好的区分const与非const版本
//通过重命名 通过不同的命名 传过来的参数是不同的
struct _list_iterator
{
typedef _list_node<T> Node;
//typedef _list_iterator<T, T&, T*> self;//这里要传 Ref 和 Ptr 不然const版本没有函数可以返回
typedef _list_iterator<T, Ref, Ptr> self;//这里要传 Ref 和 Ptr 不然const版本没有函数可以返回
Node* _node;//接收节点
_list_iterator(Node* node)
:_node(node)
{}
Ref operator*()//*重载 不需要传参数
{
return _node->_val;
}
Ptr operator->()
{
//return &(operaotr*());
return &_node->_val;
}
self& operator++()//++后 返回的是迭代器类型 因为node是*类型 所以_list_iterator不能加引用
{
_node = _node->next;
return *this;
}
self operator++(int)//++后 返回的是迭代器类型 因为node是*类型 所以_list_iterator不能加引用
{
self tmp(*this);
_node = _node->next;
return tmp;
}
self& operator--()//++后 返回的是迭代器类型 因为node是*类型 所以_list_iterator不能加引用
{
_node = _node->prve;
return _node;
}
self operator--(int)//++后 返回的是迭代器类型 因为node是*类型 所以_list_iterator不能加引用
{
self tmp(*this);
_node = _node->prve;
return tmp;
}
bool operator!=(const self& it)//传过来的是迭代器类型
{
return _node != it._node;
}
bool operator==(const self& it)
{
return _node == it.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;//根据名字不同 传过去的const和非const不同
//两个版本的T 都不允许加const 因为 构造时 是T 而传给迭代器时 是const T 是不同的，无法相互交融，报错
//通过重命名 通过不同的命名 传过来的参数是不同的
//双向迭代器
//head是哨兵位 头是哨兵位的下一个 位是哨兵位的上一个
//接受是哨兵位
//cbegin和cend 是自创 非官方
const_iterator cbegin() const
{
return const_iterator(head->next);//返回的是迭代器 所以要创建迭代器再返回
}
const_iterator cend() const
{
return const_iterator(head);//返回的是迭代器 所以要创建迭代器再返回
}
const_iterator begin() const
{
return const_iterator(head->next);//返回的是迭代器 所以要创建迭代器再返回
}
const_iterator end() const
{
return const_iterator(head);//返回的是迭代器 所以要创建迭代器再返回
}
iterator begin()
{
return iterator(head->next);//返回的是迭代器 所以要创建迭代器再返回
}
iterator end()
{
return iterator(head);//返回的是迭代器 所以要创建迭代器再返回
}
list()
{
head = new node();
head->next = head;
head->prve = head;
}
void insert(iterator pos, const T& val)
{
node* newcapacity = new node(val);
node* cur = pos._node;
node* prve = cur->prve;
//prve newcapacity pos
prve->next = newcapacity;
newcapacity->prve = prve;
newcapacity->next = cur;
cur->prve = newcapacity;
}
iterator erase(iterator pos)//返回的是迭代器 用于更新迭代器
{
assert(pos != end());
node* poos = pos._node;
node* prve = poos->prve;
node* cur = poos->next;
prve->next = cur;
cur->prve = prve;
delete poos;
return iterator(cur);
}
//找到尾节点
//创建新节点
//链接
void push_back(const T& val)
{
////找节点和创建节点
//node* tail = head->prve;
//node* newnode = new node(val);
////链接
//tail->next = newnode;
//newnode->prve = tail;
//newnode->next = head;
//head->prve = newnode;
insert(end()--, val);
}
void push_front(const T& val)
{
insert(begin(), val);
}
void pop_back()
{
erase(head->prve);
}
void pop_front()
{
erase(begin());
}
//置空
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
//析构
~list()
{
clear();
delete[] head;
head = nullptr;
}
void empty_into()
{
head = new node();
head->next = head;
head->prve = head;
}
template<class K>
list(K cur, K end)
{
empty_into();
while (cur != end)
{
push_back(*cur);
++cur;
}
}
void swap(list<T>& lv)//交换数据时 不允许加const！！！
{
std::swap(head, lv.head);
}
////传统写法
//list(const list<T>& lv)
//{
// empty_into();//初始化
// for (auto e : lv)
// {
// push_back(e);
// }
//}
//现代写法
list(const list<T>& lv)
{
empty_into();//初始化
list<T> tmp(lv.begin(), lv.end());
swap(tmp);
}
list<T>& operator=(list<T> lv)
{
swap(lv);
return *this;
}
private:
node* head;//创建头节点
};
测试代码
void test1()
{
list<int> lv;
lv.push_back(1);
lv.push_back(2);
lv.push_back(3);
lv.push_back(4);
lv.push_back(5);
lv.push_back(6);
list<int>::iterator it = lv.begin();
while (it != lv.end())
{
cout << *it << " ";
++it;
}
}
struct AA
{
AA(int a=0, int b=0) // 传的是结构体 类型必须有缺省值
:a(a)
, b(b)
{
}
int a;
int b;
};
void print_list(const list<int>& lv)
{
list<int>::const_iterator it2 = lv.begin();
while (it2 != lv.end())
{
//*it2 = 10;
cout << *it2 << " ";
++it2;
}
cout << endl;
}
void test2()
{
list<AA> lb; //传的是结构体 类型必须有缺省值
lb.push_back(AA(1, 1));
lb.push_back(AA(2, 2));
lb.push_back(AA(3, 3));
lb.push_back(AA(4, 4));
list<AA>::iterator it1 = lb.begin();
while (it1 != lb.end())
{
cout << it1->a << " " << it1->b << endl;
++it1;
}
list<int> lv;
lv.push_back(1);
lv.push_back(2);
lv.push_back(3);
lv.push_back(4);
//想调用const版本 需要对这个lv成员传参 定义成const 才能调用得到 不然begin是默认为非const版本
//也可以直接写cbegin cend 让他不用传参 也可以直接调用const版本 （自创 非官方）
list<int>::const_iterator it2 = lv.cbegin();
while (it2 != lv.cend())
{
//*it2 = 10;
cout << *it2 << " ";
++it2;
}
cout << endl;
print_list(lv);
}
void test3()
{
list<int> ls;
ls.push_back(1);
ls.push_back(2);
ls.push_back(3);
ls.push_back(4);
list<int>::iterator it = ls.begin();
//while (it != ls.end())
//{
// if (*it % 2 == 0)
// {
// ls.insert(it, 100);
// }
// ++it;
//}
//for (auto e : ls)
//{
// cout << e << " ";
//}
//cout << endl;
//list<int>::iterator it1 = ls.begin();
//while (it1 != ls.end())
//{
// if (*it1 % 2 == 0)
// {
// it1=ls.erase(it1);//erase会造成迭代器失效 所以需要更新迭代器 并且迭代器返回的是pos的下一个位置，所以不用++
// }
// else
// {
// ++it1;
// }
//}
ls.push_front(1);
ls.push_front(2);
ls.push_front(3);
ls.push_front(4);
ls.pop_back();
ls.pop_back();
ls.pop_front();
ls.pop_front();
for (auto e : ls)
{
cout << e << " ";
}
}
void test4()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
list<int> iv(lt);
list<int> io(iv.begin(), iv.end());
list<int> ip = iv;
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
for (auto e : io)
{
cout << e << " ";
}
cout << endl;
for (auto e : iv)
{
cout << e << " ";
}
cout << endl;
for (auto e : ip)
{
cout << e << " ";
}
cout << endl;
}