C++_vector类

🕗 发布于 2024-09-25 23:13 c++ 开发语言 数据结构

欢迎来到本期节目- - -

vector类

本期直接先上代码，然后以代码为例介绍需要注意的问题.

模拟实现：

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;

namespace my_room
{

    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 cbegin()const
        {
            return _start;
        }
        const_iterator cend() const
        {
            return _finish;
        }
//---------------------------------------------------------------------------------------------
//构造和析构


//无参默认构造
        vector()
        {
        //由于给了缺省值，所以可以给空
        }


//带参构造
        vector(size_t n, const T& value = T())
        {
            reserve(n);
            while (n--)
            {
                push_back(value);
            }
        }


//迭代器区间构造
        template<class InputIterator>
        vector(InputIterator first, InputIterator last)
        {
            size_t size = last - first;
            reserve(size);//提前开好空间，减少扩容次数
            while (first != last)
            {
                push_back(*first);
                first++;
            }
        }


//拷贝构造
        vector(const vector<T>& v)
        {
            vector<T> tmp(v.cbegin(), v.cend());//直接复用
            swap(tmp);
        }

//赋值重载拷贝
        vector<T>& operator=(vector<T> v)
        {
            swap(v);
            return *this;
        }

         ~vector()
         {
             delete[] _start;//为空也不影响
             _start = _finish = _endOfStorage = nullptr;
         }

//----------------------------------------------------------------------------------------------
//核心函数

            void reserve(size_t n)
            {
                if (n > capacity())
                {
                    size_t old_size = size();
                    T* tmp = new T[n];
                    for (size_t i = 0; i < old_size; i++)
                    {
                        tmp[i] = _start[i];
                    }
                    delete[] _start;
                    _start = tmp;
                    _finish = _start + old_size;
                    _endOfStorage = _start + n;
                }
            }

            void resize(size_t n, const T& value = T())
            {
                reserve(n);
                if (n <= size())
                {
                    _finish = _start + n;
                }
                else
                {
                    while (_finish != _start + n)
                    {
                        *(_finish++) = value;
                    }
                }
            }


            iterator insert(iterator pos, const T& x)
            {
                assert(pos <= end());

                size_t old_posi = pos - begin();
                if (_finish == _endOfStorage)
                {
                    size_t n = capacity() == 0 ? 4 : capacity() * 2;
                    reserve(n);
                }
                iterator tail = end();
                pos = begin() + old_posi;
                while (tail > pos)
                {
                    *tail = *(tail - 1);
                    tail--;
                }

                *pos = x;
                _finish++;
                return pos;
            }

            iterator erase(iterator pos)
            {
                assert(pos < end());
                iterator begin = pos+1;
                while (begin != _finish)
                {
                    *(begin-1) = *begin;
                    begin++;
                }
                _finish--;
                return pos;
            }


//----------------------------------------------------------------------------------------------
//简单函数
size_t size() const
            {
                return _finish - _start;
            }

            size_t capacity() const
            {
                return _endOfStorage - _start;
            }

            bool empty()const
            {
                return _start == _finish;
            }

            T& operator[](size_t pos)
            {
                assert(pos < size());
                return _start[pos];
            }
            const T& operator[](size_t pos)const
            {
                assert(pos < size());
                return _start[pos];
            }
            void push_back(const T& x)
            {
                insert(end(), x);
            }

            void pop_back()
            {
                erase(end() - 1);
            }

            void swap(vector<T>& v)
            {
                std::swap(_start, v._start);
                std::swap(_finish, v._finish);
                std::swap(_endOfStorage, v._endOfStorage);
            }


    private:

        iterator _start = nullptr; // 指向数据块的开始

        iterator _finish = nullptr; // 指向有效数据的尾

        iterator _endOfStorage = nullptr; // 指向存储容量的尾

    };
}

核心函数

reserve

首先我们看看reserve函数
当我们在实现vector时，我们都知道，实现异地扩容都要经历这个流程：

注意

在这其中，拷贝数据就需要注意，在以往的顺序表中，我们可能会用memcpy来拷贝数据，当然在内置类型的情况下，memcpy不仅不会出错，而且比赋值拷贝高效；

但是这里是类模板，数据类型T可以是自定义类型,就有可能需要深拷贝，而memcpy本质上是浅拷贝，不满足需求，所以使用赋值重载拷贝完成自定义类型的拷贝.

除此之外，还需要注意的是更新属性问题，

_finish = _start+size();//size()返回的是 (_finish - _start)的值

此时_finish指向旧空间，_start指向新空间，返回的值根本不是有效数据的个数；

所以需要在扩容之前记录一个old_size记录数据个数，使_finish指向有效数据的末尾.

 void reserve(size_t n)
 {
     if (n > capacity())
     {
         size_t old_size = size();//记录old_size是为了不影响有效数据末尾的正确计算
         T* tmp = new T[n];
         for (size_t i = 0; i < old_size; i++)
         {
             tmp[i] = _start[i];//使用赋值拷贝是为了满足有深拷贝的自定义类型对象
         }
         delete[] _start;
         _start = tmp;
         _finish = _start + old_size;
         _endOfStorage = _start + n;
     }
 }

resize

接下来瞧瞧resize
resize只需要注意，该函数会改变有效数据的个数以及有可能会扩容.

void resize(size_t n, const T& value = T())
{
    reserve(n);//管他容量够不够，直接让reserve去判断.
    if (n <= size())
    {
        _finish = _start + n;//直接删除数据
    }
    else
    {
        while (_finish != _start + n)
        {
            *(_finish++) = value;//添加数据
        }
    }
}

insert

接下来瞅瞅insert
在实现insert函数时，核心逻辑就是移动数据.

iterator insert(iterator pos, const T& x)
{
    assert(pos <= end());//注意可以尾插，所以取等

    size_t old_posi = pos - begin();//由于可能需要扩容，所以会导致迭代器指向旧空间，提前记录相对位置
    if (_finish == _endOfStorage)
    {
        size_t n = capacity() == 0 ? 4 : capacity() * 2;
        reserve(n);
    }
    
    iterator tail = end();
    pos = begin() + old_posi;//更新迭代器
    while (tail > pos)
    {
        *tail = *(tail - 1);//从后往前挨个 向后移动
        tail--;
    }

    *pos = x;//插入数据
    _finish++;
    return pos;
}

erase

最后瞄一下erase

iterator erase(iterator pos)
{
    assert(pos < end());//_finish没有数据，不能取等
    iterator begin = pos+1;
    while (begin != _finish)
    {
        *(begin-1) = *begin;//从前往后挨个  向前移动
        begin++;
    }
    _finish--;
    return pos;
}

迭代器

迭代器：

迭代器屏蔽了底层的实现细节，使得设计人员无需关心容器对象的内存分配就可以直接使用相应接口，达到类似指针的效果.

也就是说迭代器可能是指针，也可能是指针的封装.

上图中迭代器支持的行为是向下兼容的，
假设p1,p2是迭代器，i是常量

Iterator	描述	行为
随机迭代器	支持随机访问的迭代器	p1++，p1- -，p1+i，p1-i，p1==p2，p1>p2，p1<p2
双向迭代器	可以向前或者向后移动的迭代器	p1++，p1- -，p1==p2
前向迭代器	只能向前移动的迭代器	p1++，p1==p2
输入迭代器	只能向前移动并读取的迭代器	p1++，p1==p2
输出迭代器	只能向前移动并写入的迭代器	p1++ ，p1==p2

很明显咱们的vector的迭代器是随机迭代器.

迭代器失效

什么是迭代器失效？
迭代器所指向的节点无效了，既该节点被删除了.

vector迭代器失效场景

场景1：扩容

void test()
{
my_room::vector<int> arr;
for(int i = 0; i < 10; i++)//存入1到10
{
arr.push_back(i+1);
}

my_room::vector<int>::iterator old_back = arr.end()-1;//指向最后一个元素10
arr.reserve(1000);
cout<< *old_back <<endl;//程序崩溃----error代码，请勿模仿
}

扩容之后，old_back指向的空间已经被释放了，此时相当于使用野指针.

事实上，不一定只能通过直接显示调用reserve导致迭代器失效，也可以间接调用reserve发生扩容行为导致迭代器失效;

例如: 使用resize函数可能会扩容,使用insert,push_back函数也可能扩容

总的来说，就是底层涉及扩容的行为，就需要注意迭代器失效的问题.

场景2：删除

void test()
{
my_room::vector<int> arr;
for(int i = 0; i < 10; i++)//存入1到10
{
arr.push_back(i+1);
}

my_room::vector<int>::iterator  start = arr.begin();//指向第一个元素1
while(start != arr.end())//预期删除所有元素
{
arr.erase(start);//------error代码，请勿模仿
}
cout << arr.size();//看看有没有删完,但实际上在vs中直接报错.
}

本来预期的是start一开始指向第一个元素,删除之后,剩下的元素往前移,然后继续删，直到删完.

但是实际上删除行为同样也有迭代器失效的风险.

在这里插入图片描述

迭代器失效解决方案

我们知道在使用vector时，当接口涉及扩容问题或者删除问题时，会有迭代器失效的问题.
解决办法就是使用之前对迭代器重新赋值.

void test()
{
my_room::vector<int> arr;
for(int i = 0; i < 10; i++)
{
arr.push_back(i+1);
}

my_room::vector<int>::iterator old_back = arr.end()-1;
arr.reserve(1000);

old_back = arr.end()-1;
cout<< *old_back <<endl;//程序正常运行
}

void test()
{
my_room::vector<int> arr;
for(int i = 0; i < 10; i++)
{
arr.push_back(i+1);
}

my_room::vector<int>::iterator  start = arr.begin();
while(start != arr.end())
{
start = arr.erase(start);
}
cout << arr.size();//程序正常运行
}

希望本片文章对您有帮助，请点赞支持一下吧😘💕

原文地址：https://blog.csdn.net/m0_73399947/article/details/142498108

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：docker中搭建nacos并将springboot项目的配置文件转移到nacos中
下一篇：下载2001年版英特尔开发手册与使用网易有道词典

Nginx配置及部署前端项目，安排！
Nginx配置及部署前端项目
阅读更多2024-09-27
Spring Cloud全解析：服务调用之OpenFeign简介
OpenFeign是SpringCloud对于Feign进行的再次封装，使其支持了SpringMVC的标准注解以及HttpMessageConverters。直接调用该方法就可以调用该微服务的接口。O
阅读更多2024-09-27
Map和Set，TreeMap和TreeSet，HashMap和HashSet
若左子树不为空，则左子树上的所有节点的值都小于根节点的值. 若右子树不为空，则右子树上的所有节点的值都大于根节点的值左右子树也都是二叉搜索树不存在键值相等的节点。
阅读更多2024-09-27
光耦合器在信号传输和隔离中的作用
本文旨在通过逐步分解光耦合器的工作原理来消除理解光耦合器的盲点。
阅读更多2024-09-27
易盾滑块验证码
这玩意我就搞定get请求和check请求，那个b接口的d参数还是有点问题，还有就是b接口的返回参数怎么用，是不是只是加了cookie我也不确定，所以有高手的话希望可以指导一下。我的虽然能够成功，但是只
阅读更多2024-09-27
【怎样基于Okhttp3来实现各种各样的远程调用，表单、JSON、文件、文件流等待】
基于Okhttp3来实现各种各样的网络调用，支持表单、json、文件、网络流等等
阅读更多2024-09-27
HDL coder使用手册
💡 由于本科毕设女朋友准备使用FPGA完成，因此写这篇文章帮助她快速上手HDL coder的使用，降低前期入门的难度。
阅读更多2024-09-27
【C语言零基础入门篇 - 15】：单链表
链表是数据结构中线性表的一种，其中的每个元素实际上是一个单独的结构体对象，而所有对象都通过每个元素中的指针链接在一起。什么是结点：链表中每个结构体对象叫做结点。什么是首元结点：其中第一个数据结点。什么
阅读更多2024-09-27
数据库主备副本物理复制和逻辑复制对比
数据库主从节点的数据一致性是保证数据库高可用的基本要求，各个数据库在实现方式上也各有异同。而主备复制的方式无外乎两种：物理复制和逻辑复制，本文简要对比下两种方式的不同，并分析下国产数据库是如何实现的。
阅读更多2024-09-27
Java爬虫抓取数据的艺术
在信息时代，数据的重要性不言而喻。对于Java开发者来说，掌握如何使用Java进行数据抓取是一项宝贵的技能。通过编写爬虫程序，我们可以从互联网的海量信息中提取有价值的数据，用于市场分析、客户洞察、内容
阅读更多2024-09-27