首页 > 编程语言 >【C++】vector的模拟实现

【C++】vector的模拟实现

时间:2024-09-08 11:24:54浏览次数:12  
标签:finish const pos C++ start vector 模拟 size

文章目录

一、前言

如何去模拟实现?我们可以看看vector的源码,抽离出底层结构:

template <class T, class Alloc = alloc>
class vector {
     typedef T value_type;
     typedef value_type* iterator;
     typedef const value_type* const_iterator;
protected:
    iterator start;
    iterator finish;
    iterator end_of_storage;
}

这本质上与 T* a , size_t size, size_t capacity 是类似的:
在这里插入图片描述
其中

size = _finish - _start
capacity = _endofstorage - _start

二、构造函数

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

// 类模板的成员函数,还可以继续是函数模版
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

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

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

模拟实现构造函数调用不明确

不知道大家注意到没有,上面为啥重载了两个 vector(size_t n, const T& val = T()) vector(int n, const T& val = T())?

1.问题描述

vector(size_t n, const T& val = T())//这里的形参用size_t就会引发这两个构造函数调用问题
    :_start(nullptr)
    , _finish(nullptr)
    , _end_of_storage(nullptr)
{
    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)
    , _end_of_storage(nullptr)
{
    while (first != last)
    {
        push_back(*first++);
    }
}

在这里插入图片描述

这里本意是想使用第一种构造方式,用3个6进行构造。编译器会根据形参调用最匹配的函数重载。

第一个构造函数的第一个形参是size_t,形参去匹配的话需要发生隐式类型转换。

但是这两个参数更匹配第二个构造函数(因为第二个模板可以为int,完全匹配),一旦走第二个构造函数,该构造函数内部是要对first进行解引用操作,所以编译器会报非法的间接寻址(解引用)错误。

2、解决调用不明确的方法

针对构造函数vector(size_t n, const T& val = T()),我们多重载一个vector(int n, const T& val = T())版本的构造函数即可解决该问题。

三、基础接口

1.empty和clear

empty

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

clear

void clear()
{
    _finish = _start;//这里可不是置为nullptr哦
}

2.size和capacity

size

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

capacity

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

3.[]和iterator

[]

提供const版本和非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

同理普通迭代器和const迭代器版本,同理,范围for循环此时也是可以实现的:

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

四、resize和reserve

resize

n个数据去初始化,这个n是多大,会造成什么影响?我们需要进行分类讨论:
在这里插入图片描述

void resize(size_t n, const T& val = T())//val给T类型的缺省值
		{
			if (n > capacity())//n大于capacity,要扩容
			{
				reserve(n);
				while (_finish < _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
			else if (n > size())//n小于capacity但大于原size
			{
				while (_finish < _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
			else//缩size的情况
			{
				_finish = _start + n;
			}
		}

resize的参数初始化值为T类型的构造,这里可不能直接初始化为0,要是T是自定义类型呢?是vector呢?所以这里如果T是vector的化调用的就是vector的构造函数。另外,这里还需要注意的一点是:构造vector的时候是匿名对象,匿名对象具有常性,不可修改所以要加上const修饰

所以,我们自然而然可以知道,对于内置类型比如int,都是有构造函数的。

reserve

reserve最大的问题就是深拷贝!开辟新空间进行赋值的时候如果直接使用memcpy是浅拷贝。

void reserve(size_t n)
{
    if (n > capacity())
    {
        T* tmp = new T[n];
        //size()需要先保存起来,后面_start会发生改变
		size_t sz = size();
        //为空不需要拷贝了
        if (_start)
        {
            for (size_t i = 0; i < sz; i++)
            {
                tmp[i] = _start[i];
            }
            delete[] _start;
            //memcpy(tmp, _start, sizeof(T) * size());//浅拷贝
            //delete[] _start;
        }
        _start = tmp;
        _finish = _start+sz;
        _endofstorage = _start + n;
    }
}

reserve中的深浅拷贝问题

1、reserve中浅拷贝发生原因

在这里插入图片描述
这句memcpy表面上把原来的数据全部拷贝到tmp里面了,但是,这只是按字节的拷贝,如果当前类型为vector<vector>等涉及深浅拷贝类型,将会发生浅拷贝。

2、浅拷贝发生的图解

在这里插入图片描述
在这里插入图片描述
memcpy会把vector<vector>,从_start位置开始,按字节进行拷贝。如图所示,拷贝的对象是4个vector,这是一种浅拷贝!

3、解决方法

void reserve(size_t n)
{
    //扩容
    if (n > capacity())
    {
        size_t oldSize = size();//先记录下size,后续解决finish失效
        T* tmp = new T[n];
        if (_start != nullptr)
        {
            //memcpy(tmp, _start, sizeof(T) * oldSize);//浅拷贝
            for (size_t i = 0; i < oldSize; ++i)
            {
                tmp[i] = _start[i];//调用赋值运算符重载完成深拷贝
            }
            delete[] _start;
        }
        _start = tmp;
        _finish = _start + oldSize;//异地扩容后_finish失效,需重新设定_finish
        _end_of_storage = _start + n;
    }
}

借助赋值运算符重载,完成深拷贝。

五、尾插尾删

void push_back(const T& x)
{
    if (_finish == _endofstorage)
    {
        size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
        reserve(newCapacity);
    }
    *_finish = x;
    ++_finish;
}


void pop_back()
{
    assert(_finish > _start);
    --_finish;
}

六、vector迭代器失效问题

1.insert

//迭代器失效:扩容引起野指针问题
void insert(iterator pos, const T& val)
{
    assert(pos >= _start);
    assert(pos <= _finish);
    if (_finish == _endofstorage)
    {
        size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
        reserve(newCapacity);
    }
    iterator end = _finish - 1;
    while (end >= pos)
    {
        *(end + 1) = *end;
        --end;
    }
    *pos = val;
    ++_finish;
}

测试代码:

void Test3()
{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);

		for (size_t i = 0; i < v.size(); i++)
		{
			cout << v[i] << " ";
		}
		cout << endl;
		vector<int>::iterator it = find(v.begin(), v.end(), 3);
		if (it != v.end())
		{
			v.insert(it, 30);
		}
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
}

在这里插入图片描述
这是因为扩容导致pos失效了:
在这里插入图片描述
insert过程中发生扩容,导致it指向的空间实际上已经被释放,it指向已被释放的空间是野指针,造成了迭代器失效

所以,我们应该去更新pos,算出pos刚开始的相对位置,然后再去进行更新即可解决问题。但是此时外面调用insert的it仍然是失效的,因为是传值调用,形参改变不影响实参,可以通过返回值接收解决问题。(如果是传引用的话,只能传变量,而临时对象具有常性,不能调用,存在很多问题),所以直接用返回值解决。

iterator insert(iterator pos, const T& val)
{
    assert(pos >= _start);
	assert(pos <= _finish);
    if (_finish == _endofstorage)
    {
        //扩容会导致pos迭代器失效,需要更新
        size_t len = pos - _start;
        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 = val;
    ++_finish;
    return pos;
}

void Test3()
{
    vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	for (size_t i = 0; i < v.size(); i++)
    {
        cout << v[i] << " ";
    }
    cout << endl;
    v.insert(v.begin(), 0);
    vector<int>::iterator it = find(v.begin(), v.end(), 3);
    if (it != v.end())
    {
        v.insert(it, 30);
    }
    for (auto e : v)
    {
        cout << e << " ";
    }
    cout << endl;
}

2.erase
挪动数据进行覆盖即可

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

erase的pos也可能会导致pos失效,测试代码:

void Test6()
	{
		//删除所有偶数
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		vector<int>::iterator it = v.begin();
		while (it != v.end())
		{
			if (*it % 2 == 0)
			{
				v.erase(it);
			}
			++it;
		}
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}

上述代码在VS下,当erase(it)之后,it指向的位置发生改变,然后在++it的话,会出现问题,出现一些错误,造成迭代器失效。

我们最好统一认为失效了。

正确的erase:

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

测试代码:

void Test6()
	{
		//删除所有偶数
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		vector<int>::iterator it = v.begin();
		while (it != v.end())
		{
			if (*it % 2 == 0)
			{
				it = v.erase(it);
			}
			else
			{
				++it;
			}
		}
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}

对于insert和erase存在迭代器失效的问题,当迭代器失效而来,我们就不要再去访问pos的位置了,要更新pos的位置,可通过返回值接收进行访问。

七、模拟实现vector整体代码

namespace fx
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;


		vector() = default;

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

		// 类模板的成员函数,还可以继续是函数模版
		template <class InputIterator>
		vector(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

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

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

		void clear()
		{
			_finish = _start;
		}

		// v1 = v3
		/*vector<T>& operator=(const vector<T>& v)
		{
			if (this != &v)
			{
				clear();

				reserve(v.size());
				for (auto& e : v)
				{
					push_back(e);
				}
			}

			return *this;
		}*/

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

		// v1 = v3
		//vector& operator=(vector v)
		vector<T>& operator=(vector<T> v)
		{
			swap(v);

			return *this;
		}

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

		iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		const_iterator begin() const
		{
			return _start;
		}

		const_iterator end() const
		{
			return _finish;
		}

		void reserve(size_t n);


		void resize(size_t n, T val = T())
		{
			if (n < size())
			{
				_finish = _start + n;
			}
			else
			{
				reserve(n);
				while (_finish < _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
		}

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

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

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

		void push_back(const T& x)
		{
			// 扩容
			if (_finish == _end_of_storage)
			{
				reserve(capacity() == 0 ? 4 : capacity() * 2);
			}

			*_finish = x;
			++_finish;
		}

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

		iterator insert(iterator pos, const T& x)
		{
			assert(pos >= _start);
			assert(pos <= _finish);

			// 扩容
			if (_finish == _end_of_storage)
			{
				size_t len = pos - _start;
				reserve(capacity() == 0 ? 4 : capacity() * 2);
				pos = _start + len;
			}

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

			++_finish;

			return pos;
		}

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

			iterator it = pos + 1;
			while (it != end())
			{
				*(it - 1) = *it;
				++it;
			}

			--_finish;
		}

		T& operator[](size_t i)
		{
			assert(i < size());

			return _start[i];
		}

		const T& operator[](size_t i) const
		{
			assert(i < size());

			return _start[i];
		}

	private:
		iterator _start = nullptr;
		iterator _finish = nullptr;
		iterator _end_of_storage = nullptr;
	};
}

标签:finish,const,pos,C++,start,vector,模拟,size
From: https://blog.csdn.net/f_2789889770/article/details/142021603

相关文章

  • 【C++】简述STL——string类的使用
    文章目录一、STL的简述1.STL的框架2.STL版本二、string1、string的介绍2、为什么string类要实现为模板?三、string的构造接口四、string的容量相关的接口五、string对象修改相关的接口1、insert2.earse3、assign4、replace六、string对象字符串运算相关接口1、c_str2、......
  • 【洛谷 P1996】约瑟夫问题 题解(队列+模拟+循环)
    约瑟夫问题题目描述个人围成一圈,从第一个人开始报数,数到的人出列,再由下一个人重新从开始报数,数到的人再出圈,依次类推,直到所有的人都出圈,请输出依次出圈人的编号。注意:本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰名小朋友,而该题是全部出圈。输入......
  • C++内存管理
    内存是什么?内存就是计算机的存储空间,用于存储程序的指令、数据和状态。在C语言中,内存被组织成一系列的字节,每个字节都有一个唯一的地址。程序中的变量和数据结构存储在这些字节中。根据变量的类型和作用域,内存分为几个区域,如栈(stack)、堆(heap)和全局/静态存储区。内存编址计算......
  • C++ STL-deque容器入门详解
    1.1deque容器基本概念功能:双端数组,可以对头端进行插入删除操作deque与vector区别:vector对于头部的插入删除效率低,数据量越大,效率越低deque相对而言,对头部的插入删除速度回比vector快vector访问元素时的速度会比deque快,这和两者内部实现有关deque内部工作原理:deque内部......
  • C++ STL-Map容器从入门到精通详解
    1.简介Map也是一种关联容器,它是键—值对的集合,即它的存储都是以一对键和值进行存储的,Map通常也可以理解为关联数组(associativearray),就是每一个值都有一个键与之一一对应,因此,map也是不允许重复元素出现的。同时map也具备set的相关功能,其底层也会将元素进行自动排序。功能......
  • 大连市第二十四中学模拟飞行社团章程(草案)
    亲爱的飞行员:你好!欢迎来到大连市第二十四中学模拟飞行社团!我们致力于为每一位喜爱蓝天的同志提供不一样的模拟飞行体验。同时,为了是您更好的了解本社团并在加入后有更好的体验,我们特在此制作本社团章程,旨在维护社团有序、和谐的运行。一.社团简介本社团全名大连市第二十四中学......
  • 【C++ Primer Plus习题】12.1
    大家好,这里是国中之林!❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看←问题:解答:main.cpp#include<iostream>#include"Cow.h"usingnamespacestd;intmain(){ Cowc1; ......
  • sping boot 基于 RESTful 风格,模拟增删改查操作
    RESTful-> 增:post 删:delete 改: put查: getRESTful资源路径,一般以s复数结尾 以下是代码示例:packagecom.example.springboot.controller;importorg.springframework.web.bind.annotation.*;@RestControllerpublicclassHello{@RequestMappi......
  • C++编程-搜索与回溯算法2
    目录每日一诗先言正文例题六题目描述算法分析标准程序例题七:选书题目描述算法分析标准程序输出例题八:跳马问题题目描述标准程序小练习题目描述输入输出样例输入 复制样例输出 复制每日一诗红豆生南国,春来发几枝。愿君多采撷,此物最相思。Redbea......
  • 条款05: 了解c++默默编写并调用哪些函数
    1.如果没有声明任何构造函数,编译器会为你声明一个default构造函数2.惟有default构造函数被需要,才会被编译器创建出来classEmpty{public:Empty(){}//1.默认构造~Empty(){}//2.析构函数Empty(constEmpty&rhs){}//3.copy构造Empty&operator=(c......