c++ vector模拟实现的全过程

一、vector是什么?

vector是表示可变大小数组的序列容器,它也采用连续存储空间来存储元素,因此可以采用下标对vector的元素进行访问,它的大小是动态改变的,vector使用动态分配数组来存储它的元素;

二、容器特性

1.顺序序列

顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素;

2.动态数组

支持对序列中的任意元素进行快速直接访问,甚至可以通过指针进行该操作。操供了在序列末尾相对快速地添加/删除元素的操作;

3.能够感知内存分配器的

容器使用一个内存分配器对象来动态地处理它的存储需求;

三、vector的模拟实现

定义一个类:

template<class T>
class Vector
{
    T* _start; //首元素地址
    T* _finish; //最后一个元素地址的下一个地址
    T* _endOfStorage; //空间的尾地址
public:
//成员函数
};

构造函数

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

Vector(size_t n, const T& value = T())
    :_start(nullptr)
    , _finish(nullptr)
    , _endOfStorage(nullptr)
{
    reserve(n);
    while (n--)
    {
        push_back(value);
    }
}
Vector(InputInterator first, InputInterator last)
        :_start(nullptr)
        , _finish(nullptr)
        , _endOfStorage(nullptr)
    {
        while (first != last)
        {
            pushBack(*first);
            ++first;
        }
    }

数据大小、空间大小

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

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

尾插

void pushBack(const T& value)
    {
        if (_finish == _endOfStorage)
        {
            size_t newC = _endOfStorage == nullptr ? 1 : 2 * capacity();
            reverse(value);
        }
        *_finish = value;
        ++_finish;
    }

扩容

有资源进行拷贝时,使用深拷贝;类型为自定义类型时,发生浅拷贝,调用自定义类型析构函数,释放资源,导致资源二次释放,所以自定义类型的拷贝有资源时进行深拷贝;

深拷贝与浅拷贝的区别及应用

void reserve(size_t n)
{
if (n &gt; capacity())
{
size_t sz = size();
T* arr = new T[n];
if (_start)
{
memcpy(arr, _start, sizeof(T) * sz);
delete[] _start;
}
//update
_start = arr;
_finish = _start + sz;
_endOfStorage = _start + n;
}
}

改变数据大小

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

位置插入值

void insert(iterator pos, const T& val)
    {
        size_t sz = pos - _start;
        //检查位置
        if (pos >= _start && pos <= _finish)
        {
            //检查容量
            if (_finish == _endOfStoage)
            {
                size_t n = _endOfStorage == nullptr ? 1 : 2 * capacity();
                reserve(n);
                //更新迭代器
                pos = _start + sz;
            }
            //移动元素
            iterator end_u = _finish;
            while (end_u != pos)
            {
                *end = *(end_u - 1);
                --end_u();
            }
            //插入元素
            *pos = val;
            //更新位置
            ++_finish;
        }
    }

删除数据

iterator erase(iterator pos)
    {
        //检查位置
        if (pos < _finish && pos >= _start)
        {
            //移动元素
            iterator start = pos + 1;
            while (start!=_finish)
            {
                *(start - 1) = *start;
                start++;
            }
            //更新
            --_finish;
        }
        return pos;
    }
    //返回删除数据的下一个元素的位置

operator[] 重载

T& operator[](size_t pos)
    {
        if (pos >= 0 && pos < size())
            return _start[pos];
    }

operator= 重载

    Vector<T>& operator=(const Vector<T>& v)
    {
        if (this != &v)
        {
            delete[]_start;
            size_t n = v.capacity();
            _start = new T[n];
            for (size_t i = 0; i < v.capacity(); ++i)
            {
                _start[i] = v._start[i];
            }
            _finish = _start + v.size();
            _finish = _start + n;
        }
        return *this;
    }

迭代器

//vector迭代器:T*
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;
}

析构函数

~Vector()
{
    if (_start)
    {
        delete[] _start;
        _start = _finish = _endOfStorage = nullptr;
    }
}

总结

到此这篇关于c++ vector模拟实现的文章就介绍到这了,更多相关c++ vector模拟实现内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • c++中vector的使用和模拟实现

    一.接口介绍 1.插入数据 void push_back(const T& x) 在当前vector尾部插入x,如果容量不够扩大二倍. iterator insert(iterator pos, const T& x) 在POS位置插入元素x 2.容量相关 size_t capacity() 返回当前vector的容量(size+剩余容量) size_t size() 返回当前vector的元素个数 void resize(size_t n, const T& val = T())

  • C++ vector容器 find erase的使用操作:查找并删除指定元素

    概念:容器.迭代器.算法 STL包括容器.迭代器和算法: 容器 用于管理一些相关的数据类型.每种容器都有它的优缺点,不同的容器反映出程序设计的不同需求.容器自身可能由数组或链表实现,或者容器中的每个元素都有特殊的关键值. 迭代器 用于遍历一个数据集中的每个元素.这些数据集可能是容器或者容器的子集.迭代器的主要优点是它们为任意类型的容器提供一个小巧并且通用(注意通用很重要)的接口.例如,迭代器接口的一个操作是让它依次遍历数据集的每个元素.这个操作是依赖容器的内总部结构独立完成的.迭代器之所以有效是

  • C++ vector扩容解析noexcept应用场景

    c++11提供了关键字noexcept,用来指明某个函数无法--或不打算--抛出异常: void foo() noexcept; // a function specified as will never throw void foo2() noexcept(true); // same as foo void bar(); // a function might throw exception void bar2() noexcept(false); // same as bar 所以我们需要

  • C++中vector操作方式详解(多种方式)

    1. vector: 1.1 vector 说明 vector是向量类型,可以容纳许多类型的数据,因此也被称为容器 (可以理解为动态数组,是封装好了的类) 进行vector操作前应添加头文件#include <vector> 1.2 vector初始化: 方式1. //定义具有10个整型元素的向量(尖括号为元素类型名,它可以是任何合法的数据类型),不具有初值,其值不确定 vector<int>a(10); 方式2. //定义具有10个整型元素的向量,且给出的每个元素初值为1 vec

  • C++ vector类的模拟实现方法

    vector和string虽然底层都是通过顺序表来实现的,但是他们利用顺序表的方式不同,string是指定好了类型,通过使用顺序表来存储并对数据进行操作,而vector是利用了C++中的泛型模板,可以存储任何类型的数据,并且在vector中,并没有什么有效字符和容量大小的说法,底层都是通过迭代器进行操作的,迭代器底层实现也就是指针,所以说,vector是利用指针对任何顺序表进行操作的. vector属性 _start用于指向第一个有效元素 _finish用于指向最后一个有效元素的下一个位置 _e

  • 详解C++ STL vector容器访问元素的几种方式

    学会如何创建并初始化 vector 容器之后,本节继续来学习如何获取(甚至修改)容器中存储的元素. 访问vector容器中单个元素 首先,vector 容器可以向普通数组那样访问存储的元素,甚至对指定下标处的元素进行修改,比如: #include <iostream> #include <vector> using namespace std; int main() { vector<int> values{1,2,3,4,5}; //获取容器中首个元素 cout &l

  • 详解C++ STL vector容量(capacity)和大小(size)的区别

    很多初学者分不清楚 vector 容器的容量(capacity)和大小(size)之间的区别,甚至有人认为它们表达的是一个意思.本节将对 vector 容量和大小各自的含义做一个详细的介绍. vector 容器的容量(用 capacity 表示),指的是在不分配更多内存的情况下,容器可以保存的最多元素个数:而 vector 容器的大小(用 size 表示),指的是它实际所包含的元素个数. 对于一个 vector 对象来说,通过该模板类提供的 capacity() 成员函数,可以获得当前容器的容量

  • c++ vector对象相关总结

    下面随笔讲解c++ vector对象. vector对象 为什么需要vector? 封装任何类型的动态数组,自动创建和删除. 数组下标越界检查. 封装的如ArrayOfPoints也提供了类似功能,但只适用于一种类型的数组. vector对象的定义 vector<元素类型> 数组对象名(数组长度); 例: vector<int> arr(5) 建立大小为5的int数组 vector对象的使用 对数组元素的引用 与普通数组具有相同形式: vector对象名 [ 下标表达式 ] vec

  • c++ vector模拟实现的全过程

    一.vector是什么? vector是表示可变大小数组的序列容器,它也采用连续存储空间来存储元素,因此可以采用下标对vector的元素进行访问,它的大小是动态改变的,vector使用动态分配数组来存储它的元素: 二.容器特性 1.顺序序列 顺序容器中的元素按照严格的线性顺序排序.可以通过元素在序列中的位置访问对应的元素; 2.动态数组 支持对序列中的任意元素进行快速直接访问,甚至可以通过指针进行该操作.操供了在序列末尾相对快速地添加/删除元素的操作; 3.能够感知内存分配器的 容器使用一个内存

  • c++ vector模拟实现代码

    vector的介绍 1.vector是表示可变大小数组的序列容器. 2.就像数组一样,vector也采用的连续存储空间来存储元素.也就是意味着可以采用下标对vector的元素进行访问,和数组一样高效.但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自动处理. 3.本质讲,vector使用动态分配数组来存储它的元素.当新元素插入时候,这个数组需要被重新分配大小为了增加存储空间.其做法是,分配一个新的数组,然后将全部元素移到这个数组.就时间而言,这是一个相对代价高的任务,因为每当一个新

  • C++中vector的模拟实现实例详解

    目录 vector接口总览 默认成员函数 构造函数 拷贝构造 赋值重载 析构函数 迭代器相关函数 begin和end 容量相关函数 size和capacity reserve resize empty 修改容器相关函数 push_back pop_back insert erase swap 访问容器相关函数 operator[ ] 总结 vector接口总览 namespace nzb { //模拟实现vector template<class T> class vector { publi

  • C++  STL _ Vector使用及模拟实现

    目录 1.Vector的介绍 1.1 Vector的介绍 2.Vector的使用 2.1 vector的定义 2.2 vector 迭代器的使用 2.3 vector的空间增长问题 3. vector的增删查改 3.1 push_back (重点) 3.2 pop_back (重点) 3.3 insert 3.4 erase 3.5 operator [ ] 1.Vector的介绍 1.1 Vector的介绍 ​ ​vector官方文档介绍​​ 1.vector是表示可变大小数组的序列容器. 2

  • 详解C++中vector的理解以及模拟实现

    目录 vector介绍 vector常见函数介绍 vector模拟实现及迭代器失效讲解 vector介绍 vector文档 1.vector是表示可变大小数组的序列容器. 2.就像数组一样,vector也采用的连续存储空间来存储元素.也就是意味着可以采用下标对vector的元素进行访问,和数组一样高效.但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自动处理. 3.本质讲,vector使用动态分配数组来存储它的元素.当新元素插入时候,这个数组需要被重新分配大小为了增加存储空间.其做

  • C++模拟实现vector示例代码图文讲解

    目录 vector的模拟实现 使用memcpy拷贝问题 vector的模拟实现 #include <iostream> using namespace std; #include <assert.h> namespace myVector { template<class T> class vector { public: // Vector的迭代器是一个原生指针 typedef T* iterator; typedef const T* const_iterator;

  • java Socket实现简单模拟HTTP服务器

    最近复习计算机网络,复习完应用层之后对于理论知识还是没有一个深刻的概念,索性就动手用Java Socket API 模拟做一个HTTP服务器,巩固一下应用层的知识. HTTP基于TCP协议,协议采用了请求/响应模型.客户端向服务器发送一个请求,请求头包含请求的方法.URL.协议版本.以及包含请求修饰符.客户信息和内容的类似于MIME的消息结构.服务器以一个状态行作为响应,响应的内容包括消息协议的版本,成功或者错误编码加上包含服务器信息.实体元信息以及可能的实体内容--百度百科. 话不多说,还是直

  • 浅析Golang切片截取功能与C++的vector区别

    目录 1. 引言 2.分析过程 2.1 s[:]的方式截取元素 2.2 append的方式截取元素 3. 结论 浅析golang切片截取(删除)功能 1. 引言 golang的切片被认为是和C++的vector容器类似,都可以认为是动态数组,但又不完全一样. 那么区别到底在哪里呢?对元素的删除方式是很重要的一点区别 对于C++的vector来说,用erase函数来删除元素,其原理是将当前位置后面的元素都向前移动一位,删除一个元素的平均时间复杂度为O(n) 对于golang的slice来说,没有用

随机推荐