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
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;

		//默认成员函数
		vector();                                           //构造函数
		vector(size_t n, const T& val);                     //构造函数
		template<class InputIterator>
		vector(InputIterator first, InputIterator last);    //构造函数
		vector(const vector<T>& v);                         //拷贝构造函数
		vector<T>& operator=(const vector<T>& v);           //赋值重载
		~vector();                                          //析构函数

		//迭代器相关函数
		iterator begin();
		iterator end();
		const_iterator begin()const;
		const_iterator end()const;

		//容量相关函数
		size_t size()const;
		size_t capacity()const;
		void reserve(size_t n);
		void resize(size_t n, const T& val = T());
		bool empty()const;

		//修改容器相关函数
		void push_back(const T& x);
		void pop_back();
		void insert(iterator pos, const T& x);
		iterator erase(iterator pos);
		void swap(vector<T>& v);

		//访问容器相关函数
		T& operator[](size_t i);
		const T& operator[](size_t i)const;

	private:
		iterator _start;        //指向容器的头
		iterator _finish;       //指向有效数据的尾
		iterator _endofstorage; //指向容器的尾
	};
}

默认成员函数

构造函数

1、无参构造,将所有成员变量初始化为空指针即可

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

2、构造一个含有n个值为val的vector容器。

先将容器容量扩大到n,再尾插val

vector(size_t n, const T& val)
	:_start(nullptr)
	, _finish(nullptr)
	, _endofstorage(nullptr)
{
	reserve(n); //扩容
	for (size_t i = 0; i < n; i++) //尾插
	{
		push_back(val);
	}
}

3、利用迭代器区间进行构造

因为迭代器区间可以是其他迭代器区间,所以我们要重新定义一块模板,再将迭代器中的数据尾插

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

拷贝构造

传统写法

先将容器容量扩大到n,再尾插原vector类中的数据(这里扩容和尾插调整了容器尾指针和数据尾指针,我们不必再次调整)

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

现代写法

利用迭代器构造一份vector类,再交换该类和拷贝构造的类

		vector(const vector<T>& v)
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			vector<T> tmp(v.begin(), v.end());
			swap(tmp);
		}

赋值重载

传统写法

先初始化原来vector类的空间,再将数据拷贝过来

vector<T>& operator=(const vector<T>& v)
{
	if (this != &v)
	{
		delete[] _start;
		_start = _finish = _endofstorage = nullptr;

		reserve(v.capacity());
		for (const auto& e : v)
		{
			push_back(e);
		}
	}
	return *this;
}

现代写法

现代写法极为巧妙,利用传值的特性(出了函数立即销毁)传入vector类,再交换该类和拷贝构造的类达到赋值的效果

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

析构函数

释放开辟存储数据的空间,再将容器的各个成员变量置为空

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

迭代器相关函数

vector当中的迭代器实际上就是容器当中所存储数据类型的指针。

typedef T* iterator;
typedef const T* const_iterator;

begin和end

vector当中的begin函数返回容器的首地址,end函数返回容器当中有效数据的下一个数据的地址。

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

我们还需写一份const版本,const版本只能读不能写,防止vector中数据被修改

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

容量相关函数

size和capacity

size表示vector容器中已存储有效数据个数而capacity表示vector容器的最大容量,那如何得出该组数据呢?

我们知道vector成员函数_start,_finish,_endofstorage是指针,而指针减指针得到两个指针间的数据个数,我们可以用_finish-_start得到size,用_endofstorage-_start得到capacity

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

reserve

当n大于当前的capacity时,将capacity扩大到n或大于n。

当n小于当前capacity时什么也不做。

void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t sz = size(); // 记录原容器中数据个数
		T* tmp = new T[n]; // 开辟一块容量为n的空间
		if (_start) //判空
		{
			for (size_t i = 0; i < sz; i++) // 拷贝数据
			{
				tmp[i] = _start[i];
			}
			delete[] _start; // 释放原容器中的数据
		}
		_start = tmp; // 调整指针
		_finish = _start + sz;
		_endofstorage = _start + n;
	}
}

注意:这里拷贝数据不能用memcpy。当我们拷贝的是一些简单的常量时是没有问题的,但是当我们拷贝的是另一个类,如string类时,拷贝的string还是指向原来string类指向的空间。当原来string被释放时,原string类指向的空间也被释放,此时拷贝的string类指向的是一块已被释放的空间,程序结束时它将再次被释放,释放一块已被释放的空间程序报错。

resize

当n大于当前的size时,将size扩大到n,扩大的数据为val,若val未给出,则默认为容器所存储类型的默认构造函数所构造出来的值。

当n小于当前的size时,将size缩小到n。

void resize(size_t n, const T& val = T())
{
	if (n <= size())// 当n小于当前的size时
	{
		_finish = n + _start;// 将size缩小到n
	}
	else // 当n大于当前的size时
	{
		if (n > capacity())// 当n大于容量时,扩容
		{
			reserve(n);
		}

		while (_finish < _start + n)// 给size到容器结尾赋值
		{
			*_finish = val;
			_finish++;
		}
	}
}

这里用了匿名对象T()来作为缺省参数

empty

通过比较_start和_finish指针来判断容器是否为空

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

修改容器相关函数

push_back

先判断容器是否已满,如果满了先扩容再尾插,如果没满,直接尾插

void push_back(const T& x)
{
	if (_finish == _endofstorage)// 判断是否需要扩容
	{
		size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newcapacity);
	}
	// 尾插数据
	*_finish = x;
	_finish++;
}

pop_back

先判空处理,再–_finish

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

insert

功能:利用迭代器再指定位置插入数据。

实现方式:插入前判断是否需要扩容,再将指定位置后的数据往后挪动一位,把数据插入指定位置。

iterator insert(iterator pos, const T& x)
{
	assert(pos >= _start&&pos <= _finish);// 判断传入数据的合法性
	if (_finish == _endofstorage)// 扩容
	{
		size_t len = pos - _start;// 记录pos的位置
		size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newcapacity);
		pos = _start + len;
	}
	iterator end = _finish - 1;
	while (end >= pos)// 挪动数据
	{
		*(end + 1) = *end;
		--end;
	}
	*pos = x;// 插入数据
	_finish++;
	return pos;
}

注意:扩容时要记录pos和_start的相对位置,避免扩容后迭代器失效问题

erase

功能:删除指定位置数据。

实现方式:先判断传入数据的合法性,在将pos位置后的数据全部往前挪动一位,覆盖掉原pos位置的数据

iterator erase(iterator pos)
{
	assert(pos >= _start&&pos < _finish);// 判断传入数据的合法性
	iterator it = pos + 1;// 利用迭代器记录pos的后一位
	while (it != _finish)// 将pos后的数据往前挪动一位
	{
		*(it - 1) = *it;
		it++;
	}
	_finish--;

	return pos;
}

swap

功能:交换两个vector中的数据

实现方式:利用库函数中的swap进行交换

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

访问容器相关函数

operator[ ]

为了方便访问数据vector中也加入了“下标+[ ]”操作

T& operator[](size_t i)// 可读可写
{
	assert(i < size());
	return _start[i];
}

const T& operator[](size_t i) const// 只能读
{
	assert(i<size());
	return _start[i];
}

总结

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

(0)

相关推荐

  • C++ STL vector的模拟实现

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

  • c++ vector模拟实现代码

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

  • 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类的模拟实现方法

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

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

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

  • 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

  • AngularJS中使用three.js的实例详解

    AngularJS中使用three.js的实例详解 一.轨迹球的引入问题 一开始我是用下面的方式引如轨迹球,但是会报Trackballcontrols is undefined的错. import * as THREE from 'three'; import * as Trackballcontrols from 'three'; 但其实我是能够在node_module下的threejs的包中找到Trackballcontrols的文件的,我一开始以为是引用的路径没对然后修改路径到对应包下Tr

  • java中构造器内部调用构造器实例详解

    可能为一个类写了多个构造器,有时可能想在一个构造器里面调用另外一个构造器,为了减少代码的重复,可用this关键字做到这一点. public class Flower { private String string; private int age; public Flower() { // 先调用public Flower(String string, int age) this("leon", 120); // 先调用public Flower(String string, int

  • C++ 中const修饰虚函数实例详解

    C++ 中const修饰虚函数实例详解 [1]程序1 #include <iostream> using namespace std; class Base { public: virtual void print() const = 0; }; class Test : public Base { public: void print(); }; void Test::print() { cout << "Test::print()" << end

  • IOS 中CALayer绘制图片的实例详解

    IOS 中CALayer绘制图片的实例详解 CALayer渲染内容图层.与UIImageView相比,不具有事件响应功能,且UIImageView是管理内容. 注意事项:如何使用delegate对象执行代理方法进行绘制,切记需要将delegate设置为nil,否则会导致异常crash. CALayer绘制图片与线条效果图: 代码示例: CGPoint position = CGPointMake(160.0, 200.0); CGRect bounds = CGRectMake(0.0, 0.0

  • vue中v-model动态生成的实例详解

    vue中v-model动态生成的实例详解 前言: 最近在做公司的项目中,有这么一个需求,每一行有一个input和一个select,其中行数是根据服务器返回的json数据动态变化的.那么问题来了,我们要怎样动态生成v-model? 现在项目做完了就整理了一下,直接贴代码了. <!DOCTYPE html> <html> <head> <meta charset="UTF-8"> <title></title> <

  • Linux 中常用的Rpm命令实例详解

    rpm命令是RPM软件包的管理工具.rpm原本是Red Hat Linux发行版专门用来管理Linux各项套件的程序,由于它遵循GPL规则且功能强大方便,因而广受欢迎.逐渐受到其他发行版的采用.RPM套件管理方式的出现,让Linux易于安装,升级,间接提升了Linux的适用度. 语法 rpm(选项)(参数) 选项 -a:查询所有套件: -b<完成阶段><套件档>+或-t <完成阶段><套件档>+:设置包装套件的完成阶段,并指定套件档的文件名称: -c:只列出

  • Linux 中fork的执行的实例详解

    Linux 中fork的执行的实例详解 先看看一段fork的程序 int main() { pid_t pid; 语句 a; pid = fork(); 语句 b; } 1.当程序运行到 pid = fork()时,这个进程马上分裂(fork的中文意思)成两个进程,我们称为父进程和子进程,子进程是父进程的副本,副本的意思是子进程把父进程的数据空间,堆和栈都复制一遍给自己用,这要求在内存给子进程分配和父进程同样大的存储空间,这样,父,子进程拥有相同的数据,但不会共享存储空间,他们只是共享正文段.

  • java 中HttpClient传输xml字符串实例详解

    java 中HttpClient传输xml字符串实例详解 介绍:我现在有一个对象page,需要将page对象转换为xml格式并以binary方式传输到服务端 其中涉及到的技术点有: 1.对象转xml流 2.输出流转输入流 3.httpClient发送二进制流数据 POM文件依赖配置 <dependencies> <dependency> <groupId>junit</groupId> <artifactId>junit</artifact

  • java 中模式匹配算法-KMP算法实例详解

    java 中模式匹配算法-KMP算法实例详解 朴素模式匹配算法的最大问题就是太低效了.于是三位前辈发表了一种KMP算法,其中三个字母分别是这三个人名的首字母大写. 简单的说,KMP算法的对于主串的当前位置不回溯.也就是说,如果主串某次比较时,当前下标为i,i之前的字符和子串对应的字符匹配,那么不要再像朴素算法那样将主串的下标回溯,比如主串为"abcababcabcabcabcabc",子串为"abcabx".第一次匹配的时候,主串1,2,3,4,5字符都和子串相应的

随机推荐