您的位置:首页 > 教育 > 锐评 > 文化建设五大工程_长春企业自助建站系统_网络营销工程师_风云榜百度

文化建设五大工程_长春企业自助建站系统_网络营销工程师_风云榜百度

2024/10/5 22:28:22 来源:https://blog.csdn.net/xqhoj/article/details/142358177  浏览:    关键词:文化建设五大工程_长春企业自助建站系统_网络营销工程师_风云榜百度
文化建设五大工程_长春企业自助建站系统_网络营销工程师_风云榜百度

        欢迎来到繁星的CSDN。本期内容主要包括,list的介绍、使用以及与vector的优缺点。        

一、什么是list

        在先前的C语言学习中,我们接触到了顺序表和链表,而在C++中,这正好对应了vector(动态增长顺序表)和list(链表)。所以本期的内容实质上仍然是与链表相关的封装、重载函数等。

           list和之前说的string、vector一样,属于container(容器),作为STL库里的常客,list的出场为我们的链表提供的简易的使用方法。但是很可惜的是,我们的二叉树等链表的变形却不能直接使用。原因是list实质上是带头双向链表。(HEAD节点和其余节点结构一致,但是在list内为空时,该节点不销毁,只是为空)

二、list的接口

        list的接口比之list而言更有序,但数量仍然十分众多。

        具体查看网址如下:

        cplusplus.com/reference/list/list/

      构造constructor

explicit list ();//默认构造explicit list (size_type n);//传值构造
list (size_type n, const value_type& val);//传值构造template <class InputIterator>  list (InputIterator first, InputIterator last);//区间构造list (const list& x);//拷贝构造

   文档中还有其他重载函数,以及以上展示的构造函数中,我已将有关空间配置器的内容省去(因为大部分情况下我们只需要使用STL原生的配置器就可以了)。

   实际上我们可以发现,list的构造函数和vector的构造函数差别不大。

      销毁destructor

~list();

    和我们熟悉的销毁方式没有什么区别。实际上就是将链表中的动态申请部分释放,并将相关成员变量置空。而且由于这是STL库内的部分而非自定义类型需要我们自己实现,当程序结束的时候,将会自动调用销毁函数,所以无需担心。

       赋值重载operator=

list& operator= (const list& x);

     

   经过实践检验得知,当我们使用=赋值另一个list的时候,两者的地址不同,所以这是深拷贝,无需担心先前的list销毁导致复制出来的list同时销毁。 

      迭代器iterator

        list的迭代器我们可以暂时理解为指针。

#include<iostream>
#include<list>
using namespace std;int main() {int array[] = { 1,2,3,4,0,5,6,7,8,9 };int n = sizeof(array) / sizeof(int);list<int> mylist(array, array + n);auto it = mylist.begin();*it = 0;for (int a : mylist) {cout << a << endl;}return 0;
}

        (这里偷偷使用了auto来偷懒,实际写可以写为list::iterator)

        之前提过,迭代器的出现就是为了封装,减少记忆成本。

        所以这里的it仍然可以实现,++,--,*这几个方式。

        ++就是到下一个节点,--就是返回上一个节点,*就是解引用。

        与迭代器相关的接口如下:
        

   begin(),end()                          //正向迭代器

   rbegin(),rend()                       //反向迭代器

   cbegin(),cend()                      //const正向迭代器

   crbegin(),crend()                   //const反向迭代器

        但是有一点比较麻烦,list不再支持[ ],也就是随机访问。

        原因在于,底层的链表实现随机访问的代价太大,即使list的底层是带头双向链表,由于物理储存空间的不连续性,最坏情况也可以达到O(n/2)。

      容器大小capacity

    empty();

    size();

    max_size();

        相比vector,list的capacity变成了max_size,这是因为链表某一结点的空间都是单独申请,所以不存在可容纳空间这一概念,取代capacity的是max_size,代表可供使用的空间大小,这取决于系统,而非自己申请。

      访问方式access

   front();

   back();

        front与back分别是整个list的头与尾,可以通过这两个直接得到。

      成员函数member function

void push_front (const value_type& val);
void push_back (const value_type& val);
void pop_front();
void pop_back();
//对单个元素进行操作iterator erase (const_iterator position);//删除单个元素
iterator erase (const_iterator first, const_iterator last);//删除区间内的元素iterator insert (const_iterator position, const value_type& val);
iterator insert (const_iterator position, size_type n, const value_type& val);
//在某一位置插入一个或多个同一元素
template <class InputIterator>
iterator insert (const_iterator position, InputIterator first, InputIterator last);
//在某一位置插入另一容器的部分元素

       对list的相关函数操作,实际上和vector差别不大,当然C++11还支持了emplace_back,emplace_front,emplace,这分别对应push_back,push_front,insert。不过对于左值引用而言,效率一样,对于右值引用(这里未书写,仅仅是将参数类型变成右值),emplace的效率更高。

        当然list的相关函数还有很多,感兴趣的可以看:

        cplusplus.com/reference/list/list/

三、list和vector的优劣与不可替代性

        说起list,就不能不提到与vector的优劣势,以及是否可以被替代。

        list和vector的优劣取决于他们的储存方式。vector是由一段连续的物理空间储存,而list是不必使用连续空间储存,却不支持随机访问。

vectorlist
底层结构动态顺序表、连续物理空间带头双向链表
随机访问支持不支持
插入与删除尾端效率高,其余位置需要挪动元素,效率不高任意位置效率均高,O(1)
空间利用率空间利用率高、缓存利用率高空间利用率低、缓存利用率低
迭代器原生指针对原生指针进行封装
迭代器失效插入时如发生扩容,迭代器失效,删除时当前迭代器失效插入不会导致失效,删除时仅当前迭代器失效
使用场景需要高效储存、需要随机访问,不需要大量插入删除操作大量插入删除操作

四、list的模拟实现

namespace show
{// List的节点类template<class T>struct ListNode{T _val;ListNode<T>* _pPre;ListNode<T>* _pNext;ListNode(const T& val = T()):_val(val),_pNext(nullptr),_pNext(nullptr){};};//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){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}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;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}};//list类template<class T>class list{typedef list_node<T> Node;public: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;}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}list(initializer_list<T> il){empty_init();for (auto& e : il){push_back(e);}}list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}list<T>& operator=(list<T> lt){swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;}void clear(){auto it = begin();while (it != end()){it = erase(it);}}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;prev->_next = newnode;++_size;return newnode;}void pop_back(){erase(--end());}void pop_front(){erase(begin());}iterator erase(iterator pos){assert(pos != end());Node* prev = pos._node->_prev;Node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;--_size;return next;}size_t size() const{return _size;}bool empty() const{return _size == 0;}private:Node* _head;size_t _size;};
};

        

        本篇内容到此结束,谢谢大家的观看!

        觉得写的还不错的可以点点关注,收藏和赞,一键三连。

        我们下期再见~

        往期栏目:

        C++学习指南(一)——C++入门基础_c++ 学习指南-CSDN博客

        C++学习指南(二)——类和对象-CSDN博客

        C++学习指南(三)——模板_模板类-CSDN博客

        C++学习指南(四)------string-CSDN博客

        C++学习指南(五)——vector_erwei vector bianliangchushihua-CSDN博客

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com