C++STL--------list

文章目录

- - - 一、list链表的使用
    - 1、迭代器
    - 2、头插、头删
    - 3、insert任意位置插入
    - 4、erase任意位置删除
    - 5、push_back 和 pop_back()
    - 6、emplace_back尾插
    - 7、swap交换链表
    - 8、reverse逆置
    - 9、merge归并
    - 10、unique去重
    - 11、remove删除指定的值
    - 12、splice把一个链表的结点转移个另一个链表
    - 13、sore排序
- 二、operator->
- 三、list常用接口模拟实现

截图内容来源

一、list链表的使用

在这里插入图片描述
是一个支持O(1)时间复杂度插入和删除的链表结构，迭代器是双向的，底层是一个带头双向循环链表。

1、迭代器

在这里插入图片描述
双向迭代器：++ 、–

2、头插、头删

头插：
在这里插入图片描述
头删：

3、insert任意位置插入

在这里插入图片描述
更具迭代器来完成位置的确定

4、erase任意位置删除

在这里插入图片描述
位置用迭代器表示，也可以删除一个迭代器区间

5、push_back 和 pop_back()

头插：

在这里插入图片描述
头删:

6、emplace_back尾插

在这里插入图片描述
跟push_back有差异,push_back要插入的类型被固定，可以支持隐式类型转换。
emplace_back不支持隐式类型转换，但可以直接传要初始的值进行构造。

class pos
{
private:int _row;int _col;
public:pos(int row = 0, int col = 0):_row(row),_col(col){}};int main()
{list<pos> lt;pos p1(1, 2);lt.push_back(p1);lt.push_back(pos(2, 3));lt.push_back({ 2,3 });//隐式类型转换lt.emplace_back(p1);lt.emplace_back(pos(2,3));lt.emplace_back(2, 3);//可变模版参数return 0;
}

7、swap交换链表

在这里插入图片描述
比算法库里的swap更高效，底层是交换指向头结点。

8、reverse逆置

在这里插入图片描述
插入1到9，打印9到1

9、merge归并

在这里插入图片描述
合并完后链表x为空

10、unique去重

在这里插入图片描述
排成有序的再去重

11、remove删除指定的值

在这里插入图片描述
remove_if满足条件再删

12、splice把一个链表的结点转移个另一个链表

在这里插入图片描述
可以调整链表里面的顺序，把自己的结点转移给自己

13、sore排序

在这里插入图片描述
默认排序是升序
如果想降序要使用仿函数

让他大于就交换

int main()
{list<int> ls({ 1,-2,0,3,8,7 });for (auto c : ls){cout << c << ' ';}cout << endl;ls.sort();//升序ls.sort(greater<int>());//降序for (auto c : ls){cout << c << ' ';}return 0;
}

list 自己实现的sort是支持双向迭代器的，算法库里的sort是传随机迭代器

二、operator->

class pos
{
private:public:pos(int row = 0, int col = 0):_row(row),_col(col){}int _row;int _col;
};int main()
{list<pos> lt;pos p1(1, 2);lt.push_back(p1);list<pos>::iterator i = lt.begin();cout << i->_row;//这样写省略了一个->//相应于调用 i.operator->()->_row;return 0;
}

三、list常用接口模拟实现

#pragma once
#include <iostream>
#include <assert.h>
namespace lsh
{//List节点类template<class T>struct ListNode{ListNode(const T& val = T()):_val(val),_pPre(nullptr),_pNext(nullptr){}ListNode<T>* _pPre;ListNode<T>* _pNext;T _val;};//反向迭代器template<class Iterator,class Ref,class Ptr>struct Reverse_iterator{Iterator _it;typedef Reverse_iterator Self;Reverse_iterator(Iterator it):_it(it){}Ref operator*(){return *_it;}Ptr operator->(){return _it.operator->();}Reverse_iterator& operator++(){--_it;return *this;}Reverse_iterator& operator--(){++_it;return *this;}Reverse_iterator operator++(int){Reverse_iterator tmp = *this;--_it;return tmp;}Reverse_iterator operator--(int){Reverse_iterator tmp = *this;++_it;return tmp;}bool operator!=(const Self& l){return _it != l._it;}};//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._pNode){}Ref operator*(){return _pNode->_val;}Ptr operator->(){return &_pNode->_val;}Self& operator++(){_pNode = _pNode->_pNext;return *this;}Self& operator--(){_pNode = _pNode->_pPre;return *this;}Self operator++(int){Self tmp = *this;_pNode = _pNode->_pNext;return tmp;}Self operator--(int){Self tmp = *this;_pNode = _pNode->_pPre;return tmp;}bool operator!=(const Self& l){return _pNode != l._pNode;}bool operator==(const Self& l){return !(*this != l);}PNode Get(){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;typedef Reverse_iterator<iterator, T&, T* > reverse_iterator;typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;public://List的构造list(){CreateHead();}list(int n, const T& value = T()){CreateHead();for (int i = 0; i < n; i++){push_back(value);}_size = n;}template<class Iterator>list(Iterator first, Iterator last){CreateHead();while (first != last){push_back(*first);first++;}}list(const list<T>& l){CreateHead();for (auto c : l){push_back(c);}}list<T>& operator=(list<T> l){swap(l);return *this;}~list(){clear();delete _pHead;}/////List Iteratoriterator begin(){return (iterator)_pHead->_pNext;}iterator end(){return (iterator)_pHead;}const_iterator begin()const{return (const_iterator)_pHead->_pNext;}const_iterator end()const{return (const_iterator)_pHead;}reverse_iterator rbegin(){return (reverse_iterator)_pHead->_pPre;}reverse_iterator rend(){return (reverse_iterator)_pHead;}const_reverse_iterator rbegin() const{return (const_reverse_iterator)_pHead->_pPre;}const_reverse_iterator rend()const{return (const_reverse_iterator)_pHead;}////List Capacitysize_t size()const{return _size;}bool empty()const{return _size == 0;}///List AccessT& front(){return *(begin());}const T& front()const{return *(begin());}T& back(){return *(--end());}const T& back()const{return *(--end());}/////List Modifyvoid 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 tmp = pos.Get();PNode newnode = new Node(val);newnode->_pNext = tmp;newnode->_pPre = tmp->_pPre;tmp->_pPre->_pNext = newnode;tmp->_pPre = newnode;_size++;return newnode;}//删除pos位置的节点iterator erase(iterator pos){assert(pos != _pHead);PNode del = pos.Get();PNode next = del->_pNext;PNode pre = del->_pPre;pre->_pNext = next;next->_pPre = pre;delete del;_size--;return (iterator)next;}void clear(){while (_size){pop_back();}}void swap(list<T>& l){std::swap(_pHead, l._pHead);}private:void CreateHead(){_pHead = new Node();_size = 0;_pHead->_pPre = _pHead;_pHead->_pNext = _pHead;}PNode _pHead;size_t _size;};}