当前位置： 首页 > article >正文

C++——模拟实现vector

article 2024/10/5 21:15:34

1.查看vector的源代码

2.模拟实现迭代器

#pragma once

namespace jxy
{
	//模板尽量不要分离编译
	template <class T>
	class vector
	{
	public:
		typedef T* iterator;//typedef会受到访问限定符的限制
		typedef const T* const_iterator;
		//const迭代器是指向的对象不能修改，否则岂不是遍历时it都不能++了

		iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		const_iterator begin() const
		{
			return _start;
		}

		const_iterator end() const
		{
			return _finish;
		}

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

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

		for (size_t i = 0; i < v.size(); i++)
		{
			cout << v[i] << " ";
		}
		cout << endl;

		vector<int>::iterator it = v.begin();
		while (it != v.end())
		{
			cout << *it << " ";
			it++;
		}
		cout << endl;

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}

}

3.成员函数

3.1构造和析构

#pragma once

namespace jxy
{
	//模板尽量不要分离编译
	template <class T>
	class vector
	{
	public:

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

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

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

3.2拷贝构造

namespace jxy
{
	//模板尽量不要分离编译
	template <class T>
	class vector
	{
	public:

		//vector的拷贝构造
//注意：vector中拷贝数据，数据是内置类型才可以使用memcpy
//否则比如是string，又会出现深层次的浅拷贝问题
		
        vector(const vector<T>& v)
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)//这里不初始化的话，去reserve时会是随机值
		{
			reserve(v.capacity());//capacity函数也要加上const
			for (auto& e : v)
			{
				push_back(e);
			}
		}
		//注意使用引用，T是小对象还好，如果是大对象，代价就大了

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

	void test_vector8()
	{
		//不写拷贝构造，编译器默认是浅拷贝
		//所以不写拷贝构造时,程序会崩溃
		vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);

		vector<int> v2(v1);
		//vector<int>、vector<string>不是同一个类型

		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

		for (auto e : v2)
		{
			cout << e << " ";
		}
		cout << endl;

	}
}

3.3赋值重载

namespace jxy
{
	//模板尽量不要分离编译
	template <class T>
	class vector
	{
	public:

		void swap(vector<T>& tmp)
		{
			std::swap(_start, tmp._start);//不加std找不到库中的swap
			std::swap(_finish, tmp._finish);
			std::swap(_end_of_storage, tmp._end_of_storage);

		}

		//赋值重载
		vector<T>& operator=(vector<T> tmp)//调用赋值要先传参，v3传给tmp是拷贝构造
		{
			swap(tmp);
			return *this;
		}

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

	void test_vector8()
	{
		vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);

		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

		vector<int> v3;
		v3.push_back(10);
		v3.push_back(20);
		v3.push_back(30);
		v3.push_back(40);

		v1 = v3;
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;
	}
}

3.4.补充：类模板的一个奇怪用法

我们可以发现，库中的拷贝构造，x的类型写的是vector，而不是vector<T>

已知类名不是类型，然而事实上，在类里面，要使用类型的话，使用vector也可以，但不建议这么使用

3.5使用迭代器区间去构造

namespace jxy
{

	template <class T>
	class vector
	{
	public:

		//注意：在一个类模板里面还可以正常写模板函数

		template <class InputIterator>
		vector(InputIterator first, InputIterator last)
		//VS2019的编译器对内置类型进行了处理，初始化成了0，所以这里没有问题
		//但内置类型编译器不一定会处理，所以需要自己写初始化列表
		{
			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}

	private:
		iterator _start = nullptr;//这里把缺省值给上就不需要写初始化列表了
		iterator _finish = nullptr;
		iterator _end_of_storage = nullptr;
	};

	void test_vector9()
	{
		vector<int> v2;
		v2.push_back(10);
		v2.push_back(20);
		v2.push_back(30);
		v2.push_back(40);

		vector<int> v3(v2.begin(), v2.end());

		string str("hello world");
		vector<int> v4(str.begin(), str.end());
		for (auto e : v3)
		{
			cout << e << " ";
		}
		cout << endl;

		for (auto e : v4)
		{
			cout << e << " ";
		}
		cout << endl;
	}
}

为什么要写成模板函数？

因为如果这里使用iterator而不使用模板的话，那么vector使用该构造时就只能使用vector类型的迭代器区间来初始化。而如果写成模板的话，就可以使用各种类型的迭代器来初始化了，只要数据类型匹配就可以。

3.6使用n个val去构造

namespace jxy
{

	template <class T>
	class vector
	{
	public:

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

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

	void test_vector9()
	{
		vector<int> v0(10, 0);//但这里会报错
		vector<string> v1(10, "xxxx");//这里正常

		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;
	}
}

所以我们可以给int类型单独写一个重载函数来解决问题

//有更匹配的之后，就不会去实例化模板了
vector(int n, const T& val = T())
{
	reserve(n);
	for (size_t i = 0; i < n; i++)
	{
		push_back(val);
	}
}

4. Capacity

4.1 size和capacity

namespace jxy
{
	//模板尽量不要分离编译
	template <class T>
	class vector
	{
	public:

		size_t size()
		{
			return _finish - _start;
		}

		size_t capacity()
		{
			return _end_of_storage - _start;
		}

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

4.2reserve

namespace jxy
{
	//模板尽量不要分离编译
	template <class T>
	class vector
	{
	public:

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t sz = size();
				T* tmp = new T[n];
                //库里面这里是内存池来的
				if (_start)//旧空间有可能为空
				{
					memcpy(tmp, _start, sizeof(T)*size());
					delete[] _start;
				}

				_start = tmp;
				_finish = _start + sz;
				_end_of_storage = _start + n;
			}
		}
	};
}

4.3resize

namespace jxy
{
	//模板尽量不要分离编译
	template <class T>
	class vector
	{
	public:

		//void resize(size_t n,T value=T())
		void resize(size_t n, const T& value = T())
		{ 
			if (n <= size())
			{
				_finish = _start + n;

			}
			else
			{
				reserve(n);
				while (_finish < _start + n)
				{
					*_finish = value;
					_finish++;
				}
			}
		}

	};

	void test_vector3()
	{
		vector<string> v1;
		v1.resize(10);
		//空的string不会打印出来东西

		//v1.resize(10, string("xxx"));
		//可以填写匿名对象

		//v1.resize(10, "xxx");
		//甚至还可以这样写，因为单参数构造函数支持隐式类型转换

		vector<int*> v2;
		v2.resize(5);

		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

		for (auto e : v2)
		{
			cout << e << " ";
		}
		cout << endl;

	}

}

关于resize的参数

void resize(size_t n,T value=T())
这里缺省值不能给0，因为T的类型不能确定就是int
它也可以是double、string等等，所以这里是不能给固定值的
T类型的匿名对象，本质是调用默认构造，然后调用拷贝构造，优化为直接构造

void resize(size_t n, const T& value = T())
这样写就是创建一个匿名对象，然后去引用它
const引用会延长匿名对象的生命周期，延长到val不使用了，就结束了
匿名对象、临时对象具有常性，必须加const
            
这里缺省值是调用默认构造生成的值
那么问题又来了，如果T是自定义类型，那么匿名对象是有构造函数的
那如果T是内置类型呢？
比如是int，它又没有构造函数，怎么办？

事实上，模板设计出来以后，C++语法进行了升级
内置类型也可以认为有构造函数，否则泛型编程就无法使用

void test_vector2()
    {//这样写是可以的
        int a = 0;
        int b(1);
        int c = int(2);

        //在面向对象编程中，可以说一切都是对象
    }

5. Element access

5.1 operator[]

namespace jxy
{
	//模板尽量不要分离编译
	template <class T>
	class vector
	{
	public:

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

			return _start[pos];
		}

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

			return _start[pos];
		}

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

}

6. Modifiers

6.1 push_back

namespace jxy
{
	//模板尽量不要分离编译
	template <class T>
	class vector
	{
	public:

		void push_back(const T& x)
		{
			if (_finish == _end_of_storage)//判断容量是否已满
			{
				size_t sz = size();
				size_t cap = capacity() == 0 ? 4 : capacity() * 2;
				//容量为0就开空间，否则就2倍扩容，然后拷贝数据，释放旧空间
				T* tmp = new T[cap];
				if (_start != nullptr)
				{
					memcpy(tmp, _start, sizeof(T) * size());
					delete[] _start;

				}
				_start = tmp;
				_finish = _start + sz;
				_end_of_storage = _start + cap;
			}

		}

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

}

还可以去复用reserve来实现

void push_back(const T& x)
{

	if (_finish == _end_of_storage)
	{
		reserve(capacity() == 0 ? 4 : capacity() * 2);
	}

	*_finish = x;
	_finish++;

}

6.2 insert

错误示范：

namespace jxy
{
	//模板尽量不要分离编译
	template <class T>
	class vector
	{
	public:

		void insert(iterator pos,const T& val)
		{
			assert(pos >= begin());
			assert(pos <= end());		

			if (_finish == _end_of_storage)
			{
				reserve(capacity() == 0 ? 4 : capacity()*2);

			}

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

			*pos = val;
			_finish++;
		}

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

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

		for (auto e:v)
		{
			cout << e << " ";
		}
		cout << endl;

		v.insert(v.begin() + 2, 100);

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

		//头插
		//这里的头插就不需要单独处理了，因为pos不可能是0
		v.insert(v.begin(), 100);

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
    }

}

但是，只要把测试代码稍作修改，就会发现问题。

	void test_vector4()
	{

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

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

        //第一次插入数据
		v.insert(v.begin() + 2, 100);

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

        //第二次插入数据
		v.insert(v.begin(), 100);

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

        //此时push_back如果去复用insert，程序会崩溃
	}

6.2.1迭代器失效：野指针

此时就涉及到一个问题，迭代器失效。

insert的正确写法：

void insert(iterator pos,const T& val)
{
	assert(pos >= begin());
	assert(pos <= end());		

	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 = val;
	_finish++;
}

6.3 erase

namespace jxy
{

	template <class T>
	class vector
	{
	public:

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

			iterator it = pos + 1;
			while (it < _finish)
			{
				*(it - 1) = *it;
				it++;
			}
			_finish--;
		}

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

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

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

		vector<int>::iterator pos = v.begin();

		v.erase(pos);
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}

}

6.3.1迭代器失效

何为迭代器失效？

迭代器失效就是不能再使用这个迭代器了，如果使用了，那么结果就是未定义的。

迭代器失效就不能使用它来访问了。

void test_vector6()
{
	//想要删除所有偶数
	std::vector<int> v;

	//1.
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);

	//2.
	//v.push_back(1);
	//v.push_back(2);
	//v.push_back(3);
	//v.push_back(4);
	//v.push_back(5);
	//v.push_back(6);
	//此时多插了个数据就会出问题

	//3.
	//v.push_back(2);
	//v.push_back(2);
	//v.push_back(3);
	//v.push_back(4);
	//v.push_back(5);
	//此时程序可以正常运行，但是结果不对，偶数没有删除完

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

	auto it = v.begin();
	while (it != v.end())
	{
//VS2019会进行强制检查
//erase以后认为it就失效了，不允许访问，访问就会报错
		if ((*it%2) == 0)
		{
			v.erase(it);
		}
		it++;
	}

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

6.3.2解决方案

库里erase的实现：

所以要对测试代码进行改进

void test_vector6()
{
	//想要删除所有偶数
	std::vector<int> v;

	v.push_back(1);

	v.push_back(2);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	v.push_back(8);
	v.push_back(8);

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

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

此时库中的erase也可以正常使用了。

再来修改下我们模拟实现的erase

namespace jxy
{

	template <class T>
	class vector
	{
	public:

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

			iterator it = pos + 1;
			while (it < _finish)
			{
				*(it - 1) = *it;
				it++;
			}
			_finish--;
			return pos;
		}

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

	void test_vector6()
	{
		vector<int> v;

		v.push_back(1);
		v.push_back(2);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);
		v.push_back(8);
		v.push_back(8);

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

		auto it = v.begin();
		while (it != v.end())
		{
			if ((*it%2) == 0)
			{
				it=v.erase(it);
//或者erase不去更改，让它的返回值类型依旧是void，这里写作 v.erase(it);  也可以
			}

			else
			{
				it++;//不删除时才去++
			}
			
		}

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}

}

6.4总结

使用insert和erase后，我们都认为迭代器失效，不能再访问，使用的话结果是未定义的。

如果想继续使用，可以使用返回值来控制

7.关于深层次的浅拷贝问题

7.1引入

namespace jxy
{

	template <class T>
	class vector
	{
	public:

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t sz = size();
				T* tmp = new T[n];
				if (_start)//旧空间有可能为空
				{
					memcpy(tmp, _start, sizeof(T)*size());
					delete[] _start;
				}

				_start = tmp;
				_finish = _start + sz;
				_end_of_storage = _start + n;
			}
		}

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

	void test_vector7()
	{
		//深拷贝问题

		vector<string> v;
		v.push_back("111111111111111111111");
		v.push_back("111111111111111111111");
		v.push_back("111111111111111111111");
		v.push_back("111111111111111111111");
		//v.push_back("111111111111111111111");


		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

	}

}

这是为什么？

7.2解决方案

经过分析可知，主要的问题就是出在memcpy上，那么应该如何改写代码，使得string能够进行深拷贝呢？

实际上只要把memcpy改写成for循环，调用string的赋值就可以解决问题了。

namespace jxy
{

	template <class T>
	class vector
	{
	public:

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t sz = size();
				T* tmp = new T[n];
				if (_start)//旧空间有可能为空
				{
					for (size_t i = 0; i < sz; i++)
					{
						tmp[i] = _start[i];
						//string的赋值重载就是深拷贝
					}
					delete[] _start;
				}

				_start = tmp;
				_finish = _start + sz;
				_end_of_storage = _start + n;
			}
		}

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

	void test_vector7()
	{
		//深拷贝问题

		vector<string> v;
		v.push_back("111111111111111111111");
		v.push_back("111111111111111111111");
		v.push_back("111111111111111111111");
		v.push_back("111111111111111111111");
		v.push_back("111111111111111111111");

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

	}

}

进一步改进：

这里直接写深拷贝，还是有些浪费，拷贝数据，还要释放旧的空间

如果string使用引用计数的浅拷贝，就非常有价值了。

8.练习题

17. 电话号码的字母组合 - 力扣（LeetCode）


http://www.kler.cn/news/333651.html

相关文章：

  • RTC实时时钟
  • Vim 命令行模式下的常用命令
  • 【QT】亲测有效：“生成的目标文件包含了过多的段，超出了编译器或链接器允许的最大数量”错误的解决方案
  • 通过下面步骤高效提升前端加载静态文件效率
  • C++初阶：STL详解（七）——list的模拟实现
  • C++学习笔记----8、掌握类与对象（二）---- 成员函数的更多知识（2）
  • 【Mybatis篇】Mybatis的关联映射详细代码带练 （多对多查询、Mybatis缓存机制）
  • 【Java的SPI机制】Java SPI机制：实现灵活的服务扩展
  • 4.人员管理模块(开始预备工作)——帝可得管理系统
  • （16）MATLAB仿真Nakagami-m分布1
  • 高并发领取优惠卷加锁的坑！（事务边界问题/事务失效问题）
  • leetcode42:接雨水
  • Linux驱动开发(速记版)--设备模型
  • WPF下使用FreeRedis操作RedisStream实现简单的消息队列
  • Vue+NestJS项目实操（图书管理后台）
  • 分治算法(1)_颜色分类
  • 初识数据结构--时间复杂度 和 空间复杂度
  • Linux 之 安装软件、GCC编译器、Linux 操作系统基础
  • TX-LCN框架 分布式事务
  • 【案例】平面云