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
explicit list (const allocator_type& alloc = allocator_type());构造的list中包含n个值为val的元素explicit list (size_type n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type());用 [first, last) 区间中的元素构造 listtemplatelist (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type()); 拷贝构造函数list (const list& x);
begin + end返回第一个元素的迭代器 + 返回最后一个元素下一个位置的迭代器rbegin + rend返回第一个元素的 reverse_iterator, 即 end 位置 , 返回最后一个元素下一个位置的 reverse_iterator, 即 begin 位置【注意】1. begin 与 end 为正向迭代器,对迭代器执行 ++ 操作,迭代器向后移动2. rbegin(end) 与 rend(begin) 为反向迭代器,对迭代器执行 ++ 操作,迭代器向前移动
list capacityempty检测 list 是否为空,是返回 true ,否则返回 falsesize返回 list 中有效节点的个数
list element access
front返回 list 的第一个节点中值的引用back返回 list 的最后一个节点中值的引用
list modifierspush_front在 list 首元素前插入值为 val 的元素pop_front删除 list 中第一个元素push_back在 list 尾部插入值为 val 的元素pop_back删除 list 中最后一个元素insert在 list position 位置中插入值为 val 的元素erase删除 list position 位置的元素swap交换两个 list 中的元素clear清空 list 中的有效元素
首先封装好一个结点:
为了方便我们在list中利用typedef简化结点的表达方式
typedef list_node
Node; list成员变量只需要一个哨兵位头节点:
首先实现list的迭代器使其能够像vector那样利用迭代器进行数据的访问,我们想要使list迭代器像vector一样支持++访问下一个位置的数据,但是list结点之间不一定是连续的,正常的对指针++是无法访问到下一个结点的数据的,因此,list迭代器的实现不同于vector可以直接将指针作为迭代器,list需要将结点指针作为一个list迭代器类的成员变量进行封装。然后重载++等各种运算符,使其在表示上同vector一样,同时考虑到普通迭代器和const迭代器的访问区别,一般的直接在普通迭代器基础上加const的方式也变得不可行了,因此这里通过增加模板参数实现const迭代器,具体过程如下:
迭代器实现完成后,就是list剩余函数的实现了
完整代码
#include #include using namespace std; namespace my_list { template<class T> struct list_node { list_node* _next; list_node* _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_nodeNode; typedef __list_iteratorself; 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) const { return _node != it._node; } bool operator==(const self& it) const { return _node == it._node; } }; template<class T> class list { typedef list_nodeNode; public: typedef __list_iteratoriterator; typedef __list_iteratorconst T&, const T*> const_iterator; iterator begin() { _head->_next;//单参数的构造函数支持隐式类型转换,因为这里返回的时iterator,iterator的构造函数是单参数的 } iterator end() { _head; } const_iterator begin() const { _head->_next; } const_iterator end() const { _head; } list() { _head = new Node; _head->_next = _head; _head->_prev = _head; } list(const list& lt) { _head = new Node; _head->_next = _head; _head->_prev = _head; for (auto& e : lt) { push_back(e); } } void swap(list& lt) { std::swap(_head, lt._head); } list& operator=(list lt) { swap(lt); return *this; } ~list() { clear(); delete _head; _head = nullptr; } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } } 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; } void pop_back() { erease(--end()); } void pop_front() { erease(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->_next = cur; cur->_prev = newnode; newnode->_prev = prev; 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; return next; } size_t size() { size_t sz = 0; iterator it = begin(); while (it != end()) { ++sz; ++it; } return sz; } private: Node* _head; }; }
vector list 底层结构 动态顺序表,一段连续空间 带头结点的双向循环列表 随机访问 支持随机访问,访问某个元素的效率是O(1) 不支持随机访问,访问某个元素效率是O(N) 插入和删除 任意位置插入和删除效率低,需要搬移元素,时间复杂度为O(N),插入时有可能需要增容,增容:开辟新空间,拷贝元素,释放旧空间,导致效率更低 任意位置插入和删除效率高,不需要搬移元素,时间复杂度为O(1) 空间利用率 底层为连续空间,不容易造成内存碎片,空间利用率高,缓存利用率高 底层节点动态开辟,小节点容易造成内存碎片,空间利用率低,缓存利用率低 迭代器 原生态指针 对原生态指针(节点指针)进行封装 迭代器失效 在插入元素时,要给所有的迭代器重新赋值,因为插入元素可能导致重新扩容,致使原来的迭代器失效,删除时,当前迭代器需要重新赋值,否则会失效 插入元素不会导致迭代器失效,删除元素时,只会导致当前迭代器失效,其他迭代器不受影响 使用场景 需要高效存储,支持随机访问,不关心插入删除效率 大量插入和删除操作,不关心随机访问