目录
1、list的介绍
2、list常用接口函数
2.1 几个构造函数
2.1.1 构造函数的模拟实现
2.2 迭代器
2.2.1 迭代器的模拟实现
2.3 容量相关的函数
3、list的增删查改
3.1 插入insert
3.2 删除erase
3.3 头插、头删、尾插、尾删
4、list需要注意的点及功能完善
4.1 list迭代器失效问题
4.2 list的sort排序
1、list的介绍
list在底层是双向链表，能够进行动态内存分配，与其他容器相比，list的插入删除要更高效。
list的特性
1、list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2、list的底层是带头双向循环链表结构，在节点中通过指针指向其前一个元素和后一个元素。
3、与其他的序列式容器相比(array，vector，deque等)，list通常在任意位置进行插入、移除元素的效率更高。
list的缺陷
list最大的缺陷是不支持任意位置的随机访问
list和vector一样也是类模板。
2、list常用接口函数
2.1 几个构造函数
| 函数声明 | 函数说明 |
|---|---|
| list (size_type n, const value_type& val = value_type()) | 构造的list中包含n个值为val的元素 |
| list() | 构造空的list |
| list (const list& x) | 拷贝构造函数 |
| list (InputIterator first, InputIterator last) | 用[first, last)区间中的元素构造list 注意：这里的区间是左闭右开 |
//无参构造
list<int> l1;
//用10个6初始化链表
list<int> l2(10, 6);
//拷贝构造
list<int> ll2(l2);vector<int> v{ 1,2,3,4 };
//用迭代器区间初始化链表
list<int> l3(v.begin(), v.end());2.1.1 构造函数的模拟实现
无参构造
void empty_init()
{_head = new Node;_head->_next = _head;_head->_prev = _head;
}list()
{empty_init();
}拷贝构造
list(const list<T>& lt)
{empty_init();for (const auto& e : lt){push_back(e);}
}赋值构造
void swap(const list<T>& tmp)
{std::swap(_head, tmp._head);
}list<T>& operator=(const list<T> lt)
{swap(lt);return *this;
}析构
void clear()
{iterator it = begin();while (it != end()){it = erase(it);}
}~list()
{clear();delete _head;_head = nullptr;
}2.2 迭代器
可以暂时将迭代器理解成指针，这个指针指向list中的某个节点。
| 函数声明 | 接口说明 |
|---|---|
| begin + end | 返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器 |
| rbegin + rend | 返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置 |
vector<int> v1{ 5,3,10,26,9,22,12,24 };
list<int> l(v1.begin(), v1.end());auto it = l.begin();
while (it != l.end())
{cout << *it << " ";it++;
}
反向迭代
2.2.1 迭代器的模拟实现
与vector不同，list的迭代器不是一个原生指针，而是封装节点指针的类，因为用户只需要得到节点中的数据而不是整个节点。
vector随机访问可以支持像it+5，it[6]这样的形式，而list不能随机访问也就不能使用operator []来访问节点，仅支持++和--操作，这个++和--也不是指针的++和--，所以要把迭代器也封装成一个类，通过重载++、--和解引用等运算符来满足需求。
//先要封装一个结点类
template<class T>
struct ListNode
{ListNode<T>* _next;ListNode<T>* _prev;T _data;ListNode(const T& x = T()):_next(nullptr), _prev(nullptr), _data(x){}
};
//封装一个迭代器类
template<class T>
struct __list_iterator
{typedef ListNode<T> Node;typedef __list_iterator<T> self;Node* _node;__list_iterator(Node* x):_node(x){}self& operator++(){_node = _node->_next;return *this;}self operator++(int){//相当于__list_iterator<T> tmp(*this);self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int);//解引用重载T& operator*(){return _node->_data;}//T operator->(){return &_node->_data;}bool operator!=(const self& s){return _node != s._node;}bool operator==(const self& s);
};迭代器的实现
const_iterator begin()const
{//这里是单参数类型支持隐式类型转换//return const_iterator(_head->_next);return _head->_next;
}const_iterator end()const
{return _head;
}iterator begin()
{return _head->_next;
}iterator end()
{return _head;
}
2.3 容量相关的函数
| 函数 | 接口说明 |
|---|---|
| empty | 检测list是否为空，是返回true，否则返回false |
| size | 返回list中有效节点的个数 |
这里个函数我们学会使用即可。
3、list的增删查改
访问头部和尾部数据
| 函数 | 功能 |
|---|---|
| front() | 取到头节点数据的引用 |
| back() | 返回尾节点数据的引用 |
3.1 插入insert
iterator insert(iterator pos, const T& x)
{Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;//这里是为了管理_sizereturn newnode;
}3.2 删除erase
将待删除的节点的前后节点先保存起来，再删除pos出节点，将前后节点连接起来。
iterator erase(iterator pos)
{assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;--_size;return next;
}3.3 头插、头删、尾插、尾删
//尾插
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());
}
4、list需要注意的点及功能完善
4.1 list迭代器失效问题
list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，pos指向的节点的，改变的只是连接关系，位置始终都是一个位置。
只有在删除时才会失效，这个位置的数据被删除后，连接关系被改变，此位置就不在原链表中了，此时失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
4.2 list的sort排序
由于list是带头结点的双向循环链表，而算法库中的sort底层是快排，需要传入随机访问迭代器，所以list并不能使用算法库的sort。那么list的sort是怎么一回事呢？
list中给了一个适合自己的sort，这个sort实质上是归并排序，但是直接使用这个sort比list的数据先push_back到vector中，再使用算法库的sort，排完序后再导入list中的三步还要慢。
所以我们通常不使用list自己的sort。