当前位置:首页 » 《随便一记》 » 正文

【C++驾轻就熟】list深入了解及模拟实现

29 人参与  2024年10月16日 18:01  分类 : 《随便一记》  评论

点击全文阅读


目录

一、list的介绍及使用

二、标准库中的list类

2.1 list的常见接口说明

2.1.1 list对象的常见构造

1.无参构造函数

2.有参构造函数(构造并初始化n个val)

3.有参构造函数(使用迭代器进行初始化构造) 

4.拷贝构造函数 

2.1.2 list iterator的使用

1.begin() + end() 

2.rbegin() + rend() 

2.1.3 list对象的容量操作

1.empty()函数

2.size()函数

2.1.4 list对象的增删查改及访问

1.push_front()函数

2. pop_front()函数 

3. push_back()函数

4. pop_back()函数

5. insert()函数

6. erase()函数

7. swap()函数 

8. clear()函数 

9. front()函数 + back()函数 

 三、list的迭代器失效

四、list与vector的对比

五、list的模拟实现 

结尾


一、list的介绍及使用

list介绍文档

 list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。 list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。 list与forward_list非常相似:最主要的不同在于forward_list是单链表,只能朝前迭代,已让其更简单高效。 与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率更好。 与其他序列式容器相比,list和forward_list最大的缺陷是不支持任意位置的随机访问,比如:要访问list的第6个元素,必须从已知的位置(比如头部或者尾部)迭代到该位置,在这段位置上迭代需要线性的时间开销;list还需要一些额外的空间,以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)


二、标准库中的list类

2.1 list的常见接口说明

2.1.1 list对象的常见构造

1.无参构造函数
list();
int main(){list<int> l;return 0;}


2.有参构造函数(构造并初始化n个val)
list (size_type n, const value_type& val = value_type());
int main(){list<int> l(5,10);return 0;}


3.有参构造函数(使用迭代器进行初始化构造) 
template <class InputIterator>  list (InputIterator first, InputIterator last);
int main(){string s("I LOVE YOU");list<char> l(s.begin(), s.end());return 0;}


4.拷贝构造函数 
list (const list& x);
int main(){list<int> s(5,10);list<int> v(s);return 0;}


2.1.2 list iterator的使用

1.begin() + end() 

  iterator begin();const_iterator begin() const;获取第一个数据位置的iterator/const_iterator   iterator end();const_iterator end() const;获取最后一个数据的下一个位置的iterator/const_iterator
int main(){list<int> l;for (int i = 0; i < 10; i++){l.push_back(i);}list<int>::iterator it = l.begin();while (it != l.end()){*it+=100;cout << *it << ' ';++it;}cout << endl;return 0;}


2.rbegin() + rend() 

  reverse_iterator rbegin();const_reverse_iterator rbegin() const;获取最后一个数据位置的reverse_iterator/const_reverse_iterator   reverse_iterator rend();const_reverse_iterator rend() const;获取第一个数据前一个位置的reverse_iterator/const_reverse_iterator 
int main(){list<int> l;for (int i = 0; i < 10; i++){l.push_back(i);}list<int>::reverse_iterator it = l.rbegin();while (it != l.rend()){*it += 100;cout << *it << ' ';++it;}cout << endl;return 0;}

【注意】 :

begin与end为正向迭代器,对迭代器执行++操作,迭代器向后移动  rbegin(end)与rend(begin)为反向迭代器,对迭代器执行++操作,迭代器向前移动  
2.1.3 list对象的容量操作

1.empty()函数

bool empty() const;         判断是否为空
int main(){list<int> l;cout << l.empty() << endl;l.push_back(520);cout << l.empty() << endl;return 0;}


2.size()函数

size_type size() const;      获取数据个数
int main(){list<int> l;cout << l.size() << endl;for (int i = 0; i < 10; i++){l.push_back(i);}cout << l.size() << endl;return 0;}


2.1.4 list对象的增删查改及访问

1.push_front()函数

int main(){list<int> l;l.push_front(1);l.push_front(2);l.push_front(3);l.push_front(4);for (auto e : l){cout << e << ' ';}cout << endl;return 0;}
void push_front (const value_type& val);  头插

 


2. pop_front()函数 

void pop_front();  头删
int main(){list<int> l;l.push_front(1);l.push_front(2);l.push_front(3);l.push_front(4);for (auto e : l){cout << e << ' ';}cout << endl;l.pop_front();for (auto a : l){cout << a << ' ';}return 0;}


3. push_back()函数

void push_back (const value_type& val);   尾插
int main(){list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);for (auto e : l){cout << e << ' ';}cout << endl;return 0;}

 


 4. pop_back()函数

void pop_back();  尾删
int main(){list<int> l;l.push_back(1);l.push_back(3);l.push_back(1);l.push_back(4);for (auto e : l){cout << e << ' ';}cout << endl;l.pop_back();for (auto e : l){cout << e << ' ';}cout << endl;return 0;}


5. insert()函数

iterator insert (iterator position, const value_type& val);insert()函数能够在position之前插入val,并返回插入数据位置的 iterator void insert (iterator position, size_type n, const value_type& val);insert()函数能够在position之前插入 n 个 val             template <class InputIterator>void insert (iterator position, InputIterator first, InputIterator last);insert()函数能够在position之前插入一段迭代器区间的数据       
int main(){list<char> l;string s("Love");l.push_back('y');l.push_back('o');l.push_back('u');for (auto e : l){cout << e << ' ';}cout << endl;// insert()函数能够在position之前插入val,并返回插入数据位置的 iterator //l.insert(v.begin() + 5, 'v');这是错误的,因为再list中没有支撑迭代器的加法cout << *(l.insert(l.begin(), '#')) << endl;for (auto e : l){cout << e << ' ';}cout << endl;// insert()函数能够在position之前插入 n 个 val   list<char>::iterator it = l.begin();for (size_t i = 0; i < 1; i++){++it;}l.insert(it, 3, '@');for (auto e : l){cout << e << ' ';}cout << endl;// insert()函数能够在position之前插入一段迭代器区间的数据       l.insert(++l.begin(), s.begin(), s.end());for (auto e : l){cout << e << ' ';}cout << endl;return 0;}


6. erase()函数

iterator erase (iterator position);erase()函数能够删除在position位的的数据,并返回删除数据后面数据位置的 iteratoriterator erase (iterator first, iterator last);erase()函数能够删除在迭代器区间 [first,last) 的的数据,并返回删除数据后面数据位置的 iterator             
int main(){list<int> l;for (int i = 0; i < 10; i++){l.push_back(i);}for (auto e : l){cout << e << ' ';}cout << endl;// erase()函数能够删除在position位的的数据// 并返回删除数据后面数据位置的 iteratorcout << *(l.erase(l.begin())) << endl;for (auto e : l){cout << e << ' ';}cout << endl;// erase()函数能够删除在迭代器区间 [first,last) 的的数据// 并返回删除数据后面数据位置的 iterator        cout << *(l.erase(++l.begin(), --l.end())) << endl;for (auto e : l){cout << e << ' ';}cout << endl;return 0;}


7. swap()函数 

void swap (list& x);交换两个list的数据空间
int main(){list<int> l1(5, 20);list<int> l2(7, 5);//交换前for (auto e : l1){cout <<  "l1 :" << e << ' ';}cout << endl;for (auto e : l2){cout <<  "l2 :" << e << ' ';}cout << endl;//交换中l1.swap(l2);//交换后for (auto e : l1){cout << "l1 :" << e << ' ';}cout << endl;for (auto e : l2){cout << "l2 :" << e << ' ';}cout << endl;return 0;}


8. clear()函数 

void clear();清除list中的有效数据
int main(){list<int> l(4, 10);cout << l.size() << endl;l.clear();cout << l.size() << endl;return 0;}


9. front()函数 + back()函数 

访问list中的第一个数据  reference front();const_reference front() const;访问list中的最后一个数据   reference back();const_reference back() const;
int main(){list<int> l;for (int i = 0; i < 5; i++){l.push_back(i);}cout << "front:" << l.front() << endl;cout << "back:" << l.back() << endl;return 0;}


 三、list的迭代器失效

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

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

四、list与vector的对比

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

五、list的模拟实现 

#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>#include<assert.h>using namespace std;namespace lxp{template<class T>struct list_node{list_node<T>* _prev;list_node<T>* _next;T _val;list_node(const T& val = T()):_prev(nullptr), _next(nullptr), _val(val){}};// typedef __list_iterator<T, T&, T*> iterator;// typedef __list_iterator<T, const T&, const T*> const_iterator;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 = _node;_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int){self tmp = _node;_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{public:typedef list_node<T> Node;typedef _list_iterator<T, T&, T*> iterator;typedef _list_iterator<T, const T&, const T*> const_iterator;iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}list(){_head = new Node;_head->_prev = _head;_head->_next = _head;}list(const list<T>& lt){_head = new Node;_head->_prev = _head;_head->_next = _head;for (auto& e : lt){push_back(e);}}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T>& operator=(list<T> lt){swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}void push_back(const T& x){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* newnode = new Node(x);Node* cur = pos._node;Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;++_size;return newnode;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* pre = cur->_prev;Node* next = cur->_next;pre->_next = cur->_next;next->_prev = pre;delete cur;_size--;return next;}size_t size(){return _size;}private:Node* _head;size_t _size;};}

结尾

如果有什么建议和疑问,或是有什么错误,希望大家可以在评论区提一下。
希望大家以后也能和我一起进步!!
如果这篇文章对你有用的话,请大家给一个三连支持一下!!

谢谢大家收看??


点击全文阅读


本文链接:http://zhangshiyu.com/post/172766.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1