STL之vector容器的介绍与模拟实现

STL之vector容器的介绍与模拟实现

  • 1. vector简介
  • 2. vector容器使用
    • 2.1vectord 定义
    • 2.2 vector iterator 的使用
    • 2.3 vector 空间增长问题
    • 2.4 注意事项
  • 3. vector功能模拟实现
    • 3.1 架构搭建
    • 3.2 空间控制板块
    • 3.3 迭代器
    • 3.4 增加/删除数据
    • 3.5 运算符重载
    • 3.6构造/析构
  • 4. 整体代码

所属专栏：C“嘎嘎" 系统学习❤️
🚀 >博主首页：初阳785❤️
🚀 >代码托管：chuyang785❤️
🚀 >感谢大家的支持，您的点赞和关注是对我最大的支持！！！❤️
🚀 >博主也会更加的努力，创作出更优质的博文！！❤️

1. vector简介

vector的文档介绍

  1. vector是表示可变大小数组的序列容器。
  2. 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素
    进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自
    动处理。
  3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小
    为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是
    一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大
    小。
  4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存
    储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是
    对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
  5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增
    长。
  6. 与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末
    尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list
    统一的迭代器和引用更好。

2. vector容器使用

一下垒列出的都是一些比较重要的接口。

2.1vectord 定义

(constructor)构造函数声明接口说明
vector()（重点）无参构造
vector（size_type n, const value_type& val = value_type()）构造并初始化n个val
vector (const vector& x);（重点） 拷贝构造
vector (InputIterator first, InputIterator last);使用迭代器进行初始化构造

2.2 vector iterator 的使用

iterator的使用接口说明
begin +end（重点）获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置的iterator/const_iterator
rbegin + rend获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator

2.3 vector 空间增长问题

容量空间接口说明
size获取数据个数
capacity获取容量大小
empty判断是否为空
resize（重点）改变vector的size
reserve （重点）改变vector的capacity

2.4 注意事项

  1. capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。
    这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义
    的。vs是PJ版本STL，g++是SGI版本STL。
  2. reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
  3. resize在开空间的同时还会进行初始化，影响size。

3. vector功能模拟实现

3.1 架构搭建

  • 由于本次的模拟实现是基于STL库源码来模拟实现的，所以我们的本次模拟实现的整体构架是来自STL源码库的

1.首先为了防止与库里面的STL发生冲突，首先就要设置命名空间。
2.其次，从使用vector容器来看，我们容器中可以存放各种数据类型的数据，所以要用到模板。
3.在STL标准库中，使用三个指针来确定容器capacity，size的。_start指向数据块的开始，_finish指向有效数据的尾，_endOfStorage指向存储容量的尾。有了这三个指针，我们可以计算出大小，容量，以及迭代器的返回。

namespace qfw
{
	template<calss T>
	class vector
	{
	public:
		typedef T* iterator;
        typedef const T* const_iterator;
        
		vector()
		{……}
		
		~vector()
		{……}
		
	private:
		iterator _start = nullptr; // 指向数据块的开始
        iterator _finish = nullptr; // 指向有效数据的尾
        iterator _endOfStorage = nullptr; // 指向存储容量的尾
	};
}

3.2 空间控制板块

  1. 返回数据的大小size()
size_t size() const
{
    return _finish - _start;
}
  1. 返回容器的容量capacity()
size_t capacity() const
{
    return _endOfStorage - _start;
}
  1. 修改容器的容量reserve()
    在这里插入图片描述
void reserve(size_t n)
{
    if (n > capacity())
    {
        size_t old = size();//记录原来_finish的位置，防止迭代器失效
        T* tmp = new T[n];//开新的的空间
        //将数据拷贝到新的空间
        for (int i = 0; i < old; i++)
        {
            tmp[i] = _start[i];
        }
        //删除旧的空间
        delete[] _start;
        //指向新新空间，更新数据
        _start = tmp;
        _finish = _start + old;
        _endOfStorage = _start + n;
    }
}
  1. 修改容器数据的大小resize()
void resize(size_t n, const T& value = T())
{
    if (n > size())
    {
        reserve(n);
        while (_finish < _start + n)
        {
            *_finish = value;
            ++_finish;
        }
    }
    else
    {
        _finish = _start + n;
    }
}

注意：这里用到的缺省参数的知识点，但是我们容器是可以存放各种数据类型的数据的，所以我们的缺省值因该也是要对应着给对应的缺省值的也就是T()。但是这个也不是好理解，如果是T是string类型的话，string()是一个匿名对象，回去调用string的默认构造，也就是说如果T类型是自定义类型的话说的过来，它回去调用它的默认构造。但是如果T是内置类型的话怎么办，我们之前学习的时候是了解到内置类型是没有默认构造的，那这里怎么说到过去呢？所以为了解决这个问题，C++给内置类型开了后面，允许内置类型有默认构造。

3.3 迭代器

迭代器提供两个版本，const和非const版本。

iterator begin()
{
    return _start;
}
iterator end()
{
    return _finish;
}

const_iterator begin() const
{
    return _start;
}
const_iterator end() const
{
    return _finish;
}

3.4 增加/删除数据

  1. 尾插push_back()
void push_back(const T& x)
{
    if (_finish == _endOfStorage)
    {
        int newcapcity = capacity() == 0 ? 4 : capacity() * 2;
        reserve(newcapcity);
    }
    *(_finish) = x;
    ++_finish;
}
  1. 尾删pop_back()
void pop_back()
{
    assert(_finish >= _start);
    --_finish;
}
  1. 在任意位置增加insert()
iterator insert(iterator pos, const T& x)
{
    assert(pos >= _start);
    assert(pos <= _finish);

    if (_finish == _endOfStorage)
    {
        //防止扩容的时候迭代器失效
        size_t old = pos - _start;
        reserve(capacity() == 0 ? 4 : capacity() * 2);
        pos = _start + old;
    }

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

    return pos;
}
  1. 在任意位置删除erase()
iterator erase(iterator pos)
{
    assert(pos >= _start);
    assert(pos < _finish);

    iterator cur = pos + 1;
    while (cur < _finish)
    {
        *(cur - 1) = *cur;
        cur++;
    }
    --_finish;
}

3.5 运算符重载

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

3.6构造/析构

//默认构造调用初始化列表，调用缺省值
vector()
{}

//有参构造
vector(int n, const T& value = T())
{
    resize(n);
}

//区间构造
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
    while (first < last)
    {
        push_back(*first);
        ++first;
    }
}

//拷贝构造
vector(const vector<T>& v)
{
    reserve(v.capacity());
    for (const auto& e : v)
    {
        push_back(e);
    }
}

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

//赋值
vector<T>& operator= (vector<T> v)//注意这里串的不是引用，而是值转递
{
    swap(v);
    return *this;
}

//析构
~vector()
{
    if (_start)
    {
        delete[] _start;
        _start = _finish = _endOfStorage = nullptr;
    }
}

4. 整体代码

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

namespace qfw
{
    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(int n, const T& value = T())
        {
            resize(n);
        }

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

        //拷贝构造
        vector(const vector<T>& v)
        {
            reserve(v.capacity());
            for (const auto& e : v)
            {
                push_back(e);
            }
        }

        //赋值
        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];//开新的的空间
                //将数据拷贝到新的空间
                for (int 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& value = T())
        {
            if (n > size())
            {
                reserve(n);
                while (_finish < _start + n)
                {
                    *_finish = value;
                    ++_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)
        {
            if (_finish == _endOfStorage)
            {
                int newcapcity = capacity() == 0 ? 4 : capacity() * 2;
                reserve(newcapcity);
            }
            *(_finish) = x;
            ++_finish;
        }
        void pop_back()
        {
            assert(_finish >= _start);
            --_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);
            assert(pos <= _finish);

            if (_finish == _endOfStorage)
            {
                //防止扩容的时候迭代器失效
                size_t old = pos - _start;
                reserve(capacity() == 0 ? 4 : capacity() * 2);
                pos = _start + old;
            }

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

            return pos;
        }
        iterator erase(iterator pos)
        {
            assert(pos >= _start);
            assert(pos < _finish);

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/330578.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

vscode mysql cmake windows 常见问题和推荐文章

vscode mysql cmake windows 常见问题和推荐文章

1.在windows中安装mingw64和cmake&#xff08;可查一下网上的安装教程&#xff09;&#xff0c;配置环境变量 2.在vscode中用CMake构建项目的时候&#xff0c;可能会出现这样的问题:“The C compiler identification is unknownn...”,可参考这篇博客 在windows下使用Vscode用…
阅读更多...
Java基础面试题（四）

Java基础面试题（四）

Java基础面试题&#xff08;四&#xff09; 文章目录 Java基础面试题&#xff08;四&#xff09;Oracle JDK vs OpenJDKJava 和 C 的区别? 文章来自Java Guide 用于学习如有侵权&#xff0c;立即删除 Oracle JDK vs OpenJDK 可能在看这个问题之前很多人和我一样并没有接触和使…
阅读更多...
基于springboot+vue的图书个性化推荐系统(前后端分离)

基于springboot+vue的图书个性化推荐系统(前后端分离)

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战 主要内容&#xff1a;毕业设计(Javaweb项目|小程序等)、简历模板、学习资料、面试题库、技术咨询 文末联系获取 项目背景…
阅读更多...
1. 安装Git

1. 安装Git

01. 安装Git 最早Git是在Linux上开发的&#xff0c;很长一段时间内&#xff0c;Git也只能在Linux和Unix系统上跑。不过&#xff0c;慢慢地有人把它移植到了Windows上。现在&#xff0c;Git可以在Linux、Unix、Mac和Windows这几大平台上正常运行了。 要使用Git&#xff0c;第一…
阅读更多...
【C++入门到精通】智能指针 auto_ptr、unique_ptr简介及C++模拟实现 [ C++入门 ]

【C++入门到精通】智能指针 auto_ptr、unique_ptr简介及C++模拟实现 [ C++入门 ]

阅读导航 引言一、std::auto_ptr1. 简介2. 使用示例3. C模拟实现 二、std::unique_ptr1. 简介2. 使用示例3. C模拟实现 温馨提示 引言 在 C 中&#xff0c;智能指针是一种非常重要的概念&#xff0c;它能够帮助我们自动管理动态分配的内存&#xff0c;避免出现内存泄漏等问题。…
阅读更多...
靶机-Billu_b0x root 123456

靶机-Billu_b0x root 123456

查找靶机IP nmap查看开放端口22&#xff0c;80 目录扫描 查看网站&#xff0c;典型注入 phpmy 果然是登陆界面&#xff0c;不过不知道账户及密码 in.php php的配置信息&#xff0c;可以看看 add.php 上传文件目录&#xff0c;可以上传&#xff0c;不过没有回显 …
阅读更多...
C# ObjectArx 绘制表格并设置单元格合并

C# ObjectArx 绘制表格并设置单元格合并

第一行默认是标题&#xff0c;可设置行【RowType】进行设置类型 Document doc Application.DocumentManager.MdiActiveDocument;using (Transaction tr doc.TransactionManager.StartOpenCloseTransaction()){BlockTable bt tr.GetObject(doc.Database.BlockTableId, OpenMo…
阅读更多...
UE4 添加按键输入事件 并在蓝图中使用按键输入节点

UE4 添加按键输入事件 并在蓝图中使用按键输入节点

绑定按键 选择Edit/ProjectSettings/Engine/Input 在bindings中可以选择添加ActionMappings或则AxisMappings ActionMappings:按键事件&#xff0c;有按下和抬起两个事件&#xff0c;需要分别用两个键触发AxisMappings:输入事件&#xff0c;返回值为float&#xff0c;对于键盘…
阅读更多...
Rust之构建命令行程序(三)：重构改进模块化和错误处理

Rust之构建命令行程序(三)：重构改进模块化和错误处理

开发环境 Windows 10Rust 1.74.1 VS Code 1.85.1 项目工程 这次创建了新的工程minigrep. 重构改进模块化和错误处理 为了改进我们的程序&#xff0c;我们将修复与程序结构及其处理潜在错误的方式有关的四个问题。首先&#xff0c;我们的main函数现在执行两项任务:解析参数和…
阅读更多...
一文了解Servlet

一文了解Servlet

文章目录 1、什么是Servlet2、Servlet快速入门3、Servlet生命周期4、Servlet体系结构5、urlPatern配置6、XML编写Servlet 1、什么是Servlet Servlet是Java提供的一门动态web资源开发技术Servlet是JavaEE规范之一&#xff0c;其实就是一个接口&#xff0c;将来我们需要定义Serv…
阅读更多...
Apache JMeter 5.6.3压力测试步骤详解

Apache JMeter 5.6.3压力测试步骤详解

Apache JMeter 5.6.3压力测试步骤详解 压力测试简介软件测试概述性能测试性能测试指标性能指标推算web资源公式 1. 安装 Jmeter2. 创建测试任务2.1 创建线程组2.2 创建 HTTP 请求2.3 添加HTTP消息头管理器 3.添加查看结果监听器4. 执行测试5. 查看结果6. 非GUI模式测试7. 使用c…
阅读更多...
CSS||Emmet语法

CSS||Emmet语法

1、简介 ​ Emmet语法的前身是Zen coding,它使用缩写,来提高html/css的编写速度, Vscode内部已经集成该语法。 ​ 快速生成HTML结构语法 ​ 快速生成CSS样式语法 2、快速生成HTML结构语法 生成标签 直接输入标签名 按tab键即可 比如 div 然后tab 键&#xff0c; 就可以生成 <…
阅读更多...
CSS 设置背景图片

CSS 设置背景图片

文章目录 设置背景颜色设置背景图片背景图片偏移量计算原点背景图片尺寸设置背景图片位置设置背景图片重复方式设置背景范围设置背景图片是否跟随元素移动测试背景图片 本文概念部分参考&#xff1a;CSS背景background设置 设置背景颜色 background-color 设置背景颜色 设置…
阅读更多...
UE5 独立程序的网络TCP/UDP服务器与客户端基础流程

UE5 独立程序的网络TCP/UDP服务器与客户端基础流程

引擎源码版&#xff0c;复制\Engine\Source\Programs\路径下的BlankProgram空项目示例。 重命名BlankProgram&#xff0c;例如CustomTcpProgram&#xff0c;并修改项目名称。 修改.Build.cs内容 修改Target.cs内容 修改Private文件夹内.h.cpp文件名并修改.cpp内容 刷新引擎 …
阅读更多...
联想模拟器抓包

联想模拟器抓包

联想模拟器抓包 下载抓包工具配置代理并启动模拟器配置代理返回reqable查看抓包数据 下载抓包工具 reqable 配置代理并启动 模拟器配置代理 返回reqable查看抓包数据
阅读更多...
定义公共样式css

定义公共样式css

index.less 文件 // 全局按钮颜色 btn_background: #005298; btn_border-color: #6fa18d;// 默认的 btn_border-color-highlight: #0598d3;// 高亮边框 btn_border-color-success: #36be7e;// 成功边框 btn_font_color: #fff;// 边框颜色 背景色 文字颜色 .btn_public(btn_bo…
阅读更多...
外贸网站建设有哪些技巧？如何做海洋建站？

外贸网站建设有哪些技巧？如何做海洋建站？

搭建外贸网站需要什么流程步骤&#xff1f;独立网站建站怎么做&#xff1f; 外贸网站的建设变得至关重要。一家成功的外贸企业需要一个强大而专业的在线存在&#xff0c;以便吸引国际客户。在这篇文章中&#xff0c;海洋建站将探讨一些关键的技巧&#xff0c;帮助您打造出色的…
阅读更多...
Vg3225vfn压控晶体振荡器规格书

Vg3225vfn压控晶体振荡器规格书

频率范围: 25mhz ~ 500mhz电源电压:3.3 V类型绝对拉力范围:50 10 6分钟。/ 25mhz至42.5 MHz50 MHz至85 MHz&#xff0c;100mhz ~ 170mhz:20 10 6最小&#xff0c;10 10 6分钟。/ 25mhz ~ 250mhz:10 10 6分钟。/ 250 MHz至500 MHz(85C最高)操作温度温度范围:-40℃~ 85℃温度…
阅读更多...
低代码开发：解锁数字化转型新维度

低代码开发：解锁数字化转型新维度

在信息化浪潮中&#xff0c;企业正面临着前所未有的挑战与机遇。一方面&#xff0c;市场环境瞬息万变&#xff0c;业务需求迭代频繁&#xff0c;对快速应用开发提出了更高要求&#xff1b;另一方面&#xff0c;传统软件开发模式受限于高成本、长周期等瓶颈&#xff0c;难以满足…
阅读更多...
C++、QT 数字合成游戏

C++、QT 数字合成游戏

一、项目介绍 数字合成游戏 基本要求&#xff1a; 1&#xff09;要求游戏界面简洁美观&#xff0c;且符合扫雷的游戏风格。 2&#xff09;需要有游戏操作或者规则说明&#xff0c;方便玩家上手。 3&#xff09;需具有开始游戏&#xff0c;暂停游戏&#xff0c;结束游戏等方便玩…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站