讨论stl链表
讨论链表
- list迭代器失效
- list的模拟实现
- 创建结点类
- 链表迭代器
- 完成实现代码
- list与vector
链表是一个序列容器，在任意位置都可以用常数时间插入或者删除，并且可以在两个方向进行迭代。
list迭代器失效
迭代器失效指迭代器所指向的结点无效，即该结点被删除了。
- list的底层结构是双向带头循环链表，因此向list中插入数据是不会造成迭代器失效。
- 但删除数据时，指向删除结点的迭代器会失效，其他迭代器不会受影响。
list的模拟实现
创建结点类
- 链表是由一个一个结点组成，结点中存放储存的元素已经指向下一个以及前一个的指针。
template struct list_node { T _val; list_node *_prev; list_node *_next; list_node(const T &val = T()) : _val(val), _prev(nullptr), _next(nullptr) {} };链表迭代器
- 链表的迭代器不同于顺序表。顺序表的迭代器可以直接返回头部和尾部指针的位置。++操作只需要移动相应字节数的指针即可完成。
- 链表迭代器++操作不能依靠简单的指针++完成，因为不是连续空间，因此需要封装一层结点结构，以_node = _node->next来达到++的效果。
template struct __list_iterator { typedef list_node node; typedef __list_iterator self; node *_node; __list_iterator(node *node = nullptr) : _node(node) {} 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; } Ref operator*() { return _node->_val; } Ptr operator->() { return &_node->_val; } bool operator!=(const self &s) { return _node != s._node; } bool operator==(const self &s) { return _node == s._node; } };- 其中Ref和Ptr模板为传入引用或者指针对象区分const和非const的模板。
完成实现代码
namespace max { template struct list_node { T _val; list_node *_prev; list_node *_next; list_node(const T &val = T()) : _val(val), _prev(nullptr), _next(nullptr) {} }; // 迭代器封装 template struct __list_iterator { typedef list_node node; typedef __list_iterator self; node *_node; __list_iterator(node *node = nullptr) : _node(node) {} 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; } Ref operator*() { return _node->_val; } Ptr operator->() { return &_node->_val; } bool operator!=(const self &s) { return _node != s._node; } bool operator==(const self &s) { return _node == s._node; } }; template class list { typedef list_node node; typedef __list_iterator iterator; typedef __list_iterator const_iterator; public: void empty_init() { _head = new node(); _head->_next = _head; _head->_prev = _head; _size = 0; } list() { empty_init(); } list(int n, const T &val = T()) { empty_init(); for (int i = 0; i _prev; end->_next = newNode; newNode->_prev = end; newNode->_next = _head; _head->_prev = newNode; ++_size; } void push_front(const T &val) { node *newNode = new node(val); node *next = _head->_next; newNode->_next = next; next->_prev = newNode; _head->_next = newNode; newNode->_prev = _head; } void pop_back() { assert(_head->_next != _head); node *del = _head->_prev; _head->_prev = del->_prev; del->_prev->_next = _head; delete del; del = nullptr; --_size; } void pop_front() { assert(_head->_next != _head); node *del = _head->_next; _head->_next = del->_next; del->_next->_prev = _head; delete del; del = nullptr; --_size; } iterator begin() { return iterator(_head->_next); } iterator end() { return iterator(_head); } const_iterator begin() const { return const_iterator(_head->_next); } const_iterator end() const { return const_iterator(_head); } iterator insert(iterator pos, const T &val) { node *newNode = new node(val); node *prev = pos._node->_prev; prev->next = newNode; newNode->_prev = prev; newNode->_next = pos._node; pos._node->_prev = newNode; ++_size; return iterator(newNode); } iterator erase(iterator pos) { assert(_head != _head->_next); node *cur = pos._node; node *next = cur->_next; node *prev = cur->_prev; prev->_next = next; next->_prev = prev; delete cur; cur = nullptr; --_size; return iterator(next); } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); --_size; } } size_t size() const { return _size; } private: node *_head; size_t _size; }; }list与vector
- 因vector和list底层结构不同，因此在使用场景上存在一定差异。
vector list 底层结构 动态顺序表，一段连续的空间。 带头双向循环链表 随机访问 支持随机访问，效率为O(1)。 不支持随机访问，访问某个元素的效率为O(N)。 插入和删除 尾插和尾删时效率是O(1)。除此之外插入删除的效率都很低，因为需要移动数据，若插入大量数据还涉及到扩容，异地扩容需要拷贝元素和释放旧空间，效率很低。 任意位置插入和删除数据效率为O(1)。不需要移动数据。 空间利用率 底层为连续空间，不容易产生内存碎片，利用率高，缓存利用率高。 底层为动态开辟的小结点，容易造成内存碎片，空间利用率低，缓存利用率低。 迭代器 原生态指针。 对原生态指针进行封装。 迭代器失效 插入元素时可能会造成迭代器失效，因为可能会异地扩容。删除元素时当前迭代器会失效。 插入元素时不会造成迭代器失效，删除元素时会造成当前迭代器失效，其他迭代器不受影响。
- 因vector和list底层结构不同，因此在使用场景上存在一定差异。
- 其中Ref和Ptr模板为传入引用或者指针对象区分const和非const的模板。
- 链表迭代器++操作不能依靠简单的指针++完成，因为不是连续空间，因此需要封装一层结点结构，以_node = _node->next来达到++的效果。
- 链表的迭代器不同于顺序表。顺序表的迭代器可以直接返回头部和尾部指针的位置。++操作只需要移动相应字节数的指针即可完成。
- 链表是由一个一个结点组成，结点中存放储存的元素已经指向下一个以及前一个的指针。
免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们，邮箱：ciyunidc@ciyunshuju.com。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!
