【C++】vector模拟实现过程中值得注意的点

这篇具有很好参考价值的文章主要介绍了【C++】vector模拟实现过程中值得注意的点。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【C++】vector模拟实现过程中值得注意的点,C++,c++,开发语言

👀樊梓慕:个人主页

 🎥个人专栏:《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C++》《Linux》《算法》

🌝每一个不曾起舞的日子,都是对生命的辜负


前言

本篇文章旨在记录博主在模拟实现vector容器中遇到的一些问题,都是一些需要注意的细节问题,希望与大家共勉。


欢迎大家📂收藏📂以便未来做题时可以快速找到思路,巧妙的方法可以事半功倍。

=========================================================================文章来源地址https://www.toymoban.com/news/detail-796180.html

GITEE相关代码:🌟fanfei_c的仓库🌟

=========================================================================


1.迭代器失效问题

迭代器失效可以大致总结为:

        之前我们说迭代器的底层可以理解为指针,那么迭代器失效其实就是『 底层指针的指向发生了改变,而迭代器没有』,这就会导致使用迭代器时报错或者出现错误数据。

并且迭代器失效一般具有下面的特点:

  • 一般发生在需要扩容时,比如resize、reserve、insert、assign、push_back;
  • 解决方案一般为将迭代器重新赋值,所以我们查看STL-vector的底层源码会发现insert等函数实现时会有返回值,这个返回值就是让我们在使用时,将迭代器重新赋值用的(博主也模拟实现了下供大家参考);

问题剖析(以reserve和insert举例说明)

void reserve(size_t n)
{
    if (n > capacity())
    {
        size_t old = size();
        T* tmp = new T[n];
        if (_start)
        {
            //memcpy(tmp, _start, old * sizeof(T));
            //delete[] _start;

            for (size_t i = 0; i < old; i++)//解决方案
            {
                tmp[i] = _start[i];
            }
            delete[] _start;
        }
        _start = tmp;
        _finish = _start + old;
        _endOfStorage = _start + n;
    }
}

        可以看到我注释掉的代码,在最开始可能你会利用memcpy来简化代码,一步到位非常方便,但这就引发了一些意想不到的后果:『 迭代器失效』。 

假设vector中存储的为string类:

        用memcpy会导致:如果调用了reserve函数,执行到memcpy,memcpy实际为一种『 浅拷贝行为』

【C++】vector模拟实现过程中值得注意的点,C++,c++,开发语言


『 delete[]会调用析构然后释放空间』

        执行过memcpy后,如果执行delete[] _start就会调用析构函数,然后string的析构导致_ str成为野指针, 进而导致vector的迭代器_start失效。

        同样这个问题到insert的模拟实现处也存在,因为利用了memmove,比如:

iterator insert(iterator pos, const T& x)
{
    assert(pos >= _start && pos <= _finish);

    if (_finish == _endOfStorage)
    {
        size_t len = pos - _start;//保存长度
        size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity();
        reserve(newCapacity);
        pos = _start + len;//扩容后更新pos的位置,否则pos依旧指向被释放的旧空间
    }
    //memmove(pos + 1, pos, (_finish - pos) * sizeof(T));

    iterator end = _finish - 1;//解决方案
    while (end > pos)
    {
        *(end + 1) = *end;
        --end;
    }
    *pos = x;
    ++_finish;
    return pos;
}

解决memcpy、memmove浅拷贝行为导致迭代器失效的问题:

  • 如代码所示,利用重载的赋值操作符就可以避免这一问题,因为赋值是一种『 深拷贝行为』。

以上是模拟实现过程中解决的迭代器时效问题。

那么在应用中,我们可以利用erase、insert的返回值将迭代器重新赋值,防止迭代器失效。

it = s.begin();
while (it != s.end())
{
    it = s.erase(it);
    // 按照下面方式写,运行时程序会崩溃,因为erase(it)之后
    // it位置的迭代器就失效了
    // s.erase(it);
    ++it;
}

另一种解决方案是可以利用『 引用计数』的方式,这里我就不多赘述了,不了解的小伙伴可以自行百度。


2.构造函数重载导致歧义(迭代器区间构造)

迭代器区间构造是一种十分精妙的构造方式,它可以将任意类型(只要支持迭代器)初始化给vector,参数只需要传递两个迭代器即可,比如:

template <class InputIterator>//泛型迭代器
vector(InputIterator first, InputIterator last)
{
    while (first != last)
    {
        push_back(*first);
        ++first;
    }
}
void test_vector()
{
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);
    //同类型构造
    vector<int> v2(v1.begin(), v1.end());
    for (auto e : v2)
    {
        cout << e << " ";
    }
    cout << endl;

    list<int> lt;
    lt.push_back(10);
    lt.push_back(20);
    lt.push_back(30);
    lt.push_back(40);
    //不同类型构造
    vector<int> v3(lt.begin(), lt.end());
    for (auto e : v3)
    {
        cout << e << " ";
    }
    cout << endl;
    //甚至是数组
    int a[] = { 100, 200, 300 };//底层物理空间连续,天然的迭代器-指针
    vector<int> v4(a, a+3);     //指向连续物理地址空间的指针就是天然的迭代器,符合迭代器要求
    for (auto e : v4)
    {
        cout << e << " ";
    }
    cout << endl;
}

但vector中有某类构造函数是这样的:

vector(size_t n, const T& val = T())//将容器初始化为n个val
{
    resize(n, val);
}

如果你写了这样的代码:

void test_vector()
{
    vector<string> v1(5, "1111");//ok
    for (auto e : v1)
    {
        cout << e << " ";
    }
    cout << endl;

    vector<int> v2(5, 1);//err
    for (auto e : v2)
    {
        cout << e << " ";
    }
    cout << endl;
}

这就会引发报错:

【C++】vector模拟实现过程中值得注意的点,C++,c++,开发语言


问题剖析 

原因就是你的程序可能没有按你的本意走,你的本意是想『 将v2初始化为5个1』。

可是编译器会将5和1识别为迭代器,因为5和1的类型相同,不需要发生类型转换。

为什么不会识别为(size_t n,const T& val = T())呢,很明显编译器也不想发生类型转换,size_t为unsigned char,另一个参数为const T&(这里为int),需要发生类型转转换才可以匹配。

所以为了解决这一问题,我们需要再额外重载一个:

vector(size_t n, const T& val = T())//将容器初始化为n个val
{
    resize(n, val);
}
vector(int n, const T& val = T())//为了解决两个参数都为int,会自动匹配迭代器区间初始化函数导致报错
{
    resize(n, val);
}

虽然看起来好像不太高级,但是实际上STL也是这么做的。 

【C++】vector模拟实现过程中值得注意的点,C++,c++,开发语言


3.vector模拟实现源码

template<class T>
class vector
{
public:
    //Vector的迭代器是一个原生指针
    typedef T* iterator;
    typedef const T* const_iterator;
    iterator begin()
    {
        return _start;
    }
    iterator end()
    {
        return _finish;
    }
    const_iterator begin() const
    {
        return _start;
    }
    const_iterator end() const
    {
        return _finish;
    }

    // construct and destroy
    vector()
    {}

    vector(const vector<T>& v)
    {
        //传统写法
        /*_start = new T(v.capacity());
        memcpy(_start, v._start, v.size() * sizeof(T));
        _finish = _start + v.size();
        _endOfStorage = _start + v.capacity();*/

        //现代写法
        reserve(v.capacity());
        for (const auto& e : v)
        {
            push_back(e);
        }
    }

    //迭代器区间初始化    “泛型”
    //可以穿任意类型的迭代器初始化
    template <class InputIterator>
    vector(InputIterator first, InputIterator last)
    {
        while (first != last)
        {
            push_back(*first);
            ++first;
        }
    }

    vector(size_t n, const T& val = T())//如果传参两个int,会导致不匹配该函数而匹配迭代器区间初始化函数
    {
        resize(n, val);
    }

    vector(int n, const T& val = T())//为了解决两个参数都为int,会自动匹配迭代器区间初始化函数导致报错
    {
        resize(n, val);
    }

    vector<T>& operator= (vector<T> v)
    {
        swap(v);
        return *this;
    }
    ~vector()
    {
        if (_start)
        {
            delete[] _start;
            _start = _finish = _endOfStorage = nullptr;
        }
    }

    // capacity
    size_t size() const
    {
        return _finish - _start;
    }
    size_t capacity() const
    {
        return _endOfStorage - _start;
    }
    void reserve(size_t n)
    {
        if (n > capacity())
        {
            size_t old = size();
            T* tmp = new T[n];
            if (_start)
            {
                //memcpy(tmp, _start, old * sizeof(T));//用memcpy会导致模板为string类时,如果vector需要扩容,此时memcpy实际为一种“浅拷贝行为”,string成员_str会因为delete[] _start成为野指针
                //delete[] _start;//delete[]会调用析构然后释放空间
                //同样这个问题到insert的模拟实现处也存在,因为利用了memmove
                for (size_t i = 0; i < old; i++)//解决方案   另一种解决方案是可以利用“引用计数”
                {
                    tmp[i] = _start[i];
                }
                delete[] _start;
            }
            _start = tmp;
            _finish = _start + old;
            _endOfStorage = _start + n;
        }
    }
    void resize(size_t n, const T& val = T())
    {
        if (n > size())
        {
            if (n > capacity())
            {
                reserve(n);
                while (_finish < _start + n)
                {
                    *_finish = val;
                    ++_finish;
                }
            }
        }
        else
            _finish = _start + n;
    }

    ///access///
    T& operator[](size_t pos)
    {
        return _start + pos;
    }
    const T& operator[](size_t pos)const
    {
        return _start + pos;
    }

    ///modify/
    void push_back(const T& x)
    {
        //1.判断容量
        if (_finish == _endOfStorage)
        {
            reserve(capacity() == 0 ? 4 : 2 * capacity());
        }
        //2.尾插
        *_finish = x;
        ++_finish;
    }
    void pop_back()
    {
        assert(size() > 0);
        --_finish;
    }
    void swap(vector<T>& v)
    {
        std::swap(_start, v._start);
        std::swap(_finish, v._finish);
        std::swap(_endOfStorage, v._endOfStorage);
    }
    iterator insert(iterator pos, const T& x)
    {
        assert(pos >= _start && pos <= _finish);

        if (_finish == _endOfStorage)
        {
            size_t len = pos - _start;//保存长度
            size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity();
            reserve(newCapacity);
            pos = _start + len;//扩容后更新pos的位置,否则pos依旧指向被释放的旧空间
        }
        //memmove(pos + 1, pos, (_finish - pos) * sizeof(T));//memmove是一种浅拷贝行为,可能会造成模板为string类时,野指针的问题

        iterator end = _finish - 1;
        while (end > pos)
        {
            *(end + 1) = *end;
            --end;
        }
        *pos = x;
        ++_finish;
        return pos;
    }

    iterator erase(iterator pos)//未测试
    {
        assert(size() > 0);
        assert(pos >= _start && pos < _finish);
        //memmove(pos , pos+1, (_finish - pos) * sizeof(T));//memmove是一种浅拷贝行为,可能会造成模板为string类时,野指针的问题

        iterator it = pos + 1;
        while (it < _finish)
        {
            *(it - 1) = *it;
            ++it;
        }
        --_finish;
        return pos;
    }
private:
    iterator _start = nullptr; // 指向数据块的开始
    iterator _finish = nullptr; // 指向有效数据的尾
    iterator _endOfStorage = nullptr; // 指向存储容量的尾
};

以上就是本篇文章的全部内容。

模拟实现的意义就是『 让我们更好的使用』,像迭代器失效、构造函数重载-迭代器区间构造导致歧义等问题,只有我们模拟实现过,才能更深切得体会到为什么STL库的设计者要这么写,这么写的意义是什么。


=========================================================================

如果你对该系列文章有兴趣的话,欢迎持续关注博主动态,博主会持续输出优质内容

🍎博主很需要大家的支持,你的支持是我创作的不竭动力🍎

🌟~ 点赞收藏+关注 ~🌟

=========================================================================

到了这里,关于【C++】vector模拟实现过程中值得注意的点的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C++】vector模拟实现

    🚀 作者简介:一名在后端领域学习,并渴望能够学有所成的追梦人。 🚁 个人主页:不 良 🔥 系列专栏:🛸C++  🛹Linux 📕 学习格言:博观而约取,厚积而薄发 🌹 欢迎进来的小伙伴,如果小伙伴们在学习的过程中,发现有需要纠正的地方,烦请指正,希望能够与诸君一同

    2024年02月13日
    浏览(43)
  • C++模拟实现vector

    目录 1.代码实现 2.注意事项 1.成员变量 2. 不能使用memcpy函数拷贝数据 1.用string类型测试时,要考虑到vs可能把数据存储在数组buffer里面 3.insert函数中指针的失效性 1.加引用,那么就不能传常量,比如v.begin() + 3 2.加引用,就只能传变量了  4.erase成员函数的指针的失效性 这边以

    2024年02月17日
    浏览(43)
  • [C++]:11.模拟实现vector

    1.vector.h vector.h中其实包含了许多的头文件,我们在cpp中包含文件的时候头文件中还会去展开这四个头文件关于vector类主要在这个stl_vector.h中。 2.stl_vector.h 1.构造: ps:在当前的学习阶段看源码不要一行一行去看因为水平不足所以非常多基本上是看不懂的所以不要去一行一行去

    2024年01月16日
    浏览(43)
  • STL 关于vector的细节,vector模拟实现【C++】

    _start指向容器的头,_finish指向容器当中 有效数据 的下一个位置,_endofstorage指向整个容器的尾 先开辟一块与该容器大小相同的空间,然后将该容器当中的数据一个个拷贝过来即可,最后更新_finish和_endofstorage的值即可。 深拷贝版本一: 注意: 不能使用memcpy函数 , 如果vec

    2024年02月15日
    浏览(46)
  • C++——vector类及其模拟实现

    前言:前边我们进行的string类的方法及其模拟实现的讲解。这篇文章将继续进行C++的另一个常用类——vector。 vector和string一样, 隶属于C++中STL标准模板库中的一个自定义数据类型 ,实际上就是 线性表 。 两者之间有着很多相似,甚至相同的方法 。 但是它们也有着很大的不

    2024年04月13日
    浏览(42)
  • 【C++ STL】vector模拟实现

    2023年05月17日
    浏览(52)
  • 【C++】vector模拟实现及其应用

    vector是表示可变大小数组的序列容器。 就像数组一样,vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问,和数组一样高效。但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自动处理。 本质讲,vector使用动态分

    2023年04月25日
    浏览(47)
  • C++ STL vector 模拟实现

    ✅1主页:我的代码爱吃辣 📃2知识讲解:C++之STL 🔥3创作者:我的代码爱吃辣 ☂️4开发环境:Visual Studio 2022 💬5前言:上次我们已经数字会用了vector,这次我们对其底层更深一步挖掘,其中重点是,Vector中一些深浅拷贝问题。 目录 一.Vector模拟实现的整体框架 二. Vector的构

    2024年02月13日
    浏览(35)
  • C++中的vector类模拟实现

    目录 vector模拟实现 vector类设计 vector类构造函数 vector类根据个数构造函数 vector类根据迭代器区间构造函数 vector类拷贝构造函数 vector类赋值运算符重载函数 vector类析构函数 vector类获取有效数据个数函数 vector类获取容量大小函数 vector类begin()函数 vector类end()函数 vector类reser

    2024年04月13日
    浏览(38)
  • C++:vector使用以及模拟实现

    和我们原来讲的string不同, vector并不是类,是一个类模板,加类型实例化以后才是类。 vector是表示 可变大小数组 的序列容器。 像数组一样 ,vector也采用的连续存储空间来存储元素,但是容量可以动态改变。 和其它容器相比,vector访问元素、尾插、尾删较高效,但不在尾部

    2024年02月11日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包