C++--list
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
前言
这篇文章对于理解封装是非常有帮助的list的底层是双向链表结构我们在学习数据结构是就已经学过了双向链表双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。因为list独特的结构在模拟实现的时候就会发现为了list接口更好为用户使用更多是通过封装。
这篇文章会开始从list的使用开始看完list的使用之后你会发现跟string和vector的接口使用几乎是一样的虽然他们的使用是一样的他的接口都是一样的但是后面我们通过对接口的模拟实现你就会发现是不一样到底哪里不一样就需要你的深入观看--卖个关子。总的来说这篇文章就是来展示迭代器的魅力和模板的魅力。
目录
一、list的介绍及使用
1.1list的介绍
list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。因为list的底层是双向链表结构。
list与forward_list非常相似最主要的不同在于forward_list是单链表只能朝前迭代已让其更简单高效。与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率更好。
与其他序列式容器相比list和forward_list最大的缺陷是不支持任意位置的随机访问比如要访问list的第6个元素必须从已知的位置(比如头部或者尾部)迭代到该位置在这段位置上迭代需要线性的时间开销list还需要一些额外的空间以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)。
带头循环双向链表
1.2.list的使用
对于list的使用来说list中的接口比较多实则是与vector差不多的接下来我们就来简单的演示掌握list正确的使用然后再去深入研究背后的原理已达到可扩展的能力。
1.2.1 list的构造
| 构造函数 (constructor) | 接口说明 |
| list (size_type n, const value_type& val = value_type()) | 构造的list中包含n个值为val的元素 |
| list() | 构造空的list |
| list (const list& x) | 拷贝构造函数 |
| list (InputIterator first, InputIterator last) | 用[first, last)区间中的元素构造list |
例
void TestList1()
{
list<int> l1; // 构造空的l1
list<int> l2(4, 100); // l2中放4个值为100的元素
list<int> l3(l2.begin(), l2.end()); // 用l2的[begin(), end()左闭右开的区间构造l3
list<int> l4(l3); // 用l3拷贝构造l4
// 以数组为迭代器区间构造l5
int array[] = { 16, 2, 77, 29 };
list<int> l5(array, array + sizeof(array) / sizeof(int));
// 列表格式初始化C++11
list<int> l6{ 1, 2, 3, 4, 5 };
// 用迭代器方式打印l5中的元素
list<int>::iterator it = l5.begin();
while (it != l5.end())
{
cout << *it << " ";
++it;
}
cout << endl;
// C++11范围for的方式遍历
for (auto& e : l5)
cout << e << " ";
cout << endl;
}1.2.2 list iterator的使用
在list使用中我们通过迭代器的方式打印链表元素在vector中我们用的是[],因为vector是顺序表结构我们可以通过下标进行随机访问。而list却不能只能用迭代器的方式进行它的行为像指针一样。这个后面会通过源码剖析的角度来看待这里就简单的认为迭代就类似于指针。
list是链表结构在链表中因为内存地址不是连续开辟的比如通过下标2去找地址顺序表中地址是连续对应的而链表的地址是随机开辟的通过下标是不能找到相应的地址的。
以上就是证明为什么list不能用[]访问而选择用迭代器。
| 函数声明 | 接口说明 |
| begin+end | 返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器 |
例
// list迭代器的使用
// 注意遍历链表只能用迭代器和范围for
void PrintList(const list<int>& l)
{
// 注意这里调用的是list的 begin() const返回list的const_iterator对象
for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
{
cout << *it << " ";
// *it = 10; 编译不通过
}
cout << endl;
}
int main()
{
list<int> l;
l.push_back(1);
l.push_back(2);
l.push_back(3);
l.push_back(4);
PrintList(l);
return 0;
}这里需要说明一下就是begin和end既能使用iterator又能使用const_iterator。
begin iterator begin();const_iterator begin() const; end iterator end();const_iterator end() const;
使用const_iterator it =l.begin()这里是通过拷贝构造即使我们没有写拷贝构造但是系统会默认生成拷贝构造将指针进行拷贝。
const_iterator it = l.begin();
1.2.3list capacity
在链表中就不需要提前把空间开好这里是按需申请就不需要reserve和resize了。
| 函数声明 | 接口说明 |
| empty | 检测list是否为空是返回true否则返回false |
| size | 返回list中有效节点的个数 |
例
int main()
{
list<int> l;
l.push_back(1);
l.push_back(2);
l.push_back(3);
l.push_back(4);
cout << l.size() << endl;
if (!l.empty())
{
cout << "no empty!" << endl;
}
return 0;
}1.2.4 list element access
| 函数声明 | 接口说明 |
| front | 返回list的第一个节点中值的引用 |
| back | 返回list的最后一个节点中值的引用 |
例
void tets_element(list<int>& l)
{
cout << l.front() << endl;
cout << l.back() << endl;
}
1.2.5 list modifiers
| 函数声明 | 接口说明 |
| push_front | 在list首元素前插入值为val的元素 |
| pop_front | 删除list中第一个元素 |
| push_back | 在list尾部插入值为val的元素 |
| insert | 在list position 位置中插入值为val的元素 |
| erase | 删除list position位置的元素 |
| swap | 交换两个list中的元素 |
| clear | 清空list中的有效元素 |
例
// list插入和删除
void test_modifiers()
{
list <int> l;
//尾插
l.push_back(1);
l.push_back(2);
l.push_back(3);
l.push_back(4);
//尾删
l.pop_back();
PrintList(l);
cout << endl;
//头插
l.push_front(6);
l.push_front(7);
l.push_front(8);
//头删
l.pop_front();
PrintList(l);
cout << endl;
//第一个位置插入10
auto pos = l.begin();
l.insert(pos, 10);
PrintList(l);
cout << endl;
// 删除pos位置上的元素
l.erase(++pos);
PrintList(l);
}
// resize/swap/clear
void TestList5()
{
// 用数组来构造list
int array1[] = { 1, 2, 3 };
list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));
PrintList(l1);
// 交换l1和l2中的元素
list<int> l2;
l1.swap(l2);
PrintList(l1);
PrintList(l2);
// 将l2中的元素清空
l2.clear();
cout << l2.size() << endl;
}1.2.6 list的迭代器失效
之前在vector中insert是失效的但是在list中insert是不失效的。因为insert插入并没有改变pos的地址。erase却会失效迭代器失效即迭代器所指向的节点的无效即该节点被删除了。因为list的底层结构为带头结点的双向循环链表因此在list中进行插入时是不会导致list的迭代器失效的只有在删除时才会失效并且失效的只是指向被删除节点的迭代器其他迭代器不会受到影响。
例
void TestListIterator1()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(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 };
list<int> l(array, array+sizeof(array)/sizeof(array[0]));
auto it = l.begin();
while (it != l.end())
{
l.erase(it++); // it = l.erase(it);
}
}
1.2.7 sort
在list中单独有sort在之前是以模板的形式写入算法库<algorithm>。这里就说明因为它是已链表的结构排序需要重新实现那么就意味着list中sort的时间复杂度是不一样的。
list::sort void sort(); std::sort template <class RandomAccessIterator> void sort (RandomAccessIterator first, RandomAccessIterator last);
我们通过一段测试代码来比较同样的长度但是花费时间是巨大的。
void test_op()
{
srand(time(0));
const int N = 100000;
vector<int> v;
v.reserve(N);
list<int> lt1;
list<int> lt2;
for (int i = 0; i < N; ++i)
{
auto e = rand();
//v.push_back(e);
lt1.push_back(e);
lt2.push_back(e);
}
// 拷贝到vector排序排完以后再拷贝回来
int begin1 = clock();
for (auto e : lt1)
{
v.push_back(e);
}
sort(v.begin(), v.end());
size_t i = 0;
for (auto& e : lt1)
{
e = v[i++];
}
int end1 = clock();
int begin2 = clock();
// sort(lt.begin(), lt.end());
lt2.sort();
int end2 = clock();
printf("vector sort:%d\n", end1 - begin1);
printf("list sort:%d\n", end2 - begin2);
}在运行结果
1.Debug
vector sort:437
list sort:69372.Release
vector sort:7
list sort:16
在N个数据需要排序vector+ 算法sort list+ sort通过测试发现list中sort是非常耗时的vector中sort想对来说更加省时直接用list排序还不如将list的数据拷贝到vector中快。
二、list的模拟实现--非const
我们会通过几个阶段来进行模拟实现如果一下将全部模拟实现是加大了学习的成本是对学习很不友好的。
2.1list的节点
因为我们知道list是一个双向链表所以节点里面有一个前指针一个后指针有一个数据data。同时我们也模拟一个构造函数list (const list& x)用于list节点的初始化。
template < class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _data;
//构造函数
list_node(const T& x)
:_next(nullptr)
, _prev(nullptr)
, _data(x)
{}
};2.2list的迭代器
stl3.0当中的迭代器实现
template<class T, class Ref, class Ptr>
struct __list_iterator {
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
typedef __list_iterator<T, Ref, Ptr> self;
typedef bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef __list_node<T>* link_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
link_type node;
__list_iterator(link_type x) : node(x) {}
__list_iterator() {}
__list_iterator(const iterator& x) : node(x.node) {}
bool operator==(const self& x) const { return node == x.node; }
bool operator!=(const self& x) const { return node != x.node; }
reference operator*() const { return (*node).data; }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
self& operator++() {
node = (link_type)((*node).next);
return *this;
}
self operator++(int) {
self tmp = *this;
++*this;
return tmp;
}
self& operator--() {
node = (link_type)((*node).prev);
return *this;
}
self operator--(int) {
self tmp = *this;
--*this;
return tmp;
}
对于stl3.0当中的迭代器实现我们首先不去关系为什么是3个模板参数也不用去深研其他的typedef我们可以理解在iterator中不单单是一个指针了当然在iterator也有指针如下
typedef __list_node<T>* link_type;
link_type node;
在之前我们理解中我们直接对指针进行操作进行++--*解引用等等操作但是对于迭代器iterator我们通过观察发现iterator中因为list是链式结构我们对其++--接引用是不能直接实现所以就不能简单的通过指针就能完成这些操作那么它是通过对iterator封装来实现++--等操作的。使用++--等操作是通过函数调用
大家感兴趣可以先看看上面的我们先用一个简述版的来带大家简要实现一下
template < class T>
struct _list_iterator
{
typedef list_node<T> node;
node* _pnode;
//构造函数
_list_iterator(node* p)
:_pnode(p)
{}
//接引用就是返回节点的值
T& operator*()
{
return _pnode->_data;
}
//++操作就是就将当前指向下一个节点
_list_iterator<T>& operator++()
{
_pnode = _pnode->_next;
return *this;
}
//--操作就是将当前指向前一个节点
_list_iterator<T>& operator--()
{
_pnode = _pnode->_prev;
return *this;
}
//不等于传参节点的指针不等于this节点的指针
bool operator!=(const _list_iterator<T>& it)
{
return _pnode != it._pnode;
}
};2.2迭代器的价值
这里虽然我们使用vector和list的使用方法是基本类似的但是我们发现他们的底层已经出现很大的差别。这里*接引用在gcc下的vector中我们是直接对原生指针进行操作但是在list下我们是通过函数调用来实现的。
最后关于迭代器需要强调一点关于vector中的 iterator其实他可能也不是用原生指针这个需要看代码的实现因为我们在gcc和vs中我们发现迭代器失效他们失效并不一样意味着他们底层代码实现时不一样的在gcc它可以是通过原生指针的方式实现在vs也可以通过封装来实现。
结论
1.封装底层实现不暴露底层的实现细节
2.提供统一访问方式降低使用成本
物理层面比较
对于list类封装中的iteratior与vector中的iteratior的字节大小是一样的他们都是4字节。
为什么list也是4字节因为只看成员变量不看函数。所以说指针在类中封装后并没有变大在内存中还是实实在在的4byte。
他们不同的是list中存的时候节点位置的指针而vector中的是数据位置的指针。
所以在物理层面上他们是没有区别的他们字节的大小是一样的但是他们的类型不一样底层实现就是天差地别了--类型的力量。
2.3list的接口
template < class T>
class list
{
typedef list_node<T> node;
public:
typedef _list_iterator<T> iterator;
iterator begin()
{
//使用了匿名对象--调用拷贝构造
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
//当为null时next与prev都指向head
void empty_initalize()
{
_head = new node(T());
_head->_next = _head;
_head->_prev = _head;
}
//为null调用empty_initalize
list()
{
empty_initalize();
}
//拷贝构造
list(const list<T> & lt)
{
empty_initalize();
//这里需要特别注意&引用
//如果是内置类型就不影响e接受数据后push_back传入后销毁下一个传又是从lt引用
//如果lt是其他类型比如是vector类型或者是泛型数据是一串
//当push_back完后没有用引用那么push_back会销毁传一个数据他销毁了再传一个数据它又没了
for (const auto &e : lt)
{
push_back(e);//this.push_back
}
return *this;//返回链接值 head->1->2->3
}
//析构函数
~list()
{
clear();//第一步清楚数据
//第二步将头结点置空
delete _head;
_head = nullptr;
}
//将数据一一清理
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
list<T>& operator=(const list<T>& lt)
{
if (this != <)//判断链表数据不一样后进行操作
{
clear();//先清空
for (const auto&e : lt)//传值
{
push_back(e);
}
}
}
//头插
void push_front(const T& x)
{
insert(begin(), x);//调用insert
}
//头删
void pop_front()
{
erase(begin());//调用erase
}
//尾删
void pop_back()
{
erase(--end());
}
//尾插
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)
}
iterator insert(iterator pos, const T& x)
{
node* newnode = new node();//新建节点
node* cur = pos._pnode;//插入节点是在数据后插保存改数据后的节点
node* prev = cur._prve;//保存数据前的节点
//4步链接头尾
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
return iterator(newnode);//返回节点
}
iterator erase(iterator pos)
{
assert(pos != end());//不能删除头节点
node* prev = pos._pnode->_prev;//保存pos前的节点
node* next = pos._pnode->_next;//保存pos后的节点
prev->_next = next;//将后节点链接前节点
next->_prev = prev;//将前节点链接后节点
delete pos._pnode;//删除pos节点--会失效
return iterator(next);//返回pos节点后的节点
}
private:
node* _head;
};list接口的模拟实现主要insert和erase有些难度但是对于写过数据结构的代码我相信大家稍花功夫就能够轻松解决。
insert图解如下
erase图解如下
三、list的模拟实现--const
下面内容主要是迭代器被const修饰普通人的写法和大佬的写法他们尽显锋芒。
3.1理解const修饰iterator
错误写法
void list_test(const list<int>& lt)
{
const list<int>::iterator lt1 = lt.begin();
}首先需要理解const T* p1与T* const p2const迭代器类似p1的行为保护指向对象不被修改但是迭代器本身是可以被修改的。
这里的const是修饰的lt1不符合const迭代器的行为因为他保护迭代器本身不能修改那么我们也就不能++迭代器。
因为iterator是被封装使用的我们发现在struct _list_iterator中我们改变其返回值用const修饰那么我们还是可以对迭代器进行++--等操作只是返回值不能被改变。
T& operator*()
{
return _pnode->_data;
}既然是需要const修饰返回值那么我们能不能直接通过函数重载来支持呢
T& operator*()
{
return _pnode->_data;
}
const T& operator*() const
{
return _pnode->_data;
}答案是不能的。如果clt被const修饰的参数++就调用operator++()返回值是不被修改这里的this也被const修改那么this指向的节点都被修改该节点就不能实现++操作这样实现的话只能接引用但不能++。
const T& operator*() const
{
return _pnode->_data;
}
_list_iterator<T>& operator++()
{
_pnode = _pnode->_next;
return *this;
}如果我们是实现
const _list_iterator<T>& operator++() const
答案也是不行的因为这个过程就是对this值进行操作这里其实就this已经都被const修饰了。有点绕但是我们主要需要知道整个this值不然很容易就昏了。
3.2实现const修饰iterator
既然上述解释了在一个类中通过函数重载const修饰的this会影响因为我们需要函数重载的话const不仅仅需要修返回值也要修改this上面写法就是错误的
const T& operator*() const
那么我们重新建立类其他不变只将返回参数改成被const修饰即可。
const T& operator*()
template<class T>
struct _list_const_iterator
{
typedef list_node<T> node;
node* _pnode;
_list_const_iterator(node* p)
:_pnode(p)
{}
const T& operator*()
{
return _pnode->_data;
}
_list_const_iterator<T>& operator++()
{
_pnode = _pnode->_next;
return *this;
}
_list_const_iterator<T>& operator--()
{
_pnode = _pnode->_prev;
return *this;
}
bool operator!=(const _list_const_iterator<T>& it)
{
return _pnode != it._pnode;
}
};我们建立了两个类所以我们在list直接进行用就可以了。添加上begin+end被const修饰的接口就可以了。
template <class T>
class list
{
typedef list_node<T> node;
public:
typedef _list_iterator<T> iterator;
typedef _list_const_iterator<T> const_iterator;
const_iterator begin() const
{
return const_iterator(_head->_next);
}
const_iterator end() const
{
return const_iterator(_head);
}
}四、list的模拟实现--大佬的iterator
上面写的iterator我们发现大多数代码都是一样的仅仅是返回值不一样就建立了两个类这样的话代码就比较冗余。那么大佬是不可能写出这样的代码大佬就通过增加模板参数就很好的解决这一问题了。
4.1第三个参数
原来模板参数只有一个类型现在将模板参数增加为两个以前我们是通过自己构建两个类来实现他们不同功能但是我们直接在模板里多增加一个类型编译器就默认实例化两个类型。
template<class T, class Ref>
同一个类模板实例化出的2个类型
typedef __list_iterator<T, T&,> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
这里T就是普通参数Ref就是被const修饰的参数。那么在看源码的时候有三个参数这里就不得不提到返回数据的指针了。
struct pos
{
int _row;
int _col;
pos(int row=0, int col=0)
:_row(row)
, _col(col)
{
}
};
int main()
{
list<pos> lt;
pos p1(1,1);
lt.push_back(p1);
lt.push_back(p1);
lt.push_back(p1);
lt.push_back(pos(2,2));
lt.push_back(pos(3,3));
list<pos>::iterator it = lt.begin();
while (it != lt.end())
{
cout << (*it)._row << ":" << (*it)._col << endl;
++it;
}
return 0;
}我们在结构体中是通过接引用迭代器的位置的值该值再通过.去访问结构体中的行的值。这样用起来是非常别扭以前访问结构体就是直接地址->指向实参it->_row。
回忆C语言中->的用法
struct Data
{
int a, b, c;
};
int main()
{
struct Data * p;
struct Data A = { 1, 2, 3 };
int x;
p = &A;
x = p->a;
cout << x << endl;
return 0;
}这里it是迭代器所以我们需要封装->然后在进行应用。
Ptr operator->()
{
return &_pnode->_data;
}
Ptr返回的是节点数据的地址拥有->后我们再看看使用。
while (it != lt.end())
{
cout << it->_row << ":" << it->_col << endl;
++it;}
it->_row是什么意思it->是调用it.operator->(),返回节点数据的地址紧接着是返回节点数据的地址->_row正确的写法应该是it->->_row。但是这是既不好看又不好用编译器为了可读性省略了一个->。
while (it != lt.end())
{
cout << it.operator->()->_row << ":" << it->_col << endl;
++it;}
当然这样用也是不错的。
综上所述知道我们所添加的第三个参数就是T*,用于接受返回的地址。
template<class T, class Ref, class Ptr>
typedef __list_iterator<T, T&, T*> iterator;
4.2大佬的iterator
#pragma once
#include<assert.h>
namespace bit
{
template<class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _data;
list_node(const T& x)
:_next(nullptr)
, _prev(nullptr)
, _data(x)
{}
};
// 同一个类模板实例化出的2个类型
// typedef __list_iterator<T, T&, T*> iterator;
// typedef __list_iterator<T, const T&, const T*> const_iterator;
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef list_node<T> node;
typedef __list_iterator<T, Ref, Ptr> Self;
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;
}
// it++
Self operator++(int)
{
Self tmp(*this);
_pnode = _pnode->_next;
return tmp;
}
Self& operator--()
{
_pnode = _pnode->_prev;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
_pnode = _pnode->_prev;
return tmp;
}
bool operator!=(const Self& it) const
{
return _pnode != it._pnode;
}
bool operator==(const Self& it) const
{
return _pnode == it._pnode;
}
};
//vector<int>
//vector<string>
//vector<vector<int>>
// 类名 类型
// 普通类 类名 等价于 类型
// 类模板 类名 不等价于 类型
// 如list模板 类名list 类型list<T>
// 类模板里面可以用类名代表类型但是建议不要那么用
template<class T>
class list
{
typedef list_node<T> node;
public:
typedef __list_iterator<T, T&, T*> iterator;
//typedef __list_const_iterator<T> const_iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
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()
{
//iterator it(_head);
//return it;
return iterator(_head);
}
void empty_initialize()
{
_head = new node(T());
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
empty_initialize();
}
//迭代器区间构造
template <class InputIterator>
list(InputIterator first, InputIterator last)
{
empty_initialize();
while (first != last)
{
push_back(*first);
++first;
}
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
// 现代写法--复用
// lt2(lt1)
list(const list<T>& lt)//在类内部类名 等等价于 类型
//list(const list& lt) // 这里list<T>&与list&是一样的但是不建议用
{
empty_initialize();
list<T> tmp(lt.begin(), lt.end());//复用迭代器区间构造
swap(tmp);//交换head和size
}
// lt3 = lt1
list<T>& operator=(list<T> lt)//不能加&因为就是需要交换的是lt的拷贝
//list& operator=(list lt) // 不建议
{
swap(lt);
return *this;
}
size_t size() const
{
return _size;
}
bool empty() const
{
return _size == 0;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_front()
{
erase(begin());
}
void pop_back()
{
erase(--end());
}
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 != end());
node* prev = pos._pnode->_prev;
node* next = pos._pnode->_next;
prev->_next = next;
next->_prev = prev;
delete pos._pnode;
--_size;
return iterator(next);
}
private:
node* _head;
size_t _size;//为了减少后续频繁调用循环查找size
};
}五、反向迭代器
在stl源码中他是通过适配器得到将正向迭代器的接口传过来然后直接在正向迭起的基础上进行改进。
self& operator++() {
--current;
return *this;
}
self operator++(int) {
self tmp = *this;
--current;
return tmp;
}
self& operator--() {
++current;
return *this;
}
self operator--(int) {
self tmp = *this;
++current;
return tmp;
}完结
