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

【C++】vector的模拟实现

时间：2024-09-08 11:24:54浏览次数：7  
标签：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......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99