C++模拟如何实现vector

目录
  • 一、迭代器
    • 定义
    • 普通迭代器
    • const类型迭代器
  • 二、构造类
    • 构造函数
    • 拷贝构造函数
    • 赋值运算符重载
    • 析构函数
  • 三、容量相关操作
    • size、capacity
    • empty
    • resize
    • reserve
  • 三、元素访问
    • [ ]重载
    • front
    • back
  • 四、修改类接口
    • push_back
    • pop_back
    • insert
    • erase
    • clear
    • swap
  • 五、成员变量
  • 总结

一、迭代器

定义

vector类型的迭代器就是原生态的指针,对T*进行重命名即可

typedef T* iterator;
typedef const T* const_iterator;

普通迭代器

iterator begin()
{
	return start;
}
iterator end()
{
	return finish;
}

const类型迭代器

const类型迭代器可以访问const成员变量

const iterator cbegin()const
{
	return start;
}
const iterator cend()const
{
	return finish;
}

二、构造类

构造函数

构造空对象

在初始化列表中对三个成员变量进行初始化

vector()
	:start(nullptr)
	, finish(nullptr)
	, endOfStorage(nullptr)
{}

n个T类型

开辟空间以后,对finish进行自增,在空间填充元素

vector(size_t n, const T& value = T())
	:start(new T[n])
	, finish(start)
	, endOfStorage(start + n)
{
	for (int i = 0; i < n; i++)
	{
		*finish++ = value;
	}
}

重载前一个构造函数,将第一个参数设置为int类型

vector(int n, const T& value = T())
	:start(new T[n])
	, finish(start)
	, endOfStorage(start + n)
{
	for (int i = 0; i < n; i++)
	{
		*finish++ = value;
	}
}

之所以要对这种类型的构造函数进行重载,是因为在调用构造函数时,如果实参传两个整型数字,编译器会默认为int类型数据,进行推演之后与前面的size_t类型不匹配,则会调用下面的区间构造的方法,导致程序报错,如图:

迭代器构造

将构造方法中迭代器的类型写成模板类型,这样便可以接收其它类型的迭代器,如:T类型为char,Iterator迭代器为string类型,便可以从字符串中截取字符,构造vector<char>类型的对象。

//写成函数模板,可以接受任意类型的迭代器
template<typename Iterator>
vector(Iterator first, Iterator last)
{
	size_t n = ZH::distance(first, last);//获取长度
	start = new T[n];
	finish = start;
	endOfStorage = start + n;
	while (first != last){
		*finish = *first;
		first++;
		finish++;//完成赋值的同时也移动了finish的位置
	}
}

将distance方法写到另一个.hpp头文件中

template<typename Iterator>
//此处的Iterator是模板参数,表示可以传任意类型的迭代器
size_t distance(Iterator first, Iterator last)
{
	//获取元素个数,暂时只考虑底层空间连续的情况
	int count = 0;
	while (first != last)
	{
		first++;
		count++;
	}
	return count;
}

拷贝构造函数

拷贝构造函数的形参必须是const类对象的引用,必须使用const类型的迭代器才能访问,复用迭代器构造的方法定义一个临时变量temp,交换temp与当前对象

//此处拷贝构造函数的形参是const类型
vector(const vector<T>& v)
	:start(nullptr)
	, finish(nullptr)
	, endOfStorage(nullptr)
{
	//▲用const类型的迭代器访问const变量
	vector<T> temp(v.cbegin(), v.cend());
	this->swap(temp);
}

赋值运算符重载

形参设置为类类型对象,调用赋值运算符重载函数时,形参会拷贝实参,交换当前对象与形参的值。

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

析构函数

释放空间,将三个迭代器赋值为空

~vector()
{
	delete[]start;
	start = nullptr;
	finish = nullptr;
	endOfStorage = nullptr;
}

三、容量相关操作

size、capacity

size_t size()
{
	return finish - start;
}
size_t capacity()
{
	return endOfStorage - start;
}

empty

判断fiinsh与start是否相等即可,相等则为空

size_t empty()
{
	return finish == start;
}

resize

定义一个变量保存旧的size的值‘判断是减小还是增加size;判断是否需要扩容,需要则调用reserve函数,从旧空间的结束位置开始,给新增加的空间填充元素;最后改变finish的值。

void resize(size_t newsize, const T& value = T())
{
	size_t oldsize = size();
	if (newsize > oldsize){
		if (newsize > capacity()){
			reserve(newsize);
		}
		for (size_t i = oldsize; i < newsize; i++)
		{
			start[i] = value;
		}
	}
	finish = start + newsize;//不用考虑增加或减小
}

reserve

reserve的步骤:申请新空间,拷贝旧空间的元素,释放旧的空间。

void reserve(size_t newcapacity)
{
	size_t oldcapacity = capacity();
	if (newcapacity > oldcapacity)
	{
		size_t n = size();//保存size()的值
		T* temp = new T[newcapacity];
		//start不为空时才进行拷贝旧空间元素和释放的操作
		if (start)
		{
			//memcpy浅拷贝,当vector中存放的对象内部设计资源管理
			// 会有内存泄漏和野指针问题
			//memcpy(temp, start, sizeof(T) * n);

			for (size_t i = 0; i < n; i++)
			{
				temp[i] = start[i];//调用赋值运算符重载
			}
			delete[] start;
		}
		start = temp;
		//▲此处不能用satart+size(),因为size方法中有finish-start,而start值已经改变
		finish = start + n;
		endOfStorage = start + newcapacity;
	}
}

▲易错点:

  • 判断start的值是否为空 ,如果原来的start为空,则不需要再拷贝元素和释放
  • 浅拷贝问题

finish更新问题

size()的方法内部finish-start,而此时start已经发生改变,finish还是旧的,所以要提前定义一个临时变量保存size()的值

三、元素访问

[ ]重载

重载成普通类型和const类型,const类型可以访问const成员

T& operator[](size_t index)
{
	assert(index < size());
	return start[index];
}

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

front

返回动态数组第一个元素

T& front()
{
	return start[0];
}
const T& front()const
{
	return start[0];
}

back

返回最后一个位置前一个元素

T& back()
{
	return *(finish - 1);
}
const T& back()const
{
	return *(finish - 1);
}

四、修改类接口

push_back

插入前先判断空间是否已满,空间若满则进行扩容,扩容时,要原来的空间容量为0的情况;将value放置到末尾位置,并将finish向后移动一个单位

void push_back(const T& value)
{
	if (finish == endOfStorage)
	{
		//因为原来的capacity可能为0,所以要+3
		reserve(capacity() * 2 + 3);
	}
	*finish++ = value;
}

pop_back

尾删,先判断对象是否为空,若不为空则将finish位置前移一个单位

void pop_back()
{
	if (empty())
	{
		return;
	}
	finish--;
}

insert

任意位置插入,insert的返回值为新插入的第一个元素位置的迭代器;因为插入可能会进行扩容,导致start的值改变,所以先定义一个变量保存pos与start的相对位置;判断是否需要扩容;从插入位置开始,将所有元素向后搬移一个位置;将pos位置的值置为要插入的值;更新finish的值。

//第二个参数用const修饰,常量引用
//不用const修饰则为非常量引用
iterator insert(iterator pos, const T& value)
{
	int index = pos - start;
	assert(pos >= start && pos < finish);
	//判断空间是否足够
	if (finish == endOfStorage)
	{
		reserve(capacity() * 2);
	}
	pos = start + index;
	for (auto it = finish; it > pos; it--)
	{
		*it = *(it - 1);
	}
	*pos = value;
	finish++;
	return pos;
}

erase

判断下标合法性;从pos位置下一个位置开始,将所有元素向前搬移一个位置;更新finish的值

iterator erase(iterator pos)
{
	assert(pos >= start && pos < finish);

	auto it = pos;
	while (it < finish - 1)
	{
		*it = *(it + 1);
		it++;
	}
	finish--;
	return pos;
}

clear

清空所有元素,令finish=start即可

void clear()
{
	finish = start;
}

swap

vector内置的swap函数,调用标准库中的swap交换vector的三个成员变量的值

void swap(vector<T>& v)
{
	std::swap(start, v.start);
	std::swap(finish, v.finish);
	std::swap(endOfStorage, v.endOfStorage);
}

五、成员变量

private:
	iterator start;
	iterator finish;
	iterator endOfStorage;

vector内部有三个成员变量,start表示起始位置,finish表示有效元素的末尾位置,endOfStorage表示空间的末尾位置;通过这三个成员变量可以得到size和capacity等值,如图:

总结

以上为个人经验,希望能给大家一个参考,也希望大家多多支持我们。

(0)

相关推荐

  • 详解C++ STL模拟实现vector

    目录 vector 概述 接口总览 默认成员函数 构造函数 析构函数 拷贝构造函数 复制赋值函数 vector 的迭代器 元素访问 operator[] back 容量相关函数 size capacity empty resize reserve 修改函数 insert push_back erase pop_back swap vector 概述 vector 的数据结构安排及操作方式,与原生数组十分相似,两者唯一的差别在于空间运用的灵活性.原生数组是静态空间,一旦配置了就不能改变大小:vec

  • C++模拟实现STL容器vector的示例代码

    目录 一.vector迭代器失效问题 二.模拟实现构造函数调用不明确 1.问题描述 2.解决调用不明确的方法 三.reserve中的深浅拷贝问题 1.reserve中浅拷贝发生原因 2.浅拷贝发生的图解 3.解决方法 四.模拟实现vector整体代码 一.vector迭代器失效问题 1.Visual Studio和g++对迭代器失效问题的表现 int main(){ std::vector<int>v{1,2,3,4}; std::vector<int>::iterator it

  • C++模拟实现vector的示例代码

    目录 一.迭代器 定义 普通迭代器 const类型迭代器 二.构造类 构造函数 拷贝构造函数 赋值运算符重载 析构函数 三.容量相关操作 size.capacity empty resize reserve 三.元素访问 [ ]重载 front back 四.修改类接口 push_back pop_back insert erase clear swap 五.成员变量 一.迭代器 定义 vector类型的迭代器就是原生态的指针,对T*进行重命名即可 typedef T* iterator; ty

  • 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

    目录 一.迭代器 定义 普通迭代器 const类型迭代器 二.构造类 构造函数 拷贝构造函数 赋值运算符重载 析构函数 三.容量相关操作 size.capacity empty resize reserve 三.元素访问 [ ]重载 front back 四.修改类接口 push_back pop_back insert erase clear swap 五.成员变量 总结 一.迭代器 定义 vector类型的迭代器就是原生态的指针,对T*进行重命名即可 typedef T* iterator;

  • C++模拟实现vector流程详解

    目录 模拟vector 总结 模拟vector 我们可以通过模板实现类似vector的类.我们实现一个StrVecTemp类,其内部通过allocator开辟空间,存储的类型用T来表示,T是模板类型. template <typename T> class StrVecTemp { public: StrVecTemp() : elements(nullptr), first_free(nullptr), cap(nullptr) {} //拷贝构造函数 StrVecTemp(const St

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

  • C语言数据结构之vector底层实现机制解析

    目录 一.vector底层实现机制刨析 二.vector的核心框架接口的模拟实现 1.vector的迭代器实现 2.reserve()扩容 3.尾插尾删(push_back(),pop_back()) 4.对insert()插入时迭代器失效刨析 5.对erase()数据删除时迭代器失效刨析 一.vector底层实现机制刨析 通过分析 vector 容器的源代码不难发现,它就是使用 3 个迭代器(可以理解成指针)来表示的: 其中statrt指向vector 容器对象的起始字节位置: finish指

  • Python中的特殊方法以及应用详解

    前言 Python 中的特殊方法主要是为了被解释器调用的,因此应该尽量使用 len(my_object) 而不是 my_object.__len__() 这种写法.在执行 len(my_object) 时,Python 解释器会自行调用 my_object 中实现的 __len__ 方法. 除非有大量的元编程存在,直接调用特殊方法的频率应远小于实现它们的次数. 模拟数值类型 可以通过在自定义对象中实现 __add__ 和 __mul__ 等特殊方法 ,令其支持 +.* 等运算符. 如下面的模拟向

  • C++ 容器适配器priority_queue的使用及实现代码

    优先级队列(Priority Queue) 队列是一种特征为FIFO的数据结构,每次从队列中取出的是最早加入队列中的元素.但是,许多应用需要另一种队列,每次从队列中取出的应是具有最高优先权的元素,这种队列就是优先级队列(Priority Queue),也称为优先权队列. 1. 优先级队列的概念 优先级队列的定义 优先级队列是不同于先进先出队列的另一种队列.每次从队列中取出的是具有最高优先权的元素. 优先级队列的特点 优先级队列是0个或多个元素的集合,每个元素都有一个优先权或值. 当给每个元素分配

  • C++深入探究重载重写覆盖的区别

    目录 基类实现 子类实现 函数调用 总结 资源链接 基类实现 我们先实现一个基类 class BaseTest { private: virtual void display() { cout << "Base display" << endl; } void say() { cout << "Base say()" << endl; } public: virtual void func() { cout <&

  • C++虚函数表与类的内存分布深入分析理解

    目录 不可定义为虚函数的函数 将析构函数定义为虚函数的作用 虚函数表原理 继承关系中虚函数表结构 多重继承的虚函数表 多态调用原理 对齐和补齐规则 为什么要有对齐和补齐 资源链接 不可定义为虚函数的函数 类的静态函数和构造函数不可以定义为虚函数: 静态函数的目的是通过类名+函数名访问类的static变量,或者通过对象调用staic函数实现对static成员变量的读写,要求内存中只有一份数据.而虚函数在子类中重写,并且通过多态机制实现动态调用,在内存中需要保存不同的重写版本. 构造函数的作用是构造

  • c++ vector模拟实现代码

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

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

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

随机推荐