list的介绍及使用
list的介绍
1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)
list的使用
list的构造
函数名称 |
函数作用 |
list(size_t type n,const value_type |
构造的list中包含n个值为val的元素 |
list() |
构造空list |
list(const list&x) |
拷贝构造函数 |
list(first,last) |
迭代器区间中的元素构造list |
list<int> lt1(10, 1); list<int> lt2; list<int> lt3(lt1); list<int> lt4(lt3.begin(), lt3.end()); list<int>::iterator lt = lt4.begin(); while (lt != lt4.end()) { cout << *lt << " "; lt++; } cout << endl; for (auto e : lt4) { cout << e << " "; } cout << endl;
list迭代器的使用
函数名称 |
函数作用 |
begin+end |
返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器 |
rbegin+rend |
返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的 reverse_iterator,即begin位置 |
list的增删查改
函数名称 |
函数作用 |
push_back |
在list尾部插入值为val的元素 |
push_front |
在list首元素前插入值为val的元素 |
pop_back |
删除list中最后一个元素 |
pop_front |
删除list中第一个元素 |
insert |
在list position 位置中插入值为val的元素 |
erase |
删除list position位置的元素 |
list<int> lt(5,9); //头插 lt.push_front(1); //尾插 lt.push_back(2); for (auto e : lt) { cout << e << " "; } cout << endl; //尾删 lt.pop_back(); //头删 lt.pop_front(); for (auto e : lt) { cout << e << " "; } cout << endl; lt.insert(lt.begin(), 30); for (auto e : lt) { cout << e << " "; } cout << endl; lt.erase(lt.begin()); for (auto e : lt) { cout << e << " "; }
list的模拟实现
list通过一个一个结构体的结点实现，节点中包括指向下一个位置、指向前一个位置的指针和有效数值组成。
结点的封装
使用struct而不是class是因为默认为公开的
template<class T> //封装结点 struct list_node { list_node(const T& x=T()) :_data(x) ,_next(nullptr) ,_prev(nullptr) { } T _data; list_node* _next; list_node* _prev; };
迭代器的封装
list和顺序表最大的不同是list物理上不连续，需要使用指针进行移动直线下一个或者指向其他的操作，而不像顺序表物理上是连续的，++、--都可以拿到有效数据；因此需要对迭代器单独封装。
//迭代器封装 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) {} self& operator++() { _node = _node->_next; return *this; } self& operator--() { _node = _node->_prev; return *this; } self operator++(int) { self tmp(*this); _node = _node->_next; return tmp; } self operator--(int) { self tmp(*this); _node = _node->_prev; return tmp; } Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } bool operator!=(const self& s) { return _node != s._node; } bool operator==(const self& s) { return _node == s._node; } };
list成员变量
指向结构体节点的指针和有效数据的个数
Node* _node; size_t _size;
构造函数
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() { _node = new Node; _node->_next = _node; _node->_prev = _node; _size = 0; } list() { empty_init(); }
拷贝构造函数
list(list<T>& x) { empty_init(); for (auto e : x) { push_back(e); } }
operator=
void swap(list<T>& lt) { std::swap(_node, lt._node); std::swap(_size, lt._size); } list<int>& operator=(list<int> lt) { swap(lt); return *this; }
析构函数和清理空间
~list() { clear(); delete _node; _node = nullptr; } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } }
insert
void insert(iterator pos, const T& x) { Node* cur = pos._node; Node* newnode = new Node(x); Node* prev = cur->_prev; prev->_next = newnode; newnode->_next = cur; cur->_prev = newnode; newnode->_prev = prev; _size++; }
erase
iterator erase(iterator pos) { Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev; return next; }
push_back、push_front、pop_back、pop_front
void push_back(const T& x) { insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } void pop_front() { erase(begin()); } void pop_back() { erase(--end()); }
begin+end、cbegin+cend
const_iterator begin() const { return const_iterator(_node->_next); } const_iterator end() const { return const_iterator(_node); } iterator end() { return _node; } iterator begin() { return _node->_next; }
list和vector的对比
vector |
list |
|
底 |
动态顺序表，一段连续空间 |
带头结点的双向循环链表 |
随 |
支持随机访问，访问某个元素效率O(1) |
不支持随机访问，访问某个元素 |
插 |
任意位置插入和删除效率低，需要搬移元素，时间复杂 |
任意位置插入和删除效率高，不 |
空 |
底层为连续空间，不容易造成内存碎片，空间利用率 |
底层节点动态开辟，小节点容易 |
迭 |
原生态指针 |
对原生态指针(节点指针)进行封装 |
迭 |
在插入元素时，要给所有的迭代器重新赋值，因为插入 |
插入元素不会导致迭代器失效， |
使 |
需要高效存储，支持随机访问，不关心插入删除效率 |
大量插入和删除操作，不关心随 |
