文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

怎么用C++模拟实现STL容器

2023-07-04 18:10

关注

这篇文章主要介绍了怎么用C++模拟实现STL容器的相关知识,内容详细易懂,操作简单快捷,具有一定借鉴价值,相信大家阅读完这篇怎么用C++模拟实现STL容器文章都会有所收获,下面我们一起来看看吧。

一、list的介绍

列表是一种顺序容器,它允许在序列中的任何位置执行常量时间插入和删除操作,并允许在两个方向上进行迭代。它的底层是一个带头双向循环链表。

二、list的排序

list不能用算法库的sort进行排序。算法库中的sort的底层是一个快排,需满足三数取中,需要传入随机访问迭代器,所以list并不适用。

当然list中提供了一个自己的sort,它的底层是一个归并排序。但是这个sort比vector使用算法库的sort还慢,甚至比list的数据先push_back到vector到再用算法库的sort还要慢。

怎么用C++模拟实现STL容器

三、迭代器

1、list的迭代器失效问题

insert,迭代器不失效

earse失效

2、迭代器的功能分类

单向迭代器:只能++,不能--。例如单链表,哈希表;

双向迭代器:既能++也能--。例如双向链表;

随机访问迭代器:能++--,也能+和-。例如vector和string。

迭代器是内嵌类型(内部类或定义在类里)

3、list迭代器的模拟实现

普通迭代器

迭代器的实现需要支持解引用(为了取数据),支持++--。

博主模拟实现string和vector时,直接将原生指针typedef成迭代器,是因为数组的结构正好满足迭代器的行为(注:string和vector可以用原生指针实现,但是vs中采用自定义类型封装的方式实现),但是list中的节点地址是不连续的,不能使用原生指针,需要使用类进行封装+运算符重载实现。

//用类封装迭代器template <class T>struct __list_iterator{    typedef list_node<T> node;    //用节点的指针进行构造    __list_iterator(node* p)        :_pnode(p)    {}    //迭代器运算符的重载    T& operator*()    {        return _pnode->_data;    }    __list_iterator<T>& operator++()//返回值不要写成node* operator++(),因为迭代器++肯定返回迭代器啊,你返回节点指针类型不对    {         //return _pnode->_next;        _pnode=_pnode->_next;        return *this;//返回的是迭代器    }    bool operator!=(const __list_iterator<T>& it)    {        return _pnode != it._pnode;    }public:    node* _pnode;//封装一个节点的指针};

怎么用C++模拟实现STL容器

const迭代器

const迭代器的错误写法:

typedef __list_iterator<T> iterator;const list<T>::iterator it=lt.begin();

因为typedef后,const修饰的是迭代器it,只能调用operator*(),调不了operator++()。(重载operator++()为const operator++()也不行,因为const版本++还是改变不了)

正确写法:想实现const迭代器,不能在同一个类里面动脑筋,需要再写一个const版本迭代器的类。

//用类封装const迭代器template <class T>struct __list_const_iterator{    typedef list_node<T> node;    //用节点的指针进行构造    __list_const_iterator(node* p)        :_pnode(p)    {}    //迭代器运算符的重载    const T& operator*()const    {        return _pnode->_data;    }    __list_const_iterator<T>& operator++()//返回值不要写成node*,因为迭代器++肯定返回迭代器啊,你返回节点指针类型不对    {        //return _pnode->_next;//返回类型错误的        _pnode = _pnode->_next;        return *this;//返回的是迭代器    }    __list_const_iterator<T>& operator--()    {        _pnode = _pnode->_prev;        return *this;    }    bool operator!=(const __list_const_iterator<T>& it)const    {        return _pnode != it._pnode;    }public:    node* _pnode;//封装一个节点的指针}; typedef __list_const_iterator<T> const_iterator;

当然,这样写__list_iterator和__list_const_iterator这两个类会出现代码重复。STL库中是通过类模板多给一个参数来实现,这样,同一份类模板就可以生成两种不同的类型的迭代器(以下为仿STL库的模拟实现): 

//用类封装普通/const迭代器template <class T,class Ref>struct __list_iterator{    typedef list_node<T> node;    typedef __list_iterator<T,Ref> Self;    //用节点的指针进行构造    __list_iterator(node* p)        :_pnode(p)    {}    //迭代器运算符的重载    Ref operator*()    {        return _pnode->_data;    }    Self& operator++()//返回值不要写成node*,因为迭代器++肯定返回迭代器啊,你返回节点指针类型不对    {         //return _pnode->_next;//返回类型错误的        _pnode=_pnode->_next;        return *this;//返回的是迭代器    }    Self& operator--()    {        _pnode = _pnode->_prev;        return *this;    }    bool operator!=(const Self& it)    {        return _pnode != it._pnode;    }public:    node* _pnode;//封装一个节点的指针}; typedef __list_iterator<T, T&> iterator;typedef __list_iterator<T, const T&> const_iterator;

4、迭代器价值

封装底层实现,不暴露底层实现的细节;

多种容器提供统一的访问方式,降低使用成本;

C语言没有运算符重载和引用等语法,是实现不了迭代器的。

5、迭代器operator->的重载

迭代器的用法就是模拟指针的行为,如果现在有一个指向结构的指针,那么就需要用到->来解引用。

/insert(end(), x);}void pop_back(){erase(--end());}void push_front(const T& x)//头插{insert(begin(), x);}void pop_front(){erase(begin());}iterator insert(iterator pos, const T& x){node* newNode = new node(x);node* prev = pos._pnode->_prev;node* cur = pos._pnode;newNode->_prev = prev;newNode->_next = cur;prev->_next = newNode;cur->_prev = newNode;//return iterator(newNode);pos._pnode = newNode;++_size;return pos;}iterator erase(iterator pos){assert(!empty());node* prev = pos._pnode->_prev;node* next = pos._pnode->_next;prev->_next = next;next->_prev = prev;delete pos._pnode;--_size;//return iterator(next);pos._pnode = next;return pos;}//链表小接口bool empty()const{return _head->_next == _head;}void clear(){iterator it = begin();while (it != end()){it = erase(it);//erase返回删除元素的下一个}}size_t size()const{return _size;}//普通begin(),end()迭代器iterator begin(){//return iterator(_head->_next);return __list_iterator<T, T&,T*>(_head->_next);}iterator end(){return __list_iterator<T, T&,T*>(_head);}//const begin(),end()迭代器const_iterator begin()const{//return const_iterator(_head->_next);return __list_iterator<T, const T&,const T*>(_head->_next);}const_iterator end()const{return __list_iterator<T, const T&,const T*>(_head);}private:node* _head;//哨兵位size_t _size;//用于统计节点个数,空间换时间//不加这个私有变量,统计节点个数时间O(N),有这个私有变量,时间O(1),但是每个节点的体积变大};  //测试函数struct Pos{int _row;int _col; Pos(int row = 0, int col = 0):_row(row), _col(col){}};void test(){list<Pos> i;i.push_back(Pos(1, 2));i.push_back(Pos(2, 5));i.push_back(Pos(4, 3));list<Pos>::iterator it = i.begin();while (it != i.end()){cout << (&( * it))->_row;//*it取数据,再取地址、解引用得到_row,多此一举cout << it->_row;//同第三种写法,编译器为了可读性,省略了一个->cout << it.operator->()->_row;//it.operator->()是显示调用,->_row是解引用得到_rowit++;}}void test1(){list<std::vector<int>> i;std::vector<int> v1(1, 2);std::vector<int> v2(2, 4);std::vector<int> v3(3, 5);i.push_back(v1);i.push_back(v2);i.push_back(v3);list<std::vector<int>> m(i);i = m;cout << m.size();}}

关于“怎么用C++模拟实现STL容器”这篇文章的内容就介绍到这里,感谢各位的阅读!相信大家对“怎么用C++模拟实现STL容器”知识都有一定的了解,大家如果还想学习更多知识,欢迎关注编程网行业资讯频道。

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯