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; // 空list list<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; } }

五、感言

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