目录
list的介绍
1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3.与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
list的使用
list的构造
1.list(size_t n,const T& lt = T())
说明：构造的list中包含n个值为val的元素
2.list()
说明：构造空的list
3.list(const list& x)
说明：拷贝构造函数
4.list(InputIterator first,InputIterator last)
说明：用[first,last)区间中的元素构造list
list iterator的使用
此时，我们暂且将迭代器理解成一个指针，该指针指向list中的某个节点。
begin+end：返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin+rend：返回第一个元素的reverse_iterator，即end位置，返回最后一个元素下一个位置的reverse_iterator，即begin位置
注意：
1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
list capacity
empty：检测list是否为空，是返回true，否则返回false
size：返回list中有效节点个数
list modifiers
push_front：在list首元素前插入值为val的元素
pop_front：删除list中的第一个元素
push_back：在list尾部插入值为val的元素
pop_back：删除list中的最后一个元素
insert：在pos位置插入值为val的元素
erase：删除pos位置的元素
swap：交换两个list中的元素
clear：清空list中的有效元素
list的迭代器失效
我们将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
void TestListIterator()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array + sizeof(array) / sizeof(array[0]));
auto it = l.begin();
while (it != l.end())
{
//错误示范
//erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给
其赋值
//l.erase(it);
//++it;
//正确
it = l.erase(it);
}
}list模拟实现
namespace ghs
{
template<class T>
struct ListNode
{
ListNode(const T& x = T())
:_next(nullptr)
,_prev(nullptr)
,_data(x)
{
}
ListNode<T>* _next;
ListNode<T>* _prev;
T _data;
};
template<class T, class Ref, class Ptr>
struct ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator Self;
Node* _node;
ListIterator(Node* node)
:_node(node)
{}
//*it
//不能传值返回，*it只能传引用返回，因为除了读还有写的功能
//T& operator*()
Ref operator*()
{
return _node->_data;
}
//++it
Self& operator++()
{
_node = _node->_next;
return *this;
}
//it++
Self operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
//--it
Self& operator--()
{
_node = _node->_prev;
return *this;
}
//it--
Self operator--(int)
{
Self tmp(*this);
_node = _node._prev;
return tmp;
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
bool operator==(const Self& it)
{
return _node == it->_node;
}
//T* operator->()
Ptr operator->()
{
return &_node->_data;
}
};
//template<class T>
//struct ListConstIterator
//{
// typedef ListNode<T> Node;
// typedef ListConstIterator Self;
// Node* _node;
// ListConstIterator(Node* node)
// :_node(node)
// {}
// //*it
// //不能传值返回，*it只能传引用返回，因为除了读还有写的功能
// const T& operator*()
// {
// return _node->_data;
// }
// //++it
// Self& operator++()
// {
// _node = _node->_next;
// return *this;
// }
// //it++
// Self operator++(int)
// {
// Self tmp(*this);
// _node = _node->_next;
// return tmp;
// }
// //--it
// Self& operator--()
// {
// _node = _node->_prev;
// return *this;
// }
// //it--
// Self operator--(int)
// {
// Self tmp(*this);
// _node = _node._prev;
// return tmp;
// }
// bool operator!=(const Self& it)
// {
// return _node != it._node;
// }
// bool operator==(const Self& it)
// {
// return _node == it->_node;
// }
// const T* operator->()
// {
// return &_node->_data;
// }
//};
template<class T>
class list
{
typedef ListNode<T> Node;
public:
/*typedef ListIterator<T> iterator;
typedef ListConstIterator<T> const_iterator;*/
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;
//iterator begin()
//{
// //匿名对象
// return iterator(_head->_next);
//}
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
//如果返回值类型是const iterator，那表示迭代器本身不能被修改，而不是迭代器指向的内容不能被修改
//我们需要的是迭代器指向的内容不能被修改，const iterator不是我们需要的迭代器
const_iterator begin()const
{
return _head->_next;
}
const_iterator end()const
{
return _head;
}
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
empty_init();
}
//lt2(lt1)
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
//需要析构，一般就需要自己写深拷贝
//不需要析构，一般就不需要自己写深拷贝，默认浅拷贝就可以
void swap(list<T> lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
list<T>& operator=(list<T> lt)//()里调用了拷贝构造
{
swap(lt);
return *this;
}
//void push_back(const T& x)
//{
// Node* newnode = new Node(x);
// Node* tail = _head->_prev;
// tail->_next = newnode;
// newnode->_prev = tail;
// newnode->_next = _head;
// _head->_prev = newnode;
//}
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
void insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
//prev newnode cur
newnode->_next = cur;
cur->_prev = newnode;
prev->_next = newnode;
newnode->_prev = prev;
_size++;
}
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
_size--;
return iterator(next);
}
size_t size()const
{
return _size;
}
bool empty()
{
return _size == 0;
}
//不清除头结点，只是把数据清掉
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
private:
Node* _head;
size_t _size;
};
}