list的特性
STL中的list是指带头双向循环列表，list每个元素的存储相互独立，因为其节点存储位置独立不连续，其插入和删除不需要挪动其他元素效率比起vector更高。但也因为存储空间不连续的问题，不能做到和vector一样的随机访问。
list的模拟实现
template<class T>
struct ListNode
{
ListNode(const T& val = T())
:_pPre(nullptr)
,_pNext(nullptr)
,_val(val)
{
}
ListNode<T>* _pPre;
ListNode<T>* _pNext;
T _val;
};
//List的迭代器类
template<class T, class Ref, class Ptr>
class ListIterator
{
typedef ListNode<T>* PNode;
typedef ListIterator<T, Ref, Ptr> Self;
public:
ListIterator(PNode pNode = nullptr)
:_pNode(pNode)
{}
ListIterator(const Self& l)
{
_pNode = l.getpNode();
}
//T& operator*();
Ref operator*()
{
return _pNode->_val;
}
//T* operator->();
Ptr operator->()
{
return &_pNode->_val;
}
Self& operator++()
{
_pNode = _pNode->_pNext;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
_pNode = _pNode->_pNext;
return tmp;
}
Self& operator--()
{
_pNode = _pNode->_pPre;
return *this;
}
Self& operator--(int)
{
Self tmp(*this);
_pNode = _pNode->_pPre;
return tmp;
}
bool operator!=(const Self& l)
{
return _pNode != l.getpNode();
}
bool operator==(const Self& l)
{
return _pNode == l.getpNode();
}
PNode getpNode()const
{
return _pNode;
}
private:
PNode _pNode;
};
//list类
template<class T>
class list
{
typedef ListNode<T> Node;
typedef Node* PNode;
public:
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T&> const_iterator;
public:
///
// List的构造
list()
{
CreateHead();
}
list(int n, const T& value = T())
{
_size += n;
CreateHead();
PNode cur = _pHead;
while (n--)
{
PNode newnode = new Node(value);
cur->_pNext = newnode;
newnode->_pPre = cur;
newnode->_pNext = _pHead;
_pHead->_pPre = newnode;
cur = cur->_pNext;
}
}
template <class Iterator>
list(Iterator first, Iterator last)
{
Iterator cur = first;
while (cur != last)
{
push_back(cur.getpNode()->_val);
cur++;
}
}
list(const list<T>& l)
{
CreateHead();
for (auto& a : l)
{
push_back(a);
}
}
list<T>& operator=(const list<T> l)
{
list<T> tmp(l);
swap(tmp);
}
~list()
{
clear();
delete _pHead;
_pHead = nullptr;
}
///
// List Iterator
iterator begin()
{
return _pHead->_pNext;
}
iterator end()
{
return _pHead;
}
const_iterator begin()const
{
return _pHead->_pNext;
}
const_iterator end()const
{
return _pHead;
}
///
// List Capacity
size_t size()const
{
return _size;
}
bool empty()const
{
return _size == 0;
}
// List Access
T& front()
{
return _pHead->_pNext->_val;
}
const T& front()const
{
return _pHead->_pNext->_val;
}
T& back()
{
return _pHead->_pPre->_val;
}
const T& back()const
{
return _pHead->_pPre->_val;
}
// List Modify
void push_back(const T& val) { insert(end(), val); }
void pop_back() { erase(--end()); }
void push_front(const T& val) { insert(begin(), val); }
void pop_front() { erase(begin()); }
// 在pos位置前插入值为val的节点
iterator insert(iterator pos, const T& val)
{
PNode newnode = new Node(val);
PNode cur = pos.getpNode();
PNode prev = cur->_pPre;
newnode->_pNext = cur;
cur->_pPre = newnode;
prev->_pNext = newnode;
newnode->_pPre = prev;
_size++;
return iterator(newnode);
}
// 删除pos位置的节点，返回该节点的下一个位置
iterator erase(iterator pos)
{
PNode cur = pos.getpNode();
PNode prev = cur->_pPre;
PNode next = cur->_pNext;
prev->_pNext = next;
next->_pPre = prev;
delete cur;
_size--;
return iterator(next);
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
void swap(list<T>& l)
{
std::swap(_pHead, l.getpHead());
std::swap(_size, l.size());
}
PNode getpHead()const
{
return _pHead;
}
private:
void CreateHead()
{
_pHead = new Node;
_pHead->_pNext = _pHead;
_pHead->_pPre = _pHead;
_size = 0;
}
PNode _pHead;
size_t _size;
};迭代器失效问题
与vector不同，list插入时迭代器不会失效，因为节点相互独立的原因，所以list的插入不会改变其节点存储位置，如此一来迭代器的指向也不会有影响。
不过删除时仍会出现迭代器失效，迭代器指向的节点被删除时该迭代器失效（指向的节点失效，迭代器自然也就失效了），其余不受影响。
list与vector的区别
| vector | list | |
| 插入与删除 | 插入与删除都可能需要挪动部分元素，时间复杂度为O(n)，插入还往往伴随着扩容，又因为其需要连续的存储空间还可能出现开辟新空间，拷贝数据，释放旧空间的操作，整体效率低下。 | 插入与删除的时间复杂度均为O(1)，存储空间的独立使其不需要扩容，需要新节点时才进行申请，并且不需要挪动数据。 |
| 随机访问 | 存储空间连续，支持随机访问,查找的时间复杂度为O(1) | 不支持随机访问，查找的时间复杂度为O(n) |
| 迭代器 | 使用原生指针 | 使用被封装的原生指针 |
| 空间利用率 | 因其内存连续，不易造成内存碎片，空间利用率高，但缓存利用率高 | 因其节点是动态开辟而来，且相互独立。容易造成内存碎片，空间利用率低，但缓存利用率低 |
总结：如果需要高效存储、需要随机访问且不关心插入删除效率则使用vector。反之需要大量插入删除查找，不关心随机访问则使用list。
