C++——list
目录
list介绍
list的函数接口
构造函数
push_front和pop_front
push_back和pop_back
insert
erase
迭代器
front和back
size
resize
empty
clear
list::sort
unique
reverse
迭代器的实现
list介绍
- list是一种可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
- list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立结点当中，在结点中通过指针指向其前一个元素和后一个元素。
- list与forward_list非常相似，最主要的不同在于forward_list是单链表，只能进行单方向迭代。
- 与其他容器相比，list通常在任意位置进行插入、删除元素的执行效率更高。
- list和forward_list最大的缺陷是不支持在任意位置的随机访问，其次，list还需要一些额外的空间，以保存每个结点之间的关联信息（对于存储的类型较小元素来说这可能是一个重要的因素）。
总的来说，list就是一个带头双向循环链表。
list的函数接口
构造函数
list<int> l1; //构造int类型的空容器 list<int> l2(10, 2); //构造含有10个2的int类型容器 list<int> l3(l2); //拷贝构造int类型的l2容器的复制品push_front和pop_front
// push_front函数用于头插，pop_front函数用于头删 list<int> l; l.push_front(1); l.push_front(0);l.pop_front()push_back和pop_back
// push_back函数用于尾插，pop_back函数用于尾删 list<int> l; l.push_back(0); l.push_back(1);l.pop_back();insert
list<int> l; l.push_back(0); l.push_back(1); l.push_back(2);list<int>::iterator pos = find(l.begin(), l.end(), 2); // 要包含algorithm库l.insert(pos, 10); // 在pos=2位置之前插入10l.insert(pos, 2, 9); // 在pos=2位置之前插入2个9erase
list<int> l; l.push_back(0); l.push_back(1);list<int>::iterator pos = find(l.begin(), l.end(), 1); if (pos != l.end()) // 一定要找到了再删除 {l.erase(pos); // 删除指定迭代器位置的元素// pos = l.erase(pos) // 也可以接受返回值，返回的是删除位置的下一个节点 }要注意的是list也有迭代器失效的问题，既然放到erase这里才讲，那就是erase的时候会导致迭代器失效。
迭代器
list<int> l(5, 2); // 正向迭代器遍历容器 list<int>::iterator it = lt.begin(); while (it != lt.end()) {cout << *it << " ";it++; }// 反向迭代器遍历容器 list<int>::reverse_iterator rit = lt.rbegin(); while (rit != lt.rend()) {cout << *rit << " ";rit++; }front和back
// size函数用于获取当前容器当中的元素个数 list<int> l; l.push_back(0); l.push_back(1); l.push_back(2); cout << l.size() << endl;size
// front函数用于获取list容器当中的第一个元素，back函数用于获取list容器当中的最后一个元素 list<int> l; l.push_back(0); l.push_back(1); l.push_back(2);cout << l.front() << endl; cout << l.back() << endl;resize
// 当所给值大于当前的size时，将size扩大到该值，扩大的数据为第二个所给值，若未给出，则默认为容器所存储类型的默认构造函数所构造出来的值。 // 当所给值小于当前的size时，将size缩小到该值。 list<int> l(5, 1); l.resize(10, 2);l.resize(2);empty
list<int> l; cout << l.empty() << endl; // 判断容器是否为空，返回的是bool类型，就是0或1clear
// clear函数用于清空容器，清空后容器的size为0。 list<int> l(5, 1); l.clear();list::sort
list<int> l; l.push_back(4); l.push_back(7); l.push_back(5); l.push_back(9);l.sort(); // 默认将容器内数据排为升序// 既然algorithm中已经有了一个sort函数，那为什么还有在list中加入这个函数呢 // 那是因为，算法库中的sort让list使用是会报错的 // 算法库中的sort要求物理空间必须是连续的// 注意：一般也不会使用list中的sort函数 // 在数据量大的时候，效率较低，不如直接把数据插入到vector中使用algorithm中的sort函数unique
// unique函数用于删除容器当中连续的重复元素，使用这个函数必须要先排序 list<int> l; l.push_back(0); l.push_back(0); l.push_back(1); l.push_back(1); l.push_back(2); l.push_back(3); l.unique();reverse
// reverse函数用于将容器当中元素的位置进行逆置 list<int> l(); l.push_back(0); l.push_back(1); l.push_back(2); l.push_back(3); l.reverse();
迭代器的实现
// 简单定义一下list的结构 template<class T> class list_node // 结点 {T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& x = T()):_data(x),_next(nullptr),_prev(nullptr){} };template<class T> struct __list_iterator // 这里使用struct不用考虑class的权限 {typedef list_node<T> Node;typedef __list_iterator<T> iterator;Node* _node; // 迭代器还是结点的指针__list_iterator(Node* node) // 用指针初始化迭代器:_node(node){}bool operator!=(const iterator& it) const{return _node != it._node; // 判断两个迭代器指针不等就可以了}T& operator*(){return _node->_data; // 解引用就是拿到结点指向的值}T* operator->() // ->运算符是使用指针来访问成员{return &(operator*()); // 拿到指针指向的数据再取地址返回这个指针类型}iterator& operator++() // ++就把下一个结点的指针赋值给_node，注意这是前置++{_node = _node->_next;return *this;} };template<class T> class list {typedef list_node<T> Node; public:typedef __list_iterator<T> iterator;void push_back(const T& x){Node* tail = _head->_prev;Node* newnode = new Node(x);tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;}iterator begin() // begin就是头结点的下一个{return iterator(_head->_next); // 使用头结点的下一个的指针构造迭代器}iterator end() // end就是头结点{return iterator(_head->_prev);}list() // 构造函数{_head = new Node;_head->_next = _head;_head->_prev = _head;} public:Node* _head; };void test01() {list<int> l;l.push_back(1);l.push_back(2);list<int>::iterator it = l.begin();while (it != l.end()){cout << it->_data << endl; // 使用->运算符重载，有的时候，list中存放的不是int类型的数据，只使用一次it->是不够的// 比如一个坐标类型，有两个成员变量，it->只能拿到这个坐标类型的指针// 但是还不能访问到这个类型的成员，所以需要使用it->->// 但这样又会显得很奇怪，所以编译器为了增加可读性进行了特殊处理，所以用一个->就可以了++it;} }// 既然有了正常的迭代器，那如果是const对象呢 // const对象使用正常迭代器时会出现权限的放大，不可以被修改 // 那有一个返回const类型的函数就可以了，例如下面这个函数T& opeartor*() {} // 这里可以添加一个返回const类型的函数 // 但是只有返回类型不一样不能构成重载 // 所以笨方法就是再写一个const迭代器类，这个类除了返回值不一样，其他的基本都一样 // 但是很忌讳这样写// 可以这样该一下模板参数 template<class T, class Ref, class Ptr> // Ref就是引用，Ptr就是指针 struct __list_iterator {typedef __list_iterator<T, Ref, Ptr> iterator;// ... }// operator*()就可以修改为 Ref opeartor*() {}// operator->()可以修改为 Ptr operator->() {}template<class T> class list {typedef list_node<T> Node; public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;const_iterator cbegin() const{return cosnt_iterator(_head->_next);}const_iterator cend() const{return cosnt_iterator(_head);}// ... }