C++--list的使用和模拟实现

C++--list的使用和模拟实现

文章目录

​​前言​​​​一、list的介绍及使用​​

​​1.1 list的介绍​​​​1.2 list的使用​​

​​1.2.1 list的构造​​​​1.2.2 list iterator的使用​​​​1.2.3 list capacity​​​​1.2.4 list element access​​​​1.2.5 list modifiers​​​​1.2.6 list的迭代器失效​​

​​二、list的模拟实现​​

​​2.1 模拟实现list​​​​2.2对模拟的rose::list进行测试​​

​​三、list与vector的对比​​​​总结​​

前言

今天我们学的是C++的STL容器中的list，是一个双向的带头的链表，在任意位置的插入和删除的时间复杂度为O(1)，今天我们首先结合C++中list文档了解关于list容器的函数接口来实现链表的增删查改等内容，到文章最后我们自己也来模拟实现list容器。

​​正文开始​​

一、list的介绍及使用

1.1 list的介绍

1.2 list的使用

list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展 的能力。以下为list中一些常见的重要接口

1.2.1 list的构造

// constructing lists#include #include int main(){ std::list l1; // 构造空的l1 std::list l2(4, 100); // l2中放4个值为100的元素 std::list l3(l2.begin(), l2.end()); // 用l2的[begin(), end()）左闭右开的区间构造l3 std::list l4(l3); // 用l3拷贝构造l4 // 以数组为迭代器区间构造l5 int array[] = { 16,2,77,29 }; std::list l5(array, array + sizeof(array) / sizeof(int)); // 用迭代器方式打印l5中的元素 for (std::list::iterator it = l5.begin(); it != l5.end(); it++) std::cout << *it << " "; std::cout << endl; // C++11范围for的方式遍历 for (auto& e : l5) std::cout << e << " "; std::cout << endl; return 0;}

其他list的对象也可以按照这个方法打印

1.2.2 list iterator的使用

【注意】begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

1.2.3 list capacity

1.2.4 list element access

1.2.5 list modifiers

#include using namespace std;void PrintList(list& l) { for (auto& e : l) cout << e << " "; cout << endl;}//=====================================================================================// push_back/pop_back/push_front/pop_frontvoid TestList1(){ int array[] = { 1, 2, 3 }; list L(array, array + sizeof(array) / sizeof(array[0])); // 在list的尾部插入4，头部插入0 L.push_back(4); L.push_front(0); PrintList(L); // 删除list尾部节点和头部节点 L.pop_back(); L.pop_front(); PrintList(L);}//=====================================================================================// insert /erase void TestList2(){ int array1[] = { 1, 2, 3 }; list L(array1, array1 + sizeof(array1) / sizeof(array1[0])); // 获取链表中第二个节点 auto pos = ++L.begin(); cout << *pos << endl; // 在pos前插入值为4的元素 L.insert(pos, 4); PrintList(L); // 在pos前插入5个值为5的元素 L.insert(pos, 5, 5); PrintList(L); // 在pos前插入[v.begin(), v.end)区间中的元素 vector v{ 7, 8, 9 }; L.insert(pos, v.begin(), v.end()); PrintList(L); // 删除pos位置上的元素 L.erase(pos); PrintList(L); // 删除list中[begin, end)区间中的元素，即删除list中的所有元素 L.erase(L.begin(), L.end()); PrintList(L);}// resize/swap/clearvoid TestList3(){ // 用数组来构造list int array1[] = { 1, 2, 3 }; list l1(array1, array1 + sizeof(array1) / sizeof(array1[0])); PrintList(l1); list l2; // 交换l1和l2中的元素 l1.swap(l2); PrintList(l1); PrintList(l2); // 将l2中的元素清空 l2.clear(); cout << l2.size() << endl;}int main(){ TestList1(); //TestList2(); //TestList3(); return 0;}

list中还有一些操作，需要用到时大家可参阅list的文档说明

1.2.6 list的迭代器失效

前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节 点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代 器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

void TestListIterator1(){ int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; list l(array, array + sizeof(array) / sizeof(array[0])); auto it = l.begin(); while (it != l.end()) { // erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值 l.erase(it); ++it; }}// 改正void TestListIterator(){ int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; list l(array, array + sizeof(array) / sizeof(array[0])); auto it = l.begin(); while (it != l.end()) { l.erase(it++); // it = l.erase(it); }}

二、list的模拟实现

2.1 模拟实现list

要模拟实现list，必须要熟悉list的底层结构以及其接口的含义，通过上面的学习，这些内容已基本掌握，现 在我们来模拟实现list。

namespace rose{ template struct _list_node { T _val; _list_node* _prev; _list_node* _next; _list_node(const T& val=T()) :_val(val) ,_prev(nullptr) , _next(nullptr) {} }; //原生指针(节点指针),已经无法完成迭代器的功能 //list::iterator ->Node* //通过两个模板参数控制 template struct _list_iterator //_list_iterator去封装Node*，重载这个类的operator*，++等运算符，去模拟像指针一样的访问行为 { //节点的指针原生行为不满足迭代器定义 //这里迭代器通过类去封装节点的指针，重载运算符来控制 typedef _list_node node; typedef _list_iterator self; node* _pnode; _list_iterator(node* pnode) :_pnode(pnode) {} //拷贝构造，operator=，析构我们不写，编译器默认生成就可以用 Ref operator*() { return _pnode->_val; } //这里本来应该是两个->，第一个是it->去调用重载的operator->返回T*的指针，第一个箭头去T*的指针去，访问对象中的成员 //但是两个箭头，程序的可读性很差，所以编译器做了特殊的识别处理，为了可读性，省略了一个箭头 Ptr operator->() { return &(_pnode->_val); } bool operator!=(const self& s)const { return _pnode != s._pnode; } bool operator==(const self& s)const { return _pnode == s._pnode; } //it++ -> it.operator(&it); self& operator++() { _pnode = _pnode->_next; return *this; } self& operator--() { _pnode = _pnode->_prev; return *this; } //it++ -> it.operator(&it,0); self operator++(int) { self tmp(*this); _pnode = _pnode->_next; return tmp; } self operator--(int) { self tmp(*this); _pnode = _pnode->_prev; return tmp; } }; //有了这样的方式，不关心容器底层结构到底是数组，链表，树形结构等等，封装隐藏了底层的细节 //让我们可以用简单统一的方式去访问修改容器，这个也就是迭代器真正的价值 template class list { typedef _list_node node; public: typedef _list_iterator iterator; typedef _list_iterator const_iterator; //只能读不能写，如何控制_list_iterator中如何控制写呢？ //typedef _list_const_iterator const_iterator; iterator begin() { return iterator(_head->_next); } const_iterator begin()const { return const_iterator(_head->_next); } iterator end() { return iterator(_head); } const_iterator end()const { return const_iterator(_head); } list() { //_head = new node(T()); _head = new node; _head->_next = _head; _head->_prev = _head; } list(const list& lt) { _head = new node; _head->_next = _head; _head->_prev = _head; for (const auto& e : lt) { push_back(e); } } //list& operator=(const list& lt) //{ // if (this != <) // { // clear(); // for (const auto& e : lt) // { // push_back(e); // } // } // return *this; //} list& operator=(list lt) { swap(_head, lt._head); return *this; } ~list() { clear(); delete _head; _head = nullptr; } void clear() { iterator it = begin(); while (it != end()) { //it=erase(it); erase(it++); } } void push_back(const T& x) { //node* newnode=new node(x); //node* tail = _head->_prev; //tail->_next = newnode; head tail newnode //newnode->_prev = tail; //newnode->_next = _head; //_head->_prev = newnode; insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } void pop_front() { erase(begin()); } void pop_back() { assert(_head->next != _head); /*node* tail = _head->_prev; node* prev = tail->_prev; prev->_next = _head; _head->_prev = prev; delete tail;*/ erase(--end()); } void insert(iterator pos,const T& x) { node* cur = pos._pnode; node* prev = cur->_prev; node* newnode = new node(x); prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; } iterator erase(iterator pos) { assert(pos._pnode); assert(pos!=end()); node* cur = pos._pnode; node* prev = cur->_prev; prev->_next = cur->_next; cur->_next->_prev = prev; delete cur; return (iterator)prev->_next; } bool empty() { return begin() == end(); } size_t size() { size_t sz = 0; iterator it = begin(); while (it != end()) { sz++; it++; } return sz; } private: node* _head; };

2.2对模拟的rose::list进行测试

void PrintList(const list& lt) { list::const_iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; it++; } cout << endl; } class Date { public: int _year = 0; int _month = 1; int _day = 1; }; void test_list1() { list lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); list::iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; it++; } cout << endl; PrintList(lt); } void test_list2() { list lt; lt.push_back(Date()); lt.push_back(Date()); lt.push_back(Date()); lt.push_back(Date()); list::iterator it = lt.begin(); while (it!=lt.end()) { cout << it->_year << " " << it->_month << " " << it->_day << " " << endl;; it++; } } void test_list3() { list lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.clear(); }

三、list与vector的对比

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不 同，其主要不同如下：

总结

例如：以上就是今天要讲的内容，本文仅仅简单介绍了list的使用和模拟实现，最后我们还将list和vector两个重要的容器进行了对比。文章主要的一部分迭代器失效需要大家多多注意一些细节就好了，今天就到这里啦！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。