淘宝做基础销量怎么网站,1688网站一起做网店,wordpress搜索页面,建筑公司愿景口号大全目录
前言
1 push_back pop_back
2 迭代器类
2.1 !
2.2 --
2.3 *
3 Print_List
4 有关自定义类型
5 有关const迭代器
6 拷贝构造 赋值 析构 Insert erase 前言
有了string#xff0c;vector的基础#xff0c;我们模拟实现list还是比较容易的#xff0c;这里同…目录
前言
1 push_back pop_back
2 迭代器类
2.1 !
2.2 --
2.3 *
3 Print_List
4 有关自定义类型
5 有关const迭代器
6 拷贝构造 赋值 析构 Insert erase 前言
有了stringvector的基础我们模拟实现list还是比较容易的这里同样先看源码进行简单的分析这里直接说了就list的模拟实现难就难在于需要三个自定义类型所以我们的重难点就是如何捋清它们三个之间的关系 一共三个自定义类型分别是用来控制节点的控制迭代器的控制链表的那么为什么会这么复杂呢尤其是在迭代器部分的模板有三个参数。
对于vector来说空间是连续的所以我们想要访问它的内容是很容易的在vector和string中的迭代器可以理解为指针指针就可以找到下一个空间但是链表不同链表的空间不是连续的所以内置类型指针的满足不了访问下一个空间的目的那么为了能操纵迭代器的行为我们这里就需要一个自定义类型来让迭代器按照我们的想法去移动。
在list类中我们看到只有一个成员变量即node那么随着typedef看过去就知道link_type是控制节点的类的指针类型。
迭代器具体等会再细说现在大体模式了解了就开始进入吧。 1 push_back pop_back
文档里面说list是双向带头循环链表所以我们需要一个哨兵位也需要两个指针所以我们先创建一个节点类节点类的模板也是必要的因为节点里面不可能存的只有一种类型除此之外还有调用对应的构造函数因为是带头循环所以创建好一个节点之后需要让它自己指向自己这是构造函数的写法
template class T
struct ListNode
{ListNodeT* _next;ListNodeT* _prev;T _data;ListNode(const T val T()):_next(nullptr),_prev(nullptr),_data(val){}
};
对此代码稍微有点陌生的是ListNodeT*的写法其实就是该节点类型的指针便于指向下一块空间而已对于构造函数的参数是和vector的resize很像的给一个缺省值方便初始化T()的写法也不陌生了吧。
节点类里面存在的是指针域和数值域其余的也没有什么要特殊注意的。
节点类我们就创建好了那么就该创建一个list类了
templateclass T
class list
{
public:typedef ListNodeT Node;private:Node* _head;size_t _size;
};
对于计数问题我们可以遍历的时候单独创建一个变量也可以在类里面直接创建一个变量insert的时候erase的时候--两种方式任选其一都是没问题的。
这里的所以typedef最好都放在限定符的后面有时候是会报错的比如找不到什么的为了方便这里就把ListNodeT重命名了Node。
那么现在就满足了实现push_back的基本条件push_back实现本身是没啥问题的在数据结构中就提到了连接的问题这里就直接连接了
void push_back(const T val)
{Node* newnode new Node(val);newnode-_next _head;newnode-_prev _head-_prev;_head-_prev-_next newnode;//下两个的顺序不能变_head-_prev newnode;_size;
}
这里的连接推荐的是先连接newnode防止动其他节点的时候被修改了比如_head-_prev要后连接不然就会变成了newnode-_prev newnode就会出问题了。
尾删的操作也是很简单的但是链表为空的时候不能删除所以我们需要一个判断链表是否为空的函数
bool empty_list()
{return _head-_next ! _head;
}
当然链表为空的时候_size是为0的所以判断为空的条件有两个我们选取任意一个都可以的。
void pop_back()
{assert(empty_list());Node* tail _head-_prev;Node* new_tail tail-_prev;new_tail-_next _head;_head-_prev new_tail;_size--;
}
那么现在我们就可以对数据进行添加和删除了现在的情况就是如何打印数据呢前言提及对于链表的迭代器不是像普通迭代器一样那么简单所以我们这里需要创建一个迭代器类。 2 迭代器类
对于迭代器里面我们要搞懂一个问题就是这个类的用处是什么成员变量有哪些成员函数有什么
对于第一个问题不用多说是用来遍历链表的那么第二个问题成员变量有什么
我们要遍历一个链表无非就是要下一个位置的地址在一个节点类里面我们有前后两个节点的地址所以我们要遍历一个链表就需要一个当前节点有一个节点就够了所以
template class T
struct ListIterator
{typedef ListNodeT Node;typedef ListIterator iterator;Node* _node;ListIterator(Node* node):_node(node){}};
因为节点和迭代器我们是要访问全部成员的所以使用了结构体在源码里面也是这样操作的。
按照上文的理解我们只需要一个节点所以成员变量只有一个Node* _node这里也要用到重命名因为类域不一样所以我们不能接着用list中使用的typedef这里创建好之后我们应该进入下一个问题成员函数有什么
这个问题的答案来源于我们使用迭代器需要干什么遍历打印的时候我们需要判断该节点是不是尾节点需要解引用该节点得到里面的数值需要迭代器到下一个空间也可能需要--到上一个空间当节点里面存的是自定义类型更麻烦我们还需要对-进行重载这个先不管先一个一个函数的重载。
2.1 !
判断节点是否相等的唯一条件是地址是否相等
bool operator!(const iterator it)
{return _node ! it._node;
}bool operator(const iterator it)
{return _node it._node;
}
2.2 --
为了重载更完美重载前置和后置
iterator operator(int)
{Self tmp(*this);_node _node-_next;return tmp;
}
iterator operator()
{_node _node-_next;return *this;
}iterator operator--()
{_node _node-_prev;return *this;
}iterator operator--(int)
{Self tmp(*this);_node _node-_prev;return tmp;
}
返回值是引用可以减少拷贝但是返回的是临时对象就不能返回引用了这个在string里面提及过也没有什么要特别注意的。
2.3 *
T operator*()
{return _node-_data;
}
就so easy。
返回引用是因为遍历的时候涉及到修改所以需要引用类型。
那么80%的迭代器已经完成了。 3 Print_List
想要实现打印我们的三件套范围for迭代器下标访问就失效了一个list里面不存在下标访问。现在需要的是begin和end函数返回的是头结点和尾结点的地址为了和源码保持一致这里还要实现一个const版本的但是没什么难度:
iterator begin()
{return _head-_next;
}
iterator end()
{return _head;
}const_iterator begin() const
{return _head-_next;
}
const_iterator end() const
{return _head-_prev;
}
end节点就是哨兵位节点即_head现在打印的基本条件我们都满足了那就试试吧:
templateclass T
void Print_List(listT ll)
{listint::iterator it1 ll.begin();while(it1 ! ll.end()){cout *it1 ;it1;}cout endl;
}
不管是用范围for也好还是迭代器本质都是用迭代器这里就使用迭代器就完事了。
模板也是必不可少的因为是在类外实现的所以我们需要类域访问限定符这里用到的* ! 等操作我们都实现了就可以完美实现打印。
测试代码
void Test1_list()
{listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);Print_List(lt);lt.push_front(5);lt.push_front(6);lt.push_front(7);Print_List(lt);
} 4 有关自定义类型
如果我是说如果
struct A
{int _a1;int _a2;A(int a1 1,int a2 2):_a1(a1),_a2(a2){}
};链表存了一个这个我们应该如何打印呢相信这算得上一个难度我们先抛开这个问题先看如如何在链表里面存进这种类型的数据
void Test2_list()
{listA lt;A aa1(1, 2);//构造A aa2 { 1,2};//隐式类型转换lt.push_back(aa1);//有名对象lt.push_back(A(2,1));//匿名对象lt.push_back({1,2});//隐式类型转换lt.push_back({9,9});
}
这和在vector里面存入一个string是一样的有名对象和匿名对象这个过一下就好了我们回想C语言的一段代码
void test_list2()
{A* ptr aa1;(*ptr)._a1;ptr-_a1;
}
对于一个指针想要访问成员需要用到-那么我们也可以对指针进行解引用得到该结构体再使用.操作符进行访问所以-实际上的操作可以理解为解引用之后再使用.操作符那么要变身了
T* operator-()
{return _node-_data;
}
while (it ! lt.end())
{cout it-_a1 : it-_a2 ;cout it.operator-()-_a1 : it.operator-()-_a2 ;cout (*it)._a1 : (*it)._a2 ;it;
}
得到了指针就能打印所以重载-的返回值是指针那么为什么打印的时候可以直接it-_a1对于it来说它是一个迭代器类的指针它的成员变量是没有_a1的这就不得不说我们的编译器了编译器实际上是优化了一下真正的代码是it.operator-()-_a1先调用了-函数然后返回的数据类型的指针再次调用-这次调用的就不是函数了是-这个操作符这才得以打印所以优化容易让人有点看不懂。 5 有关const迭代器
对于const迭代器来说我们有一个简单粗暴的解决办法就是重新创建一个类原来的迭代器是ListIteratorconst迭代器就叫ListConstIterator就好了
template class T
struct ListConstIterator
{typedef ListNodeT Node;typedef ListConstIteratorT Self;Node* _node;ListConstIterator(Node* node):_node(node){}const T operator*(){return _node-_data;}const T* operator-(){return _node-_data;}//返回的是迭代器Self operator(int){Self tmp(*this);//Self tmp _node; //错辣_node _node-_next;return tmp;}Self operator(){_node _node-next;return *this;}Self operator--(){_node _node-_prev;return *this;}Self operator--(int){Self tmp(*this);_node _node-_prev;return tmp;}//迭代器里面是node 比较就是地址比较bool operator!(const Self it){return _node ! it._node;}bool operator(const Self it){return _node it._node;}
};
实际上我们只改动了两个地方一个是*一个是-的返回值无非是T*变成了const T*加一个const而已。
但是仅仅是为了这两个地方单独引入一个类太不划算了所以这里再次用到了模板
template class T,class Ref,class Ptr
struct ListIterator
{typedef ListNodeT Node;typedef ListIteratorT,Ref,Ptr Self;Node* _node;ListIterator(Node* node):_node(node){}//T operator*()Ref operator*(){return _node-_data;}//T* operator-()Ptr operator-(){return _node-_data;}
};
无非就是返回的指针和地址而已那么根据参数的不同我们返回的类型不同就ok了
templateclass T
class list
{
public:typedef ListNodeT Node;typedef ListIteratorT,T,T* iterator;typedef ListIteratorT,const T,const T* const_iterator;iterator begin(){return _head-_next;}iterator end()//end节点就是哨兵位{return _head;}const_iterator begin() const{return _head-_next;}const_iterator end() const{return _head-_prev;}
}
然后再再再重命名一下就大功告成了。
测试代码: void PrintList(const listint lt){listint::const_iterator it lt.begin();while (it ! lt.end()) {//*it 10;cout *it ;it;}cout endl;} 6 拷贝构造 赋值 析构 Insert erase
剩下的就是收尾工作了。
insert和erase的基本没什么要注意的已经在数据结构里面实现过了这里直接给上代码了
void Insert(iterator pos,const T val)
{Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(val);newnode-_next cur;newnode-_prev prev;cur-_prev newnode;prev-_next newnode; _size;
}iterator erase(iterator pos)
{Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;_size--;return iterator(next);
}
因为预防迭代器失效的问题erase的返回值要给iterator其他的就是正常的连接了。
实现了之后push_back和pop_back也可以复用了
void push_back(const T val)
{Insert(end(), val);
}void pop_back()
{erase(end()--);
}
对于拷贝构造来说参数是引用我们的实现方式是开一个头结点然后为尾插使用的是const版本的迭代器
list(const listT lt)
{empty_init();for (auto e : lt){push_back(e);}
}
这里的empty_init就是list的构造函数
void empty_init()
{_head new Node;_head-_next _head;_head-_prev _head;_size 0;
}
list()
{empty_init();
}
源码是这么写的我觉得是因为不能显式的调用析构所以需要给创造头结点的函数给单独拉出来按照源码咯就。
对于赋值来说使用现代写法就可以
listT operator(listT lt)
{swap(lt);return *this;
}void swap(listT lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}
对于析构析构即释放每个空间实际上就是把每个节点都删除了就好所以这里来个clear函数专门用来删除节点
void clear()
{iterator it begin();while (it ! end()){it erase(it);}
}
~list()
{clear();delete _head;_head nullptr;
}
析构函数就完美实现了。
那么list的实现就到此为止了。 感谢阅读
