1. list的介绍及使用
1.1 list的介绍
1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指其前一个元素和后一个元素。
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)
1.2 list的使用
list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口：
1.2.1 list的构造
1.2.2 list iterator的使用
list迭代器可以理解成一个指针，该指针指向list中的某个节点。实际它是指针的封装。
void testlist1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
list<int>::iterator it = lt.begin();
cout << *it++ << endl;
while (it != lt.end())
{
cout << *it << " ";
it++;
}
cout << endl;
}
1.2.3 list capacity
1.2.4 list element access
int main()
{
//list<int> lt(3);
vector<int> v{ 4,5 };
vector<string> tokens{ "4","13","5","/","+" };
cout<<evalRPN(tokens)<<endl;
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
//这里可以直接修改里面第一个元素的值
lt.front() = 10;
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
return 0;
}1.2.5 list modifiers
以下代码对部分接口进行测试：
void testlist3()
{
list<int> lt;
lt.push_front(1);
lt.push_front(2);
lt.push_front(3);
lt.push_front(4);
lt.push_front(5);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
list<int> lt1;
lt1.push_front(10);
lt1.push_front(20);
lt1.push_front(30);
lt1.push_front(40);
lt.swap(lt1);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl<<"头删后："<<endl;
lt.erase(lt.begin());
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
1.2.6 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]));
for (auto e : l)
{
cout << e <<" ";
}
auto it = l.begin();
while (it != l.end())
{
//此时it已经指向原来it的下一个迭代器位置
l.erase(it++); // it = l.erase(it);
//下面两行为错误写法
//l.erase(it);
//++it;
}
for (auto e : l)
{
cout << e <<endl;
}
}
2. list的模拟实现
2.1 模拟实现list
要模拟实现list，必须要熟悉list的底层结构以及其接口的含义，通过上面的学习，这些内容已基本掌握，现在我们来模拟实现list。
namespace xwy {
template<typename T>
struct listNode
{
T _data;
listNode<T>* _pre;
listNode<T>* _next;
//单参数构造函数
listNode(const T& val = T())
:_data(val),
_pre(nullptr),
_next(nullptr)
{
}
};
template<typename T, class Ref, class Ptr>
struct _list_iterator
{
// 受类域的限制
typedef listNode<T> Node;
typedef _list_iterator<T,Ref,Ptr> self;
Node* _node;
_list_iterator(Node *node=nullptr):
_node(node)
{
}
//操作符重载
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &(_node->_data);
}
self& operator--()
{
_node = _node->_pre;
return *this;
}
self operator-(int a)
{
Node* ptr = _node;
while (a--&&ptr)
{
ptr = ptr->_pre;
}
return ptr;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
self operator++(int)
{
// self tmp(*this) 拷贝构造自己
Node* tmp = _node;
_node = _node->_next;
return tmp;
}
bool operator!=(const self& node)const
{
return _node != node._node;
}
};
// 适配器 -- 复用
template<class Iterator, class Ref, class Ptr>
struct Reverse_iterator
{
Iterator _it;
typedef Reverse_iterator<Iterator, Ref, Ptr> self;
Reverse_iterator(const Iterator &it):
_it(it)
{
}
//操作符重载
Ref operator*()
{
return *_it;
}
self& operator--()
{
++_it;
return *this;
}
Ptr operator->()
{
return &(*_it);
}
self& operator++()
{
--_it;
return *this;
}
self operator++(int)
{
// self tmp(*this) 拷贝构造自己
Iterator it = _it;
--_it;
return it;
}
bool operator!=(const self& lt) const //const和const比较 ，非const和const比较
{
return lt._it != _it; //不支持那两种类型的比较，是因为不存在那两种类型比较的重载
}
};
template<typename T>
class list
{
public:
typedef listNode<T> Node;
typedef _list_iterator<T,T&,T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;
typedef Reverse_iterator<iterator,T&,T*> reverse_iterator;
typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
//无参构造函数
list()
{
empty_init();
}
template<class iterator>
list(iterator first,iterator last)
{
empty_init();
while (first != last)
{
push_back(*first);
first++;
}
}
//拷贝构造
list(const list& lt)
{
empty_init();
auto it = lt.begin();
while (it != lt.end())
{
push_back(*it);
it++;
}
}
//迭代器的实现
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}
//反向迭代器
reverse_iterator rbegin()
{
return --end();
}
reverse_iterator rend()
{
return --begin();
}
const_reverse_iterator rbegin() const
{
return --end();
}
const_reverse_iterator rend() const
{
return --begin();
}
void push_back(const T& val)
{
Node* newnode = new Node(val);
newnode->_next = _head;
_head->_pre->_next = newnode;
newnode->_pre = _head->_pre;
_head->_pre = newnode;
}
iterator erase(iterator pos) //在pos位置删除
{
Node* cur = pos._node;
Node* prev = cur->_pre;
Node* next = cur->_next;
delete cur;
prev->_next = next;
next->_pre = prev;
return next;
}
// 在pos位置前插入值为val的节点
iterator insert(iterator pos, const T& val)
{
Node* cur = pos._node;
Node* newNode = new Node(val);
newNode->_next = cur;
newNode->_pre = cur->_pre;
cur->_pre->_next = newNode;
cur->_pre = newNode;
return pos;
}
/*void push_back(const T& val)
{
insert(_head, val);
}*/
void push_front(const T& val)
{
insert(_head->_next, val);
}
void swap(list<T>& l)
{
std::swap(l._head, _head);
}
void clear()
{
//清理数据,不清头节点
iterator it = begin();
while (it != end())
{
it = erase(it);//it就是下一个位置
}
}
~list()
{
clear();
delete _head; // 只有节点是new出来，需要delete，但这个只delete 了一个节点
}
private:
void empty_init()
{
_head = new Node();
_head->_next = _head->_pre = _head;
}
Node* _head;
};2.2 list的反向迭代器
反向迭代器的++就是正向迭代器的--，反向迭代器的--就是正向迭代器的++，因此反向迭代器的实现可以借助正向迭代器，即：反向迭代器内部可以包含一个正向迭代器，对正向迭代器的接口进行包装即可.
template<class Iterator>
class ReverseListIterator
{
// 注意：此处typename的作用是明确告诉编译器，Ref是Iterator类中的类型，而不是静态成员变量
// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量
// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
public:
typedef typename Iterator::Ref Ref;
typedef typename Iterator::Ptr Ptr;
typedef ReverseListIterator<Iterator> Self;
public:
//
// 构造
ReverseListIterator(Iterator it): _it(it){}
//
// 具有指针类似行为
Ref operator*(){
Iterator temp(_it);
--temp;
return *temp;
}
Ptr operator->(){ return &(operator*());}
//
// 迭代器支持移动
Self& operator++(){
--_it;
return *this;
}
Self operator++(int){
Self temp(*this);
--_it;
return temp;
}
Self& operator--(){
++_it;
return *this;
}
Self operator--(int)
{
Self temp(*this);
++_it;
return temp;
}
//
// 迭代器支持比较
bool operator!=(const Self& l)const{ return _it != l._it;}
bool operator==(const Self& l)const{ return _it != l._it;}
Iterator _it;
};3. list与vector的对比
vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下:
