1.前言

1.1list与vector的不同

区别：list的迭代器底层和其他两个迭代器底层有很大区别，因为list的链式结构决定了与它们两个的不一样

相同：迭代器用法大致一样，其他成员函数的使用也大致一样。

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及 应用场景不同，其主要不同如下

1.2 迭代器的分类 

 例子：

可以得知list类型无法使用std中的sort函数，因为list的迭代器是双向的，而sort函数的迭代器参数是随机的 ，同理可以得出，string，vector，deque都可以使用std中的sort

 1.3 list的本质

带头双向循环链表！！！！！！！！！！！！！！！！！！！

2.list节点 

<code>template<class T>//记得每一个类前要写模板

struct list_node //struct和class一样均为类，不同的是struct中的所有成员均为公有（public）类型，可直接访问

{

T data;

list_node<T>* next;

list_node<T>* prev;

list_node(const T& x=T()) //const T& x=T()，在没有给值的情况下，系统会通过T（）自动生成一个类型匹配的值赋给x

:data(x)

,next(nullptr)

,prev(nullptr)

{}

};

用类来封装一个一个结点，里面有两个指针，一个是指向下一个位置的指针，一个是指向前一个位置，还有一个用来存放数据的变量

3.list类框架 

template<class T>

class List

{

public:

typedef List_node<T> node;//取别名

void empty_list()

{

head = new Node;

head->_next = head;

head->_prev = head;

}

List()//构造函数

{

empty_list();

}

private:

node*head;//头节点

size_t _size;

}

list类里面包含的是结点的指针，也就是哨兵位头节点的指针

4.list迭代器

4.1 list迭代器框架

这里的迭代器是用封装加运算符重载来实现的，由于迭代器也会有很多类型，所以我们使用模板的形式

//T,T&,T*

//T,const T&,const T* //设定了两种迭代器

template<class T,class Ref,class Ptr>//记得每一个类前要写模板,可设置多个模板参数

struct list_iterator

{

typedef list_node<T> node;

typedef list_iterator<T,Ref,Ptr> self;

node* node1;

list_iterator(node* node2)

:node1(node2)

{}

}

4.2 list常用迭代器 

//T,T&,T*

//T,const T&,const T* //设定了两种迭代器

template<class T,class Ref,class Ptr>//记得每一个类前要写模板,可设置多个模板参数

struct list_iterator

{

typedef list_node<T> node;

typedef list_iterator<T,Ref,Ptr> self;

node* node1;

list_iterator(node* node2)

:node1(node2)

{}

self& operator++()

{

node1 = node1->next;

return *this; //模拟++

}

self& operator--()

{

node1 = node1->prev;

return *this; //模拟--

}

Ref operator*()

{

return node1->data; //模拟指针解引用

}

Ptr operator->()

{

return &node1->data;

}

bool operator!=(const self& S)

{

return node1 != S.node1;

}

};

迭代器的每一个操作都采用了运算符重载，其实这样看来还是指针在操作，只不过他不是直接的进行操作，而是换了一种方式

5.list函数详解 

5.1插入和删除

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)//在pos位置插入x

{

node* it = pos.node1;

node* newnode = new node(x);

node* prev = it->prev;

prev->next = newnode;

newnode->prev = prev;

newnode->next = it;

it->prev = newnode;

++_size;

return iterator(newnode); //返回新插入的元素的位置

}

iterator erase(iterator pos)

{

node* it = pos.node1;

node* prev = it->prev;

node* next = it->next;

delete it;

prev->next = next;

next->prev = prev;

--_size;

return iterator(next); //返回删除后的当前位置

}

5.2  拷贝构造和赋值运算符重载

list(const list<T>& it) //i1(i2)

{

int i = 0;

empty_list(); //初始化列表

for (auto e : it) //相当于自动调用迭代器，并解引用，最后迭代器再++

{

i = 1;

push_back(e);

}

}

void swap(list<T>& it)

{

std::swap(head, it.head);

std::swap(_size, it._size);

}

list operator=(list<T>it)// i1=i2 传参直接调用拷贝构造

{

swap(it);

return *this;

}

size_t size()

{

return _size;

}

5.3 list析构函数 

~list()

{

clear();

delete head;

head = nullptr;

}

void clear()

{

iterator it = begin();

while (it != end())

{

it = erase(it);

}

}

6.打印函数 

//打印

template<typename Container>

void print_container(const Container& con)

{

typename Container::const_iterator it = con.begin();

while (it != con.end())

{

cout << *it << " ";

++it;

}

cout << endl;

}

这里用的是typename，原因在于编译器在编译的时候，会去Container里面去找const_iterator这个类型，但是Container是一个模板，并没有实例化，所以编译器也不知道怎么定义，所以就在编译的时候就过不了，但是我们在前面加一个typename就会告诉编译器，先过，后面再来实例化，这样就可以解决问题了

适用于不知道list<T>中的T到底是什么类型时统一调用打印函数

7.代码总览

namespace zone

{

template<class T>//记得每一个类前要写模板

struct list_node //struct和class一样均为类，不同的是struct中的所有成员均为公有（public）类型，可直接访问

{

T data;

list_node<T>* next;

list_node<T>* prev;

list_node(const T& x=T()) //const T& x=T()，在没有给值的情况下，系统会通过T（）自动生成一个类型匹配的值赋给x

:data(x)

,next(nullptr)

,prev(nullptr)

{}

};

//T,T&,T*

//T,const T&,const T* //设定了两种迭代器

template<class T,class Ref,class Ptr>//记得每一个类前要写模板,可设置多个模板参数

struct list_iterator

{

typedef list_node<T> node;

typedef list_iterator<T,Ref,Ptr> self;

node* node1;

list_iterator(node* node2)

:node1(node2)

{}

self& operator++()

{

node1 = node1->next;

return *this; //模拟++

}

self& operator--()

{

node1 = node1->prev;

return *this; //模拟--

}

Ref operator*()

{

return node1->data; //模拟指针解引用

}

Ptr operator->()

{

return &node1->data;

}

bool operator!=(const self& S)

{

return node1 != S.node1;

}

};

//

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() //可读可写

{

return iterator(head->next);

}

iterator end()

{

return iterator(head);

}

const_iterator begin()const //只可读，不可写

{

return const_iterator(head->next);

}

const_iterator end()const

{

return const_iterator(head);

}

void empty_list()

{

head = new node;

head->next = head;

head->prev = head;

_size = 0;

}//建立头节点

list()

{

empty_list(); //初始化列表

}

~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)//在pos位置插入x

{

node* it = pos.node1;

node* newnode = new node(x);

node* prev = it->prev;

prev->next = newnode;

newnode->prev = prev;

newnode->next = it;

it->prev = newnode;

++_size;

return iterator(newnode); //返回新插入的元素的位置

}

iterator erase(iterator pos)

{

node* it = pos.node1;

node* prev = it->prev;

node* next = it->next;

delete it;

prev->next = next;

next->prev = prev;

--_size;

return iterator(next); //返回删除后的当前位置

}

list(const list<T>& it) //i1(i2)

{

int i = 0;

empty_list(); //初始化列表

for (auto e : it) //相当于自动调用迭代器，并解引用，最后迭代器再++

{

i = 1;

push_back(e);

}

}

void swap(list<T>& it)

{

std::swap(head, it.head);

std::swap(_size, it._size);

}

list operator=(list<T>it)// i1=i2 传参直接调用拷贝构造

{

swap(it);

return *this;

}

size_t size()

{

return _size;

}

private:

node* head;

size_t _size;

};

void test()

{

list<int> arr; //调用class里的初始化列表

arr.push_back(1);

arr.push_back(2);

arr.push_back(3);

arr.push_back(4);

arr.push_back(5);

arr.pop_back();

int i = 0;

list<int> brr(arr);

for (auto e : brr)

{

i = 1;

cout << e << ' ';

}

}

}

8.杂谈 

iterator begin() //可读可写

{

return iterator(head->next); //原文写的是匿名对象，也可以写成return head->next

}

iterator end()

{

return iterator(head); //原文写的是匿名对象，也可以写成return head

}

思考：为啥可以这么改写？ 

1.单参数构造函数支持隐式类型转换 ，构造函数如下：

list_iterator(node* node2)

:node1(node2)

{}

2.函数返回需要调用拷贝构造，可理解为iterator（const iterator&it）//const可加可不加

3.但是return的是node*类型数据，不是iterator类型，这时因为存在一个单参数的构造函数

list_iterator(node* node2)，编译器会将node*数据隐式转换为iterator类型对象再调用拷贝构造

 ！！！！！！！！！！！！！

类似string(const char* str);

string s1 = “hello world”;

字符指针隐式类型转换为string。