一级目录：list的介绍
1.在数据结构中，我们都学过list是一个链表，有很多分类，比如单向链表，双向链表，循环链表等等…，但在STL中，list是一个容器，毋庸置疑，是用来保存链表与数据结构中的list有相似之处，但是在实现的时候会更加的绝妙，让人佩服。
首先，我们先看看文档中对STL中list的介绍：
- list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
- list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
- list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
- 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
- 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)
2.list的优缺点：
在底层，list的实现方式是双向循环的链表，所以其优缺点与数据结构中的链表是相似的。
优点：
①：由于是链表的存储，所以在任意位置的删除和插入效率非常高，不需要移动数据。
②：可以进行大量的插入和删除，要多少申请多少，不用担心申请过多的不需要空间。
缺点：
①：不支持随机访问，每次访问都必须从头节点（或者指定节点）开始往后（或者往前）逐个访问，效率比较低。
②：底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低。
3.迭代器
迭代器:目前看来就跟指针的操作是相同的，但是它不是传统指针，而是相当于一个被封装了的指针，并且其操作都是通过操作运算符进行完成的，并且操作和使用与指针相类似。
但是在使用的时候，会存在迭代器失效的问题：
迭代器失效是在进行删除节点的操作中出现的，因为会存在将该节点删除后，再对该节点的迭代器进行操作，这样会使迭代器失效，例如如下操作：
list<int> L;
iterator it = L.begin();
while(it != L.end())
{
L.erase(it);
it++;
}
while(it != L.end())
{
L.erase(it++);
}
二级目录：list接口
由于在C++中，对于list的使用已经拥有了完整的代码，所以在实现一些有关链表的操作时，我们不需要再重新编写代码，可以使用关于list的接口去调用底层已经实现好的操作。
有关list的接口如下：
1.list的构造接口：
list()
list (size_type n, const value_type& val = value_type())
list (const list& x)
list (InputIterator first, InputIterator last)
2.迭代器的接口：
（为了保证迭代器能像指针一样被使用，所以迭代器的各种使用方法都是经过运算符重载）
iterator begin();
iterator end();
3.list的容量：
bool empty();
int size();
4.list元素的访问：
_Ty& front();
_Ty& back();
5.list函数方法接口:
void push_front(value_type a);
void Pop_front();
void push_back(value_type a);
void Pop_back();
iterator insert(iterator _P, const _Ty& _X = _Ty());
iterator erase(iterator _P);
void clear();
void swap(list<int>& L);
三级目录：list的模拟实现
namespace m_list
{
template<typename _Ty>
class list
{
public:
struct _Node
{
struct _Node* _Prev;
struct _Node* _Next;
_Ty _Value;
};
public:
typedef _Node* _Nodeptr;
typedef size_t size_type;
typedef _Ty* pointer_type;
typedef _Ty& reference_type;
typedef _Ty value_type;
typedef const _Ty* const_pointer_type;
typedef const _Ty& const_reference_type;
public:
list():_Head(_BuyNode()),_Size(0)
{}
public:
void push_back(value_type a)
{
insert(end(),a);
}
void push_front(value_type a)
{
insert(begin(), a);
}
void Pop_back()
{
erase(--end());
}
void Pop_front()
{
erase(begin());
}
public:
class iterator
{
friend class list;
public:
iterator()
{}
iterator(_Nodeptr P) :_Ptr(P)
{}
_Ty operator*()
{
return _Ptr->_Value;
}
_Ty* operator->()
{
return &(_Ptr->_Value);
}
iterator& operator++()
{
_Ptr = _Ptr->_Next;
return (*this);
}
iterator operator++(int)
{
iterator r_Ptr = *this;
++*this;
return r_Ptr;
}
iterator& operator--()
{
_Ptr = _Ptr->_Prev;
return (*this);
}
iterator operator--(int)
{
iterator r_Ptr = *this;
--*this;
return r_Ptr;
}
bool operator==(iterator& X)
{
return _Ptr == X._Ptr;
}
bool operator!=(iterator& X)
{
return !(_Ptr == X._Ptr);
}
_Nodeptr _Mynode()const
{
return _Ptr;
}
private:
_Nodeptr _Ptr;
};
public:
iterator insert(iterator _P, const _Ty& _X = _Ty())
{
_Nodeptr s = _P._Mynode();
s->_Prev = _BuyNode(s, s->_Prev);
s = s->_Prev;
s->_Prev->_Next = s;
s->_Value = _X;
++_Size;
return (iterator(s));
}
iterator erase(iterator _P)
{
_Nodeptr _S = (_P++)._Mynode();
_S->_Next->_Prev = _S->_Prev;
_S->_Prev->_Next = _S->_Next;
_Size--;
free(_S);
_S = nullptr;
return (iterator(_P));
}
iterator erase(iterator _F, iterator _L)
{
while (_F != _L)
erase(_F++);
return (_F);
}
public:
iterator begin()
{
return iterator(_Head->_Next);
}
iterator end()
{
return iterator(_Head);
}
public:
bool empty()
{
return _Size == 0;
}
int size()
{
return _Size;
}
public:
_Ty& front()
{
return _Head->_Next->_Value;
}
_Ty& back()
{
return _Head->_Prev->_Value;
}
public:
void clear()
{
erase(begin(), end());
}
void swap(list<int>& L)
{
std::swap(_Head, L._Head);
}
private:
_Nodeptr _BuyNode(_Nodeptr _Narg = 0, _Nodeptr _Parg = 0)
{
_Nodeptr s = (_Nodeptr)malloc(sizeof(_Node));
s->_Next = _Narg != 0 ? _Narg : s;
s->_Prev = _Parg != 0 ? _Parg : s;
return s;
}
private:
_Nodeptr _Head;
size_type _Size;
};
};
|