c++的学习之路：13、vector（2）

news/2025/4/1 3:30:31/

本章主要是模拟实现vector，文章末附上代码，和源码。

目录

一、STL源码

二、构造与析构

三、迭代器与【】、size、capacity、empty

四、reserve与resize

五、push_back与pop_back

六、insert与erase

七、测试 1

八、代码

九、思维导图

一、STL源码

今天看的是STL30这个源码，他的vector点开是下图这种可以看出他也是调用了几个头文件，上面注释的就是一些开源声明，大概就是说是可以使用、增删查改甚至售卖，做出有用的修改也需要声明。

如下图二可以看出vector的参数是只有三个原生指针，这个就是从图一这里就可以看出是一个typede进行的重定义的。

 他的size，capacity是如下图这样使用的，下面九不一一展示了，源码上传了可以自己看看。

二、构造与析构

如下方代码就是这个构造和析构，这里是放在了我的命名空间中以防和库里面的vector重复，这里是利用了缺省传值，在定义的时候直接赋值为nullptr然后进行一个空的初始化，然后如下方代码中vector(size_t n, const T& val = T())这一句就是利用一个匿名对象进行初始化，因为这样就可以直接使用模板进行构造，因为这样就可以使用不用的类型进行初始化对象，然后又利用了模板参数InputIterator进行初始化，这里就是如上篇文章中可以使用范围进行初始化，这里就是利用迭代器的原理，first就是迭代器的begin，last就是迭代器的end，也就是首和尾，然后进行构造，相当于缺省值的构造，这里面构造是需要开辟空间和插入数据，所以这里先写在这了，代码在后面文章， vector(int n, const T& val = T())有个这个是因为写入的值默认是整形，在构造时会进行隐形类型转换，size_t是无符号整形，需要转化，但是有类模板会优先使用这个就会造成野指针。

namespace ly
{
    template<class T>
    class vector
    {
    public:
        typedef T* iterator;
        typedef const T* const_iterator;

        vector()
        {}

        vector(size_t n, const T& val = T())
        {
            reserve(n);
            for (size_t i = 0; i < n; ++i)
            {
                push_back(val);
            }
        }

        vector(int n, const T& val = T())
        {
            reserve(n);
            for (int i = 0; i < n; ++i)
            {
                push_back(val);
            }
        }

        template <class InputIterator>
        vector(InputIterator first, InputIterator last)
        {
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }

        ~vector()
        {
            delete[] _start;
            _start = _finish = _end_of_storage = nullptr;
        }
    private:
        iterator _start = nullptr;
        iterator _finish = nullptr;
        iterator _end_of_storage = nullptr;
    };

}
 

三、迭代器与【】、size、capacity、empty

如下方代码所示，先看迭代器，在上文中就已经重定义了iterator是T*，所以这里begin就是直接返回start的指针，end就是finish，看过源码和之前模拟实现过string就会发现这里很好用，这里也是同样的有const，因为这里需要重载就是因为需要访问const类型的，size就是finish-start就能得出size，同理capacity就是end_of_storage - start，enpty就是判断是否满了，这里就是start等于finish的时候就是满了，【】就是直接访问就可以了，在pos位置进行访问，这里也是如下方代码所示。

        iterator begin()
        {
            return _start;
        }

        iterator end()
        {
            return _finish;
        }

        const_iterator begin() const
        {
            return _start;
        }

        const_iterator end() const
        {
            return _finish;
        }

        size_t size() const
        {
            return _finish - _start;
        }

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

        bool empty()
        {
            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];
        }

四、reserve与resize

这里是和之前模拟实现string的时候差不多，判断容量是否够，不够减扩容，这里因为需要计算—finish地址，所以提前记录了size，然后创建一个空间，然后利用memcpy进行拷贝数据，在把旧的start释放了，在指向新的空间，在把finish和end_of_storage计算出来就好了，resize也是需要判断是否是缩容，缩容并不需要缩容，只需要删除数据就可以了，扩容也就是需要扩容后，再把数据初始化就可以了。

        void reserve(size_t n)
        {
            if (n > capacity())
            {
                size_t sz = size();
                T* tmp = new T[n];
                if (_start)
                {
                    memcpy(tmp, _start, sizeof(T) * size());
                    delete[] _start;
                }
                _start = tmp;
                _finish = _start + sz;
                _end_of_storage = _start + n;
            }
        }

        void resize(size_t n, T val = T())
        {
            if (n < size())
            {
                _finish = _start + n;
            }
            else
            {
                if (n > capacity())
                {
                    reserve(n);
                }        
                while (_finish != _start + n)
                {
                    *_finish = val;
                    ++_finish;
                }
            }
        }

五、push_back与pop_back

这里就是先判断是否满了，满了就先进行扩容，然后进行存入数据，没满就把数据直接存入，删除也就是直接--覆盖就好了。

        void push_back(const T& x)
        {
            if (_finish == _end_of_storage)
            {
                reserve(capacity() == 0 ? 4 : capacity() * 2);
            }
            *_finish = x;
            ++_finish;
        }

        void pop_back()
        {
            assert(!empty());
            --_finish;
        }

六、insert与erase

如下方代码，这里实现的思路是先断言，pos位置是在start和finish之间，不是就报错，如果刚好数据满了就进行扩容，这里需要注意的是扩容的时候需要进行计算pos的绝对位置，也就是距离start的长度，在扩容后在进行计算pos位置，然后就是挪动数据与把数据存入，erase就不需要判断相等finish的时候，因为满了也可以删，然后在进行挪动覆盖，这个就是erase的实现。

        iterator insert(iterator pos, const T& val)
        {
            assert(pos >= _start);
            assert(pos <= _finish);
            if (_finish == _end_of_storage)
            {
                size_t len = pos - _start;
                reserve(capacity() == 0 ? 4 : capacity() * 2);
                pos = _start + len;
            }
            iterator end = _finish - 1;
            while (end >= pos)
            {
                *(end + 1) = *end;
                --end;
            }
            *pos = val;
            ++_finish;
            return pos;
        }

        void erase(iterator pos)
        {
            assert(pos >= _start);
            assert(pos < _finish);
            iterator start = pos + 1;
            while (start != _finish)
            {
                *(start - 1) = *start;
                ++start;
            }
            --_finish;
        }

七、测试 1

这里就进行测试一下上面写的代码是否有错，如下图的代码就是测试push_back与pop_back的写发，然后这里也是测试了下迭代器的使用，for的实现就是迭代器。

void Print(const vector<int>& v)
    {
        for (auto vi : v)
        {
            cout << vi << ' ';
        }
        cout << endl;
    }

    void Test1()
    {
        vector<int> v1;
        v1.push_back(1);
        v1.push_back(2);
        v1.push_back(3);
        v1.push_back(4);
        Print(v1);
        v1.pop_back();
        v1.pop_back();
        Print(v1);
    }

 

 这里就是测试了下【】与利用模板进行范围的初始化

void Test2()
    {
        vector<int> v1;
        v1.push_back(1);
        v1.push_back(2);
        v1.push_back(3);
        v1.push_back(4);
        Print(v1);
        vector<int> v2(v1.begin(), v1.end());
        Print(v2);
        for (size_t i = 0; i < v2.size(); i++)
        {
            cout << v2[i] << ' ';
        }
        cout << endl;
    } 

 这里是测试插入和删除，这里利用了find找到1和3进行头插和在3的位置插入，如下方所示。

void Test3()
    {
        vector<int> v1;
        v1.push_back(1);
        v1.push_back(2);
        v1.push_back(3);
        v1.push_back(4);
        Print(v1);
        auto pos = find(v1.begin(), v1.end(), 1);
        v1.insert(pos, 0);
        pos = find(v1.begin(), v1.end(), 3);
        v1.insert(pos, 30);
        Print(v1);
        pos = find(v1.begin(), v1.end(), 0);
        v1.erase(pos);
        pos = find(v1.begin(), v1.end(), 30);
        v1.erase(pos);
        Print(v1);
    } 

八、代码

vector.h

#pragma once
#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;namespace ly
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;vector(){}vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; ++i){push_back(val);}}vector(int n, const T& val = T()){reserve(n);for (int i = 0; i < n; ++i){push_back(val);}}template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}bool empty(){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 reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){memcpy(tmp, _start, sizeof(T) * size());delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}}void resize(size_t n, T val = T()){if (n < size()){_finish = _start + n;}else{if (n > capacity()){reserve(n);}		while (_finish != _start + n){*_finish = val;++_finish;}}}void push_back(const T& x){if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;}void pop_back(){assert(!empty());--_finish;}iterator insert(iterator pos, const T& val){assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = val;++_finish;return pos;}void erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator start = pos + 1;while (start != _finish){*(start - 1) = *start;++start;}--_finish;}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};void Print(const vector<int>& v){for (auto vi : v){cout << vi << ' ';}cout << endl;}void Test1(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);Print(v1);v1.pop_back();v1.pop_back();Print(v1);}void Test2(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);Print(v1);vector<int> v2(v1.begin(), v1.end());Print(v2);for (size_t i = 0; i < v2.size(); i++){cout << v2[i] << ' ';}cout << endl;}void Test3(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);Print(v1);auto pos = find(v1.begin(), v1.end(), 1);v1.insert(pos, 0);pos = find(v1.begin(), v1.end(), 3);v1.insert(pos, 30);Print(v1);pos = find(v1.begin(), v1.end(), 0);v1.erase(pos);pos = find(v1.begin(), v1.end(), 30);v1.erase(pos);Print(v1);}
}

test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include "vector.h"int main()
{ly::Test3();
}

 

九、思维导图


http://www.ppmy.cn/news/1409400.html

相关文章

ChatGPT Excel 大师

ChatGPT Excel 大师

原文&#xff1a;ChatGPT Excel Mastery 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 序言 欢迎来到 Excel 掌握的变革之旅&#xff0c;在这里&#xff0c;尖端技术和永恒专业知识在“ChatGPT Excel 掌握&#xff1a;释放专家技巧和窍门的力量”中融合。在当今快节…
阅读更多...
vue3+elementPlus：实现数字滚动效果（用于大屏可视化）

vue3+elementPlus：实现数字滚动效果（用于大屏可视化）

自行封装注册一个公共组件 案例一&#xff1a; //成功案例&#xff1a; //NumberScroll.vue /* 数字滚动特效组件 NumberScroll */<template><span class"number-scroll-grow"><spanref"numberScroll":data-time"time"class&qu…
阅读更多...
【单片机】74HC4052电路图，单片机端口复用电路

【单片机】74HC4052电路图，单片机端口复用电路

74HC4052电路图 如下图&#xff0c;还是很好理解&#xff0c;PA9、PA10是单片机引脚。 当A和B是00&#xff0c;那么就是X-COM和0X短路&#xff0c;Y-COM和0Y短路。 当A和B是01&#xff0c;那么就是X-COM和1X短路&#xff0c;Y-COM和1Y短路。 以此类推。 74HC 工艺可以直接3.…
阅读更多...
RocketMq实现单条发送，批量消费

RocketMq实现单条发送，批量消费

1.传送门 安装RocketMq&#xff0c;RocketMq图形界面&#xff0c;spring boot集成RocketMq&#xff0c;参考以下三篇 本文安装版本是目前最新版RocketMq 5.2.0 安装RocketMq&#xff08;服务器Mq配置外网IP&#xff09;_rocket mq如何不使用ip连接-CSDN博客 RocketMq安装控…
阅读更多...
python爬虫学习第十五天-------ajax的get和post请求

python爬虫学习第十五天-------ajax的get和post请求

嗨嗨嗨&#xff01;兄弟姐妹大家好哇&#xff01;今天我们来学习ajax的get和post请求 一、了解ajax Ajax&#xff08;Asynchronous JavaScript and XML&#xff09;是一种在 Web 开发中用于创建交互式网页应用程序的技术。通过 Ajax&#xff0c;网页可以在不重新加载整个页面…
阅读更多...
Linux 常用指令及其理论知识

Linux 常用指令及其理论知识

个人主页&#xff1a;仍有未知等待探索-CSDN博客 专题分栏&#xff1a;http://t.csdnimg.cn/Tvyou 欢迎各位指教&#xff01;&#xff01;&#xff01; 目录 一、理论知识 二、基础指令 1、ls指令&#xff08;列出该目录下的所有子目录和文件&#xff09; 语法&#xff1a; …
阅读更多...
俺们家Copilot和ChatGPT可不是一回事

俺们家Copilot和ChatGPT可不是一回事

俺们微软真的很想让大家使用俺们家的 Copilot 人工智能工具&#xff0c;不管大家是否愿意 。 一份新的报告显示&#xff0c;一些客户遇到了一个问题&#xff1a;它没有 ChatGPT 那么好用。但俺们微软认为&#xff0c;问题出在他们没能正确使用俺们家 Copilot 或不理解这两种产…
阅读更多...
[xboard]real6410-3 S3C6410光盘资料与功能测试

[xboard]real6410-3 S3C6410光盘资料与功能测试

文章目录 1 real6410官方资源1 官方镜像2 官方源码3 官方测试2 ok6410a资源官方镜像3 友善6410资源1 官方镜像4 友坚5 uboot学习参考1 real6410官方资源 1 官方镜像 2 官方源码 3 官方测试 2 ok6410a资源 官方镜像 http://bbs.witech.com.cn/thread-44722-1-1.h
阅读更多...
最新文章

Copyright @ 2022~2023