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

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

一、list的介绍

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

二、list的排序

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

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

三、迭代器

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;//封装一个节点的指针};

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容器”知识都有一定的了解，大家如果还想学习更多知识，欢迎关注编程网其他教程频道。