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比较

	vector	list
底层结构	动态顺序表，一段连续空间	带头节点的双向循环链表
随机访问	支持随机访问，访问某个元素效率O(1)	不支持随机访问，访问某个元素O(N)
插入和删除	任意位置插入和删除效率低，需要搬移元素，时间复杂度O(N)，插入时有可能需要增容，开辟新空间，效率更低	任意位置插入和删除效率更高，不需要搬移元素，时间复杂度O(1)
空间利用率	连续空间,不容易造成内存碎片,利用率高,缓存利用率高	节点动态开辟,小节点容易造成碎片,利用率低
迭代器	原生态指针	对原生态指针封装
迭代器失效	插入元素,要给所有的迭代器重新赋值,插入时会扩容失效。删除时，也会失效	插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响
使用场景	需要高效存储，支持随机访问，不关心插入和删除效率	大量插入和删除，不关心随机访问