目录
push_back、push_front、pop_front、pop_back
承接CD46.【C++ Dev】list的模拟实现(1)文章
1.const修饰的迭代器的实现
回顾const修饰的迭代器的要求:1.自己可以修改 2.指向的数据不能修改
方法1:分成两个类
const修饰的迭代器和非const修饰的迭代器分成两个类,写两份代码,这两份代码仅仅是operator*的返回的参数不同
//const修饰的迭代器
const T& operator*()
{
return node->data;
}
//非const修饰的迭代器
T& operator*()
{
return node->data;
}注意:const修饰的迭代器中的operator*不能写成T& operator*() const,这个const修饰的是this指针指向的对象node不能被修改(在CD22.【C++ Dev】类和对象(13) 流提取运算符的重载和const成员文章讲过),不是指node->data不能修改
完整代码
#pragma once
namespace mystl
{
template<class T>
struct __list_node
{
typedef __list_node<T>* link_type;
__list_node(const T& x = T())
:next(nullptr)
, prev(nullptr)
, data(x)
{
}
link_type next;
link_type prev;
T data;
};
template<class T>
struct __list_iterator
{
typedef __list_node<T>* link_type;
typedef __list_iterator<T> iterator;
__list_iterator(link_type x)
:node(x)
{}
iterator& operator++()
{
node = node->next;
return *this;
}
iterator operator++(int)
{
iterator tmp(*this);
node = node->next;
return tmp;
}
iterator& operator--()
{
node = node->prev;
return *this;
}
iterator operator--(int)
{
iterator tmp(*this);
node = node->prev;
return tmp;
}
bool operator!=(const iterator& x) const
{
return node != x.node;
}
bool operator==(const iterator& x) const
{
return node == x.node;
}
T& operator*()
{
return node->data;
}
link_type node;
};
template<class T>
struct __list_const_iterator
{
typedef __list_node<T>* link_type;
typedef __list_const_iterator<T> const_iterator;
__list_const_iterator(link_type x)
:node(x)
{}
const_iterator& operator++()
{
node = node->next;
return *this;
}
const_iterator operator++(int)
{
const_iterator tmp(*this);
node = node->next;
return tmp;
}
const_iterator& operator--()
{
node = node->prev;
return *this;
}
const_iterator operator--(int)
{
const_iterator tmp(*this);
node = node->prev;
return tmp;
}
bool operator!=(const const_iterator& x) const
{
return node != x.node;
}
bool operator==(const const_iterator& x) const
{
return node == x.node;
}
const T& operator*()
{
return node->data;
}
link_type node;
};
template<class T>
class list
{
typedef __list_node<T> list_node;
typedef __list_node<T>* link_type;
public:
typedef __list_iterator<T> iterator;
typedef __list_const_iterator<T> const_iterator;
list()
{
node = new list_node;
node->next = node;
node->prev = node;
}
void push_back(const T& x)
{
link_type tmp = new list_node(x);
//先找尾
link_type tail = node->prev;
tail->next = tmp;
tmp->prev = tail;
tmp->next = node;
node->prev = tmp;
}
iterator begin()
{
//返回哨兵位的下一个节点
return node->next;
}
iterator end()
{
//返回哨兵位
return node;
}
const_iterator begin() const
{
//返回哨兵位的下一个节点
return node->next;
}
const_iterator end() const
{
//返回哨兵位
return node;
}
private:
link_type node;
};
}测试代码:
#include <iostream>
#include "list.h"
void print_list(const mystl::list<int>& ls)//权限缩小
{
mystl::list<int>::const_iterator it = ls.begin();
while (it != ls.end())
{
std::cout << *it << " ";
it++;
}
}
int main()
{
mystl::list<int> ls;
ls.push_back(1);
ls.push_back(2);
ls.push_back(3);
print_list(ls);
return 0;
}运行结果:
方法2:STL库的写法
STL的源码:__list_iterator迭代器类有3个模版参数:T、Ref、Ptr
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 Ref reference;
//......
reference operator*() const { return (*node).data; }
}
operator*的返回类型为reference,而reference为Ref,Ref是__list_iterator类的第二个模版参数
这样可以为Ref指定:T&或者const T&,这样可以简写const修饰和非const修饰的迭代器,没有必要写两份代码
之前返回类型为iterator要改成__list_iterator<T, Ref>,可以重定义为self
其实是让编译器来代替我们写iterator和const_iterator这两个类
template<class T,class Ref>
struct __list_iterator
{
typedef __list_node<T>* link_type;
typedef __list_iterator<T,T&> iterator;
typedef __list_iterator<T,const T&> const_iterator;
typedef __list_iterator<T, Ref> self;
typedef Ref reference;
__list_iterator(link_type x)
:node(x)
{}
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& x) const
{
return node != x.node;
}
bool operator==(const self& x) const
{
return node == x.node;
}
reference operator*()
{
return node->data;
}
link_type node;
};继续测试之前的代码,运行结果:
注:反向迭代器的实现之后会单独讲
2.STL库的第三个模版参数T*的解释
上方代码实现的__list_iterator只有2个模版参数,但是STL库却有3个模板参数:
template<class T, class Ref, class Ptr>
struct __list_iterator
{
//......
}看看Ptr出现在什么函数中:
STL库将Ptr重定义为pointer:
typedef Ptr pointer;那就找pointer还出现在哪里:
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */发现:pointer是operator->的返回类型,原因:
迭代器的任务是模拟指针,而结构体指针是可以用operator->来访问其指向对象的成员,那迭代器也要有operator->操作符
那自制的operator->可以这样写:
template<class T,class Ref,class Ptr>
struct __list_iterator
{
typedef __list_node<T>* link_type;
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 Ref reference;
typedef Ptr pointer;
//......
reference operator*()
{
return node->data;
}
pointer operator->()
{
return &(node->data);
}
link_type node;
};
当然也可以复用operator*,写成:
pointer operator->()
{
return &(operator*());
}测试代码:
#include <iostream>
#include "list.h"
class Myclass
{
public:
Myclass(const int val1=0, const char val2='\0')
:_val1(val1)
, _val2(val2)
{}
int _val1;
char _val2;
};
int main()
{
mystl::list<Myclass> ls;
ls.push_back(Myclass(1,'a'));
ls.push_back(Myclass(2, 'b'));
ls.push_back(Myclass(3, 'c'));
mystl::list<Myclass>::iterator it = ls.begin();
while (it != ls.end())
{
std::cout << it->_val1 << " " << it->_val2 << std::endl;
std::cout << (*it)._val1 << " " << (*it)._val2 << std::endl;
it++;
}
return 0;
}运行结果:
发现it->_val1和(*it)._val1的效果是等价的
->->的简写语法
注意到operator->()返回的是Myclass*,严谨来说Myclass*是不能访问_val1和_val2的,应该写成
std::cout << it->->_val1 << " " << it->->_val2 << std::endl;但编译器在编译时自动加上了第二个->,C++标准只允许写一个->,提高运算符重载的可读性
3.其他成员函数
insert
和STL保持一致:
这里只实现第一个:
先生成新节点,再在pos前插入:
iterator insert(iterator pos,const T& val)
{
link_type newnode = new list_node(val);
newnode->prev = pos.node->prev;
newnode->next = pos.node;
pos.node->prev->next = newnode;
pos.node->prev = newnode;
return newnode;
}测试代码:
#include <iostream>
#include "list.h"
int main()
{
mystl::list<int> ls;
ls.push_back(1);
ls.push_back(2);
ls.push_back(3);
auto new_it1=ls.insert(++ls.begin(), 4);//在2的前面插入4
for (auto a : ls)
std::cout << a << " ";
return 0;
}运行结果:
erase
和STL保持一致:
这里只实现第一个:
注意:erase不能删哨兵位,因此先断言
erase函数在删除元素时,会使当前迭代器失效n并返回指向下一个元素的迭代器,因此不能返回void
iterator erase(iterator pos)
{
assert(pos != end());
iterator ret = pos.node->next;
pos.node->prev->next = pos.node->next;
pos.node->next->prev = pos.node->prev;
delete pos.node;
return ret;
}测试代码:
#include <iostream>
#include "list.h"
int main()
{
mystl::list<int> ls;
ls.push_back(1);
ls.push_back(2);
ls.push_back(3);
ls.erase(++ls.begin());//删除2
for (auto a : ls)
std::cout << a << " ";
return 0;
}运行结果:
push_back、push_front、pop_front、pop_back
可以复用insert和erase的代码
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());
}测试代码:
#include <iostream>
#include "list.h"
int main()
{
mystl::list<int> ls;
ls.push_back(1);
ls.push_back(2);
ls.push_back(3);
ls.push_back(4);
ls.pop_back();
ls.pop_front();
ls.push_back(5);
ls.push_front(6);
for (auto a : ls)
std::cout << a << " ";
return 0;
}运行结果:
size
STL库的实现:
size_type size() const {
size_type result = 0;
distance(begin(), end(), result);
return result;
}distance是算法库<algorithm>中的函数,用于计算两个迭代器之间的距离,并将结果存储到result中,这里我们实现的简单一些:
void distance(const_iterator begin, const_iterator end, size_type& result) const
{
const_iterator it = begin;
while (it != end)
{
it++;
result++;
}
}
size_type size() const
{
size_type result = 0;
distance(begin(), end(), result);
return result;
}测试代码:
#include <iostream>
#include "list.h"
int main()
{
mystl::list<int> ls;
ls.push_back(1);
ls.push_back(2);
ls.push_back(3);
ls.push_back(4);
std::cout << ls.size();
return 0;
}(当然这样遍历一遍是有缺点的,比较耗时,可以为list类引入第二个成员变量size来存储链表的长度,这里省略不写)
运行结果:
clear
和STL保持一致:
删除多余节点,只保留哨兵位
void clear()
{
iterator it = begin();
while (it != end())
it=erase(it);//应对迭代器失效,接收返回值
}测试代码:
#include <iostream>
#include "list.h"
int main()
{
mystl::list<int> ls;
ls.push_back(1);
ls.push_back(2);
ls.push_back(3);
for (auto a : ls)
std::cout << a << " ";
ls.clear();
ls.push_back(4);
ls.push_back(5);
ls.push_back(6);
for (auto b : ls)
std::cout << b << " ";
return 0;
}运行结果:
析构函数~list()
先调用clear(),再将node释放,最后置为空指针
~list()
{
clear();
delete node;
node = nullptr;
}拷贝构造函数(★)
注意是深拷贝,浅拷贝会出问题(在CD44.【C++ Dev】vector模拟实现(3)文章的深拷贝问题解决提到过)
方法:通过遍历的方式一个个拷贝
//const修饰,防止权限放大
list(const list<T>& ls)//必须是引用,这个&如果不写,会无限调用拷贝构造函数
{
//准备哨兵位
node = new list_node;
node->next = node;
node->prev = node;
//添加节点
for (auto& a : ls)//使用引用,节省时间
{
push_back(a);
}
}测试代码:
#include <iostream>
#include "list.h"
int main()
{
mystl::list<int> ls;
ls.push_back(1);
ls.push_back(2);
ls.push_back(3);
mystl::list<int> ls_copy(ls);
for (auto a : ls_copy)
std::cout << a<<" ";
return 0;
}运行结果:
私有函数empty_initialize
两种构造函数的部分代码有些冗余
可以封装成一个私有函数empty_initialize(),当然库里面也是这样实现的:
swap
和STL保持一致:
注:上面swap的参数:list& x的list是类名,不是类型,却也可以做参数,C++的语法支持这样做,但不建议这样写,代码不直观
交换链表其实是交换头节点
void swap(list<T>& ls)//写成void swap(list& ls)也可以
{
std::swap(node, ls.node);
}测试代码:
#include <iostream>
#include "list.h"
int main()
{
mystl::list<int> ls1; ls1.push_back(1); ls1.push_back(2); ls1.push_back(3);
mystl::list<int> ls2; ls2.push_back(4); ls2.push_back(5); ls2.push_back(6);
std::cout << "ls1:";
for (auto a : ls1) std::cout << a << " ";
std::cout << std::endl << "ls2:";
for (auto b : ls2) std::cout << b << " ";
ls1.swap(ls2);
std::cout << std::endl << "ls1:";
for (auto a : ls1) std::cout << a<<" ";
std::cout << std::endl << "ls2:";
for (auto b : ls2) std::cout << b<<" ";
return 0;
}运行结果:
operator=
使用CD40.【C++ Dev】string类的模拟实现(4)(operator=、拷贝构造函数的现代写法、写时拷贝的简单了解)文章提到的现代写法:1.operator=的参数需要调用拷贝构造 2.调用swap
list<T>& operator=(list<T> tmp)//写成list& operator=(list tmp)也可以
{
swap(tmp);
return *this;
}测试代码:
#include <iostream>
#include "list.h"
int main()
{
mystl::list<int> ls1; ls1.push_back(1); ls1.push_back(2); ls1.push_back(3);
mystl::list<int> ls2 = ls1;
std::cout << "ls2:";
for (auto a : ls2) std::cout << a << " ";
return 0;
}4.提交到leetcode题上测试成员函数的正确性
题:https://leetcode.cn/problems/design-linked-list/
你可以选择使用单链表或者双链表，设计并实现自己的链表。
单链表中的节点应该具备两个属性：
val和next。val是当前节点的值，next是指向下一个节点的指针/引用。如果是双向链表，则还需要属性
prev以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。实现
MyLinkedList类：
MyLinkedList()初始化MyLinkedList对象。int get(int index)获取链表中下标为index的节点的值。如果下标无效，则返回-1。void addAtHead(int val)将一个值为val的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。void addAtTail(int val)将一个值为val的节点追加到链表中作为链表的最后一个元素。void addAtIndex(int index, int val)将一个值为val的节点插入到链表中下标为index的节点之前。如果index等于链表的长度，那么该节点会被追加到链表的末尾。如果index比长度更大，该节点将 不会插入 到链表中。void deleteAtIndex(int index)如果下标有效，则删除链表中下标为index的节点。示例：
输入 ["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"] [[], [1], [3], [1, 2], [1], [1], [1]] 输出 [null, null, null, null, 2, null, 3] 解释 MyLinkedList myLinkedList = new MyLinkedList(); myLinkedList.addAtHead(1); myLinkedList.addAtTail(3); myLinkedList.addAtIndex(1, 2); // 链表变为 1->2->3 myLinkedList.get(1); // 返回 2 myLinkedList.deleteAtIndex(1); // 现在，链表变为 1->3 myLinkedList.get(1); // 返回 3提示：
0 <= index, val <= 1000- 请不要使用内置的 LinkedList 库。
- 调用
get、addAtHead、addAtTail、addAtIndex和deleteAtIndex的次数不超过2000。
代码
namespace mystl
{
template<class T>
struct __list_node
{
typedef __list_node<T>* link_type;
__list_node(const T& x = T())
:next(nullptr)
, prev(nullptr)
, data(x)
{}
link_type next;
link_type prev;
T data;
};
template<class T,class Ref,class Ptr>
struct __list_iterator
{
typedef __list_node<T>* link_type;
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 Ref reference;
typedef Ptr pointer;
__list_iterator(link_type x)
:node(x)
{}
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& x) const
{
return node != x.node;
}
bool operator==(const self& x) const
{
return node == x.node;
}
reference operator*()
{
return node->data;
}
pointer operator->()
{
return &(node->data);
}
link_type node;
};
template<class T>
class list
{
typedef __list_node<T> list_node;
typedef __list_node<T>* link_type;
typedef size_t size_type;
public:
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
list()
{
empty_initialize();
}
list(const list<T>& ls)
{
empty_initialize();
for (auto& a : ls)
{
push_back(a);
}
}
void push_back(const T& x)
{
insert(end(), x);
}
iterator begin()
{
return node->next;
}
iterator end()
{
//返回哨兵位
return node;
}
const_iterator begin() const
{
return node->next;
}
const_iterator end() const
{
return node;
}
iterator insert(iterator pos,const T& val)
{
link_type newnode = new list_node(val);
newnode->prev = pos.node->prev;
newnode->next = pos.node;
pos.node->prev->next = newnode;
pos.node->prev = newnode;
return newnode;
}
iterator erase(iterator pos)
{
assert(pos != end());
iterator ret = pos.node->next;
pos.node->prev->next = pos.node->next;
pos.node->next->prev = pos.node->prev;
delete pos.node;
return ret;
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_front()
{
erase(begin());
}
void pop_back()
{
erase(--end());
}
void distance(const_iterator begin, const_iterator end, size_type& result) const
{
const_iterator it = begin;
while (it != end)
{
it++;
result++;
}
}
size_type size() const
{
size_type result = 0;
distance(begin(), end(), result);
return result;
}
void clear()
{
iterator it = begin();
while (it != end())
it=erase(it);
}
void swap(list<T>& ls)
{
std::swap(node, ls.node);
}
list<T>& operator=(list<T> tmp)
{
swap(tmp);
return *this;
}
~list()
{
clear();
delete node;
node = nullptr;
}
private:
void empty_initialize()
{
node = new list_node;
node->next = node;
node->prev = node;
}
link_type node;
};
}
class MyLinkedList {
public:
MyLinkedList()
{}
mystl::list<int>::iterator getiterator(int index)
{
mystl::list<int>::iterator it=ls.begin();
while(index--)
it++;
return it;
}
int get(int index)
{
if (index<ls.size())
return getiterator(index).node->data;
return -1;
}
void addAtHead(int val)
{
ls.push_front(val);
}
void addAtTail(int val)
{
ls.push_back(val);
}
void addAtIndex(int index, int val)
{
if (index<=ls.size())//取等是尾插
ls.insert(getiterator(index),val);
}
void deleteAtIndex(int index)
{
if (index<ls.size())
ls.erase(getiterator(index));
}
mystl::list<int> ls;
};提交结果
