C++ 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统一的迭代器和引用更好。

参考侯捷老师《STL源码刨析》这本书画的：

Vector的一些接口：

namespace MyVector
{
	template<class T>
    class vector
    {
             
        public:

        // Vector的迭代器是一个原生指针

        typedef T* iterator;
        typedef const T* const_iterator;

        iterator begin();
        iterator end();
        
        const_iterator cbegin() const;
        const_iterator cend() const;   

        // 初始化
        vector();
        // 析构
        ~vector();

        vector(int n, const T& value = T());
        vector(size_t n, const T& val = T());

        //类模板的成员函数可以是函数模板
        template<class InputIterator>
        vector(InputIterator first, InputIterator last);

        vector(const vector<T>& v);
        vector<T>& operator= (vector<T> v);
        
        size_t size() const;
        size_t capacity() const;

        void reserve(size_t n);
        void resize(size_t n, const T& value = T());
        
        T& operator[](size_t pos);
        const T& operator[](size_t pos)const;
        
        bool empty();
        void push_back(const T& x);
        void pop_back();

        void swap(vector<T>& v);
    
        iterator insert(iterator pos, const T& x);
        iterator erase(iterator pos);

        private:

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

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

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

    };
}

iterator begin()

        iterator begin()
        {
            return _start;
        }

iterator end()

        iterator end()
        {
            return _finish;
        }

const_iterator cbegin()

        const_iterator cbegin()
        {
            return _start;
        }

const_iterator cend() const

        const_iterator cend() const
        {
            return _finish;
        }

四个比较简单的迭代器

vector()

        vector()
            :_start(nullptr)
            ,_finish(nullptr)
            , _endOfStorage(nullptr)
        {}

~vector()

        ~vector()
        {
            delete[] _start;
            _start = _finish = _endOfStorage;
        }

初始化与析构

        //类模板的成员函数可以是函数模板
        template<class InputIterator> // InputIterator定义的一个迭代器类型

        vector(InputIterator first, InputIterator last)
            :_start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }

vector<T>& operator= (vector<T> v)

        vector<T>& operator= (vector<T> v)
        {
            swap(v);
            return *this;
        }

        // v1 = v3

size_t size() const

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

        // 有效数据的尾减去数据块的开始就是元素个数

size_t capacity() const

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

        // 开辟空间的容量

void reserve(size_t n)

        void reserve(size_t n)
        {
            if (n > capacity())
            {
                T* tmp = new T[n];
                size_t old_size = size();
                for (size_t i = 0; i < old_size; i++)
                {
                    tmp[i] = _start[i]; // 深拷贝

                }
                delete[] _start;

                _start = tmp; // 老的_start已经失效，更新一下
                _finish = tmp + old_size;
                _endOfStorage = tmp + n;
            }
        }

void resize(size_t n, const T& value = T())

        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;
            }
        }

vector(const vector<T>& v)

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

        // v2(v1) 用已经存在的 v1 去初始化 v2

T& operator[](size_t pos)

const T& operator[](size_t pos)const

        T& operator[](size_t pos)
        {
            assert(pos < size()); // 保证下标为有效数据
            return _start[pos];
        }

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

iterator insert(iterator pos, const T& x)

        iterator insert(iterator pos, const T& x)
        {
            assert(pos >= _start);
            assert(pos <= _finish);
            if (_finish == _endOfStorage)
            {
                size_t len = pos - _start;
                reserve(capacity() == 0 ? 4 : 2 * capacity());

                //如果扩容了要更新pos
                pos = _start + len;
            }
            iterator it = _finish - 1;
            while (it >= pos)
            {
                *(it + 1) = *it;
                --it;
            }
            *pos = x;
            ++_finish;
        }

iterator erase(iterator pos)

        iterator erase(iterator pos)
        {
            assert(pos >= _start);
            assert(pos <= _finish);
            iterator it = pos + 1;
            while (it < _finish)
            {
                *(it - 1) = *it;
                --it;
            }
            --_finish;
            return pos;
        }

vector(int n, const T& value = T())

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

vector(size_t n, const T& val = T())

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

bool empty()

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

void push_back(const T& x)

        void push_back(const T& x)
        {
            insert(end(), x);
        }

void pop_back()

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

void swap(vector<T>& v)

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

完整代码：

#pragma once

#include <assert.h>

namespace bit
{
	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()
        {
            return _start;
        }

        const_iterator cend() const
        {
            return _finish;
        }


        // construct and destroy

        vector()
            :_start(nullptr)
            ,_finish(nullptr)
            , _endOfStorage(nullptr)
        {}

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

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


        //类模板的成员函数可以是函数模板
        template<class InputIterator>

        vector(InputIterator first, InputIterator last)
            :_start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }


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

        vector<T>& operator= (vector<T> v)
        {
            swap(v);
            return *this;
        }

        ~vector()
        {
            delete[] _start;
            _start = _finish = _endOfStorage;
        }


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

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

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

                }
                delete[] _start;

                _start = tmp;
                _finish = tmp + old_size;
                _endOfStorage = tmp + 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;
            }
        }





        T& operator[](size_t pos)
        {
            assert(pos < size());
            return _start[pos];
        }

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


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

        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);
        }

        iterator insert(iterator pos, const T& x)
        {
            assert(pos >= _start);
            assert(pos <= _finish);
            if (_finish == _endOfStorage)
            {
                size_t len = pos - _start;
                reserve(capacity() == 0 ? 4 : 2 * capacity());

                //如果扩容了要更新pos
                pos = _start + len;
            }
            iterator it = _finish - 1;
            while (it >= pos)
            {
                *(it + 1) = *it;
                --it;
            }
            *pos = x;
            ++_finish;
        }

        iterator erase(iterator pos)
        {
            assert(pos >= _start);
            assert(pos <= _finish);
            iterator it = pos + 1;
            while (it < _finish)
            {
                *(it - 1) = *it;
                --it;
            }
            --_finish;
            return pos;
        }

    private:

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

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

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

    };

}

测试代码：

#include <iostream>
#include<algorithm>
#include<vector>

#include "Vector.h"

using namespace std;

int main()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	cout << v.size() << endl;
	cout << v.capacity() << endl;
	for (size_t i = 0; i < v.size(); i++)
	{
		cout << v[i] << " ";
	}
	cout << endl;

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

	v.reserve(30);
	cout << v.capacity() << endl;
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	vector<int> v1(v);
	v1.push_back(100);
	v1.push_back(200);
	v1.pop_back();
	for (auto e : v1)
	{
		cout << e << " ";
	}
}

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

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

相关文章

Python使用tkinter制作无边框透明时钟源码讲解（tkinter如何实现窗口无边框透明）

Python使用tkinter制作无边框透明时钟源码讲解（tkinter如何实现窗口无边框透明）

文章目录 📖 介绍 📖🏡 演示环境 🏡📒 文章内容 📒📝 导入必要的库📝 创建主窗口🎯 去掉窗口边框🎯 设置窗口透明度🎯 允许窗口背景透明🎯 设置窗口背景颜色为透明🎯 设置窗口位置🎯 创建用于显示时间的标签📝 更新时间函数📝 使窗口可移动📝…
阅读更多...
java打印金字塔paremid和空心金字塔

java打印金字塔paremid和空心金字塔

java打印金字塔 首先确定每行打印几个空格&#xff0c;在确定每行打印几个* 设总层数为layers&#xff0c;当前层数为i。 则每行打印空格数layers-i&#xff0c;每行打印星号数2*i-1 import java.util.Scanner;public class Paremid{public static void main(String[] args) …
阅读更多...
2024华为OD机试真题-生成哈夫曼树-(C++/Python)-C卷D卷-100分

2024华为OD机试真题-生成哈夫曼树-(C++/Python)-C卷D卷-100分

2024华为OD机试题库-(C卷+D卷)-(JAVA、Python、C++) 题目描述 给定长度为 n 的无序的数字数组，每个数字代表二叉树的叶子节点的权值，数字数组的值均大于等于1。 请完成一个函数，根据输入的数字数组，生成哈夫曼树，并将哈夫曼树按照中序遍历输出。 为了保证输出的二叉树中…
阅读更多...
6.S081的Lab学习——Lab7: Multithreading

6.S081的Lab学习——Lab7: Multithreading

文章目录 前言一、Uthread: switching between threads (moderate)提示&#xff1a;解析 二、Using threads (moderate)解析&#xff1a; 三、Barrier (moderate)解析&#xff1a; 总结 前言 一个本硕双非的小菜鸡&#xff0c;备战24年秋招。打算尝试6.S081&#xff0c;将它的…
阅读更多...
html侧导航栏客服栏

html侧导航栏客服栏

ico 替换 ICO <html xmlns"http://www.w3.org/1999/xhtml"><head><meta http-equiv"Content-Type" content"text/html; charsetutf-8"><title>返回顶部</title><script src"js/jquery-2.0.3.min.js"…
阅读更多...
项目四 OpenStack身份管理

项目四 OpenStack身份管理

任务一 理解身份服务 1.1 •Keystone的基本概念 • 认证 &#xff08; Authentication &#xff09; —— 确认用户身份的过程 &#xff0c;又称身份验证 。 • 凭证 &#xff08; Credentials &#xff09; —— 又 称凭据&#xff0c;是用于 确认用户身份的数据 。 • 令牌…
阅读更多...
SpringMVC系列三: Postman(接口测试工具)

SpringMVC系列三: Postman(接口测试工具)

接口测试工具 &#x1f49e;Postman(接口测试工具)Postman介绍Postman是什么Postman相关资源Postman安装Postman快速入门Postman完成Controller层测试其它说明 &#x1f49e;课后作业 上一讲, 我们学习的是SpringMVC系列二: 请求方式介绍 现在打开springmvc项目 &#x1f49e…
阅读更多...
三电平光伏逆变器高效DPWM研究

三电平光伏逆变器高效DPWM研究

1. 引言 本文从效率 提升角度出发 , 详细分析了逆变器不同调制策略下开关 器件及滤波器损耗分布情况 , 并在 50kW 组串式三电平光伏逆变器上对比分析采用 SVPWM 和 DPWM 两种 调制方法对逆变器效率和谐波的影响 , 最终验证了采用 DPWM 调制策略的优越性。 2 SVPWM 和 DPWM 对比…
阅读更多...
浙江工商大学24计算机考研数据，好几个专业都接收调剂，计专复试线284分！

浙江工商大学24计算机考研数据，好几个专业都接收调剂，计专复试线284分！

浙江工商大学&#xff08;Zhejiang Gongshang University&#xff09;&#xff0c;简称“浙商大”&#xff08;ZJSU&#xff09;&#xff0c;坐落于浙江省杭州市&#xff0c;是中华人民共和国教育部、中华人民共和国商务部和浙江省人民政府共建的浙江省重点建设高校&#xff0c…
阅读更多...
解决：Xshell通过SSH协议连接Ubuntu服务器报“服务器发送了一个意外的数据包，received：3，expected：20”

解决：Xshell通过SSH协议连接Ubuntu服务器报“服务器发送了一个意外的数据包，received：3，expected：20”

下图所示&#xff1a; 日志也基本看不出来问题在哪&#xff0c;只是说断开了连接大概是验证失败。有幸在某论坛评论区找到了原因&#xff0c;是因为我的xshell版本太低了而服务器的ssh版本太高&#xff0c;高版本的ssh默认屏蔽了一部分不太安全的算法导致建立连接的时候验证失败…
阅读更多...
“论软件架构风格”必过范文，软考高级，系统架构设计师论文

“论软件架构风格”必过范文，软考高级，系统架构设计师论文

论文真题 软件体系结构风格是描述某一特定应用领域中系统组织方式的惯用模式。体系结构风格定义一个系统家族，即一个体系结构定义一个词汇表和一纽约束。词汇表中包含一些构件和连接件类型，而这组约束指出系统是如何将这些构件和连接件组合起来的。体系结构风格反应了领域中…
阅读更多...
全国青少年人工智能创新挑战赛考试系统果然卡壳了

全国青少年人工智能创新挑战赛考试系统果然卡壳了

本比赛的官网地址是&#xff1a;http://aiic.china61.org.cn/niWXB 昨天考的全国青少年人工智能创新挑战赛的图形化编程卡的没有答题区&#xff0c;有的是空白&#xff0c;有的是组卷&#xff0c;大家先熟悉题目&#xff0c;构思怎么编程&#xff0c;两道编程题5050分值&#…
阅读更多...
1.Triangle

1.Triangle

一、你好&#xff0c;三角形 在OpenGL中&#xff0c;任何事物都在3D空间中&#xff0c;而屏幕和窗口却是2D像素数组&#xff0c;这导致OpenGL的大部分工作都是关于把3D坐标转变为适应你屏幕的2D像素。 3D坐标转为2D坐标的处理过程是由OpenGL的图形渲染管线&#xff08;Graphi…
阅读更多...
Hallo技术：革新电影、游戏与虚拟现实中的动态肖像动画

Hallo技术：革新电影、游戏与虚拟现实中的动态肖像动画

在数字娱乐的浪潮中&#xff0c;逼真的动态肖像动画成为了电影制作、游戏开发和虚拟现实等领域不可或缺的一部分。复旦大学研发的Hallo技术&#xff0c;以其独特的扩散模型和分层音频驱动视觉合成模块&#xff0c;为这一领域带来了革命性的突破。 技术概览 Hallo技术是一种基…
阅读更多...
【UML用户指南】-20-对基本行为建模-交互图

【UML用户指南】-20-对基本行为建模-交互图

目录 1、概述 2、顺序图 2.1、两个不同于通信图的特征&#xff1a; 2.1.1、顺序图有对象生命线 2.1.2、顺序图有控制焦点 2.2、结构化控制 2.2.1、可选执行opt 2.2.2、条件执行alt 2.2.3、并行执行par 2.2.4、循环迭代执行loop 2.3、嵌套活动图 3、通信图 3.1、两…
阅读更多...
Redis进阶 - 朝生暮死之Redis过期策略

Redis进阶 - 朝生暮死之Redis过期策略

概述 Redis 是一种常用的内存数据库&#xff0c;其所有的数据结构都可以设置过期时间&#xff0c;时间一到&#xff0c;就会自动删除。你可以想象 Redis 内部有一个死神&#xff0c;时刻盯着所有设置了过期时间的 key&#xff0c;寿命一到就会立即收割。 你还可以进一步站在死神…
阅读更多...
关于笔记本电脑连接电源时触摸板失灵、卡顿、乱飘的问题

关于笔记本电脑连接电源时触摸板失灵、卡顿、乱飘的问题

目录 前言 问题原因 解决方法 前言 我查阅了相关的资料和方法如下&#xff08;很感谢这位楼主大佬提供的问题所在&#xff09;&#xff1a; 问题原因 解决方法 那么解决方法无非就是几种&#xff08;方法仅供参考&#xff0c;不排除一些危险性&#xff09;&#xff1a; 1…
阅读更多...
扫码称重上位机

扫码称重上位机

目录 一 设计原型 二 后台代码 一 设计原型 模拟工具: 二 后台代码 主程序&#xff1a; using System.IO.Ports; using System.Net; using System.Net.Sockets; using System.Text;namespace 扫码称重上位机 {public partial class Form1 : Form{public Form1(){Initialize…
阅读更多...
测试辅助工具(抓包工具)的使用1 之初识抓包工具（fiddler）

测试辅助工具(抓包工具)的使用1 之初识抓包工具（fiddler）

1.什么是抓包&#xff1f; 说明&#xff1a;客户端向服务器发送请求以及服务器响应客户端的请求,都是以数据包来传递的。 抓包&#xff08;packet capture&#xff09;&#xff1a;通过工具拦截客户端与服务器交互的数据包。 抓包后可以修改数据包的内容 2.为什么要抓包&…
阅读更多...
【鸿蒙 HarmonyOS】尺寸设置：size/layoutWeight/constraintSize

【鸿蒙 HarmonyOS】尺寸设置：size/layoutWeight/constraintSize

一、背景 常见尺寸&#xff1a;width&#xff08;宽度&#xff09;、height&#xff08;高度&#xff09;、padding&#xff08;内边距&#xff09;、margin&#xff08;外边距&#xff09; 主要整理下size&#xff08;设置高宽尺寸&#xff09;、layoutWeight&#xff08;对…
阅读更多...
最新文章

Copyright @ 2022~2023