C++_STL之list篇

一、list的介绍

  std::list是C++标准模板库(STL)中的一个双向链表容器。与vector和deque不同，list不支持随机访问，但它在任何位置插入和删除元素都非常高效。

1.基本特性

(1)双向链表结构：每个元素都包含指向前驱和后继的指针

(2)非连续存储：元素分散存储在内存中，通过指针连接

(3)时间复杂度：

        任意位置插入/删除：O(1)

        随机访问：O(n)

        遍历：O(n)

二、list常用操作

        我这里就通过调试来带大家看一下每个函数的效果。

1.创建和构造

        列举了一些list构造时的基础用法.

#include <iostream>
#include <list>
using namespace std;int main()
{list<int> l1;               // 空listlist<int> l2(5);            // 包含5个默认构造的元素(0)list<int> l3(5, 10);        // 包含5个值为10的元素list<int> l4 = { 1, 2, 3 };   // 初始化列表list<int> l5(l4);           // 拷贝构造list<int> l6(l5.begin(), l5.end()); // 通过迭代器范围构造return 0;
}

        

2.迭代器

由于list不支持随机访问，只能通过迭代器或front/back方法访问元素：

list<int> l = { 1, 2, 3, 4, 5 };cout << l.front()<<endl;  // 第一个元素 (1)
cout << l.back()<<endl;   // 最后一个元素 (5)// 遍历list
for (auto it = l.begin(); it != l.end(); ++it) {cout << *it << " ";
}
cout << endl;
// C++11起可用范围for循环
for (int val : l) {cout << val << " ";
}
return 0;

 迭代器构造：

3.拷贝构造

4.clear()

        效果：清空链表中所有数据。

5.size()

        返回链表中节点的个数

6.push_back(const T& x)

        在链表尾部插入值为x的节点。

7.push_front(const T& x)

        在链表头部插入值为x的节点。

8.insert(iterator pos, const T& x)

        在第pos个位置插入值为x的节点。

9.pop_back()

        删除尾部元素

10.pop_front()

        删除头部元素

11.erase(iterator pos)

        删除第pos位置的元素

三、list的模拟实现

1.构造函数

        首先我们可以通过STL库学习一下list的基本实现方法，然后自己根据SLTL库中的代码模拟实现一个list。

        通过库中代码，我们需要先实现出list底层节点的模板以及迭代器所需要的模板，然后在构造函数。代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include <assert.h>namespace lwf
{//创建模板结构体template<class T>struct list_node{list_node<T>* _next;list_node<T>* _prev;T _val;list_node(const T& val = T()):_next(nullptr), _prev(nullptr), _val(val){}};//创建模板结构体template<class T, class Ref, class Ptr>struct _list_iterator{typedef list_node<T> Node;typedef _list_iterator<T, Ref, Ptr> self;Node* _node;_list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_val;}Ptr operator->(){return &_node->_val;}self& operator++(){_node = _node->_next;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}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;}};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;void empty_init(){_head = new Node;_head->_prev = _head;_head->_next = _head;_size = 0;}list(){empty_init();}list(const list<T>& It){empty_init();for (auto& e : It){push_back(e);}}private:Node* _head;size_t _size;};
}

2.迭代器

		iterator begin(){//return iterator(_head->next);return _head->_next;}iterator end(){return _head;}const_iterator begin()const{//return iterator(_head->next);return _head->_next;}const_iterator end()const{return _head;}

3.拷贝构造

        拷贝构造的实现就是将原有的list变量拷贝给被拷贝对象深拷贝。

		list(const list<T>& It){empty_init();for (auto& e : It){push_back(e);}}void swap(list<T> It){std::swap(_head, It._head);std::swap(_size, It._size);}list<T>& operator=(list<T> It)//list& operator=(list<T> It)	这样写也可以{swap(It);return *this;}

4.clear()

        通过迭代器来将list中元素逐个删除

		void clear(){iterator it=begin();while (it != end()){it = erase(it);}_size = 0;}

5.size()

        返回内部元素_size（_size一直是在统计list中元素的个数）即可。

		size_t size(){return _size;}

6.insert(iterator pos, const T& x)

        首先需要创建一个新节点，然后通过双链表结构的思路将节点插入所需要插入的位置，双链表在前面的博客中有实现过，需要的可自行查看。。

		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;cur->_prev = newnode;newnode->_next = cur;++_size;//解决迭代器失效问题return newnode;}

7.push_back(const T& x)

        在list尾部插入x，此时我们这里可以巧妙的运用上面的insert(iterator pos, const T& x)函数来实现。

		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;*/insert(end(), x);}

8.push_front(const T& x)

        在list头部插入x，此时我们这里也可以巧妙的运用上面的insert(iterator pos, const T& x)函数来实现。

		void push_front(const T& x){insert(begin(), x);}

9.erase(iterator pos)

        删除list中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;}

10.pop_back()

         删除list的尾部，此时我们这里也可以巧妙的运用上面的erase(iterator pos)函数来实现。

		void pop_back(){erase(--end());}

11.pop_front()

         删除list的头部，此时我们这里也可以巧妙的运用上面的erase(iterator pos)函数来实现。

		void pop_front(){erase(begin());}

12.析构函数

        这里我们可以直接调动clear()函数来清除链表中的节点，然后释放private中的_head节点即可。

		~list(){clear();delete _head;_head = nullptr;}

四、实现的整体代码。

        这里是自我实现的所有代码的集合，需要的可自行拿取。

#pragma once#include<iostream>
using namespace std;
#include <assert.h>namespace lwf
{template<class T>struct list_node{list_node<T>* _next;list_node<T>* _prev;T _val;list_node(const T& val = T()):_next(nullptr), _prev(nullptr), _val(val){}};template<class T,class Ref,class Ptr>struct _list_iterator{typedef list_node<T> Node;typedef _list_iterator<T, Ref, Ptr> self;Node* _node;_list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_val;}Ptr operator->(){return &_node->_val;}self& operator++(){_node = _node->_next;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}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;}};/*template<class T>struct _list_const_iterator{typedef list_node<T> Node;Node* _node;_list_const_iterator(Node* node):_node(node){}const T& operator*(){return _node->val;}_list_const_iterator<T>& operator++(){_node = _node->_next;return *this;}_list_const_iterator<T> operator++(int){_list_const_iterator<T> tmp(*this);_node = _node->_next;return tmp;}bool operator!=(const _list_const_iterator<T>& it)const{return _node != it._node;}bool operator==(const _list_const_iterator<T>& it)const{return _node == it._node;}};*/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;iterator begin(){//return iterator(_head->next);return _head->_next;}iterator end(){return _head;}const_iterator begin()const{//return iterator(_head->next);return _head->_next;}const_iterator end()const{return _head;}void empty_init(){_head = new Node;_head->_prev = _head;_head->_next = _head;_size = 0;}list(){empty_init();}list(const list<T>& It){empty_init();for (auto& e : It){push_back(e);}}void swap(list<T> It){std::swap(_head, It._head);std::swap(_size, It._size);}list<T>& operator=(list<T> It)//list& operator=(list<T> It)	这样写也可以{swap(It);return *this;}~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it=begin();while (it != end()){it = erase(it);}_size = 0;}size_t size(){return _size;}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;*/insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}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;cur->_prev = newnode;newnode->_next = cur;++_size;//解决迭代器失效问题return newnode;}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;}private:Node* _head;size_t _size;};void Test_1(){list<int> It;It.push_back(1);It.push_back(2);It.push_back(3);It.push_back(4);It.push_front(5);It.push_front(6);It.push_front(7);It.push_front(8);for (auto& e : It){cout << e << " ";}cout << endl;It.pop_back();It.pop_front();for (auto& e : It){cout << e << " ";}cout << endl;}void Test_2(){list<int> It;It.push_back(1);It.push_back(2);It.push_back(3);It.push_back(4);It.push_front(5);It.push_front(6);It.push_front(7);It.push_front(8);for (auto& e : It){cout << e << " ";}cout << endl;It.pop_back();It.pop_front();for (auto& e : It){cout << e << " ";}cout << endl;It.clear();It.push_front(50);It.push_front(60);It.push_front(70);It.push_front(80);for (auto& e : It){cout << e << " ";}cout << endl;cout << It.size() << endl;}void Test_3(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout << e << " ";}cout << endl;list<int> lt1(lt);for (auto e : lt1){cout << e << " ";}cout << endl;list<int> lt2;lt2.push_back(10);lt2.push_back(20);lt2.push_back(30);lt2.push_back(40);for (auto e : lt2){cout << e << " ";}cout << endl;lt1 = lt2;for (auto e : lt1){cout << e << " ";}cout << endl;}
}

五、感言

        家人们创作不易，在这里感谢各位大佬和友友们的支持，如果各位有所收获，不介意的话给我点个赞再走吧，感谢大家！