13 list的实现

注意

实现仿cplus官网的list类，对部分主要功能实现

实现

文件

#pragma once
#include <assert.h>namespace mylist
{template <typename T>struct __list_node{__list_node(const T& x = T()): _prev(nullptr), _next(nullptr), _data(x){}__list_node<T>* _prev;__list_node<T>* _next;T _data;};//迭代器template <class T, class Ref, class Ptr>struct __list_iterator{typedef __list_node<T> node;typedef __list_iterator<T, Ref, Ptr> self;__list_iterator(node* it_node){node_iterator = it_node;}Ref operator*(){return node_iterator->_data;}Ptr operator->(){//return &node_iterator->_data;return &(operator*());}self& operator++(){node_iterator = node_iterator->_next;return *this;;}self operator++(int){self tmp(*this);node_iterator = node_iterator->_next;return tmp;;}self& operator--(){node_iterator = node_iterator->_prev;return *this;;}self operator--(int){self tmp(*this);node_iterator = node_iterator->_prev;return tmp;;}bool operator!=(const self& x){return node_iterator != x.node_iterator;}bool operator==(const self& x){return node_iterator == x.node_iterator;}node* node_iterator;};template <class T>class list{typedef  __list_node<T> node;public:typedef  __list_iterator<T, T&, T*> iterator;typedef  __list_iterator<T, const T&, const T*> const_iterator;iterator begin(){iterator tmp(_head->_next);return tmp;}iterator end(){iterator tmp(_head);return tmp;}const_iterator begin() const{const_iterator tmp(_head->_next);return tmp;}const_iterator end() const{const_iterator tmp(_head);return tmp;}//构造void empyt_init(){_head = new node;_head->_prev = _head->_next = _head;}list(){empyt_init();}template <class InputIterator>list(InputIterator first, InputIterator last){empyt_init();while (first != last){push_back(*first);first++;}}void swap(list<T>& x){std::swap(_head, x._head);}list(const list<T>& x){empyt_init();list<T> tmp(x.begin(), x.end());swap(tmp);/*const_iterator it = x.begin();while (it != x.end()){push_back(*it);it++;}*//*for (auto e : x){push_back(e);}*/}list<T>& operator=(list<T> x){swap(x);return *this;}//addvoid push_front(const T& x){Insert(begin(), x);}void push_back(const T& x){node* new_node = new node(x);_head->_prev->_next = new_node;new_node->_prev = _head->_prev;_head->_prev = new_node;new_node->_next = _head;}void Insert(iterator pos, const T& x){node* new_node = new node(x);//记录前后节点node* pre = pos.node_iterator->_prev;node* cur = pos.node_iterator;//连接pre->_next = new_node;new_node->_prev = pre;new_node->_next = cur;cur->_prev = new_node;}//devoid pop_front(){Erase(begin());}void pop_back(){Erase(--end());}iterator Erase(iterator pos){//头节点不能删assert(pos != end());node* prev = pos.node_iterator->_prev;node* next = pos.node_iterator->_next;prev->_next = next;next->_prev = prev;delete pos.node_iterator;return iterator(next);}//析构void clear(){iterator it = begin();while (it != end()){Erase(it++);}}~list(){clear();delete _head;_head = nullptr;}private:node* _head;};}

测试

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <string>
#include "list.h"
using namespace mylist;
void printlist(const list<int> l2)
{list<int>::const_iterator it = l2.begin();while (it != l2.end()){std::cout << *it << " ";it++;}
}class A
{
public:A(int a = 1, int b = 6){_a = a;_b = b;}A(const A& x){}int _a;int _b;
};int main()
{list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);list<int>::iterator it = l1.begin();while (it != l1.end()){std::cout << *it << " ";it++;}std::cout << std::endl;//l1.clear();//l1.pop_back();/*l1.push_back(1);l1.push_back(2);l1.push_back(3);it = l1.begin();while (it != l1.end()){std::cout << *it << " ";it++;}*//*list<int> l2;l2 = l1;it = l2.begin();while (it != l2.end()){std::cout << *it << " ";it++;}*///std::cout << n1;//printlist(l1);/*for (auto ch : l1){std::cout << ch << " ";}*//*list<int>::iterator it = l1.begin();while (it != l1.end()){int tmp = *it;std::cout << (*it) << std::endl;it++;}*///std::cout << "hello world\r\n";/*list<A> l2;l2.push_back(A(1, 3));l2.push_back(A(1, 4));l2.push_back(A(2, 3));list<A>::iterator it = l2.begin();std::cout << it->_a;*/return 0;
}

注意事项

1.和c语言的链表一样，先设计一个节点的结构体。构造函数传入节点值构造对应的节点
2.迭代器的结构统一了静态，需要三个模板参数。第一个是数据的类型，第二个Ref作为重载*符号的返回值，const迭代器传const值的引用，第三个Ptr重载->的返回值，区分const的迭代器
3.链表的初始化，申请一个哨兵位的节点，它的下一个和前一个节点都指向自己
4.拷贝构造只需要一个构造一个链表，然后交换头节点的指针
5.删除时不能删除头节点

list和vector比较