C++篇 Vector模拟实现（1） 初始化 迭代器遍历 插入尾插尾删 一文详解

vector<int>v1;//无参数的构造
	vector<int>v2(10, 1);//带参数的构造，初始化1个数组，
	vector<int>v3(++v2.begin(), --v2.end());//还可以用一段迭代器区间去初始化
	//v3用v2去初始化，不想要第一个，也不想用最后一个，可以向上面那么写。v3有8个1

	//遍历v3，下标第一种遍历方法
	for (size_t i = 0; i < v3.size(); i++)
	{
		cout << v3[i] << " ";
	}
	cout << endl;
	//用迭代器去遍历，要指定类域，实例化的模板参数，第二种遍历
	vector<int>::iterator it = v3.begin();
	while (it != v3.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	
	//第三种遍历,范围for
	for (auto e : v3)
	{
		cout << e << " ";
	}
	cout << endl;

void test_vector2()
{
	vector<int>v(10, 1);//初始化10个1
	v.reserve(20);//扩容到20
	cout << v.capacity() << endl;//20
	cout << v.size() << endl;//10

	v.reserve(15);
	cout << v.capacity() << endl;//20
	cout << v.size() << endl;//10

	v.reserve(5);
	cout << v.capacity() << endl;//20
	cout << v.size() << endl;//10    //坚决不缩容，capacity在增加到20之后，就没有变化了
}

void test_vector3()
{
	vector<int>v(10.1);
	v.reserve(20);//扩容到capacity=20，size是10，capacity是20
	cout << v.capacity() << endl;//20
	cout << v.size() << endl;//10

	v.resize(15.2);//10个1，补了5个2（调试过程中）,capacity=20
	cout << v.size() << endl;
	cout << v.capacity() << endl;

	v.resize(25.3);//capacity是30，按照2倍扩容，10个1，size=25
	cout << v.size() << endl;
	cout << v.capacity() << endl;

	v.resize(5);//capacity=30,size=5,只保留5个数据，5个1
	cout << v.size() << endl;
	cout << v.capacity() << endl;
}

void test_vector4()
{
	vector<int>v(10, 1);
	v.push_back(2);
	v.insert(v.begin(), 0);

	//遍历要用迭代器
	for (auto e : v)
	{
		cout << e << " ";// 0  1  1  1  1  1   1   1   1   1   1   2
	}
	cout << endl;

	v.insert(v.begin() + 3, 10);//在第3个位置加一个10

	for (auto e : v)
	{
		cout << e << " ";// 0  1  1  10  1   1  1   1   1   1   1   1   2
	}
	cout << endl;

	v.clear();//实现vector的流插入流提取，方法1
	int x;
	cin >> x;
	v.push_back(x);

	vector<int> v1(5, 0);//给5个数据初始化为0，方法2：用范围for进行遍历
	for (size_t i = 0; i < 5; i++)
	{
		cin >> v1[i];//cin输入v1[i]；
	}
	for (auto e : v1)
	{
		cout << e << " ";//用范围for进行遍历，输入的数字用空格分割，最后打印出55个数字
	}
	cout << endl;
}

void test_vector5()
{
	vector<string>v1;//vector中还可以存储自定义类型
	string s1("xxxxxxx");

	v1.push_back(s1);
	v1.push_back("yyyyyy");//const char* 还可以隐式类型转换
	for (const auto& e : v1)//*it取每个值，都是一个string，string给e，进行每次拷贝构造
		//有多少个string对象就要拷贝构造多少次，所以加& ，不改变遍历的值前面加const
		//以前都是拷贝一下Int，代价比较小，如果要拷贝string，不仅要开空间还要调用数据

	{
		cout << e << " ";
	}
	cout << endl;


	//假如要实现10*5的二维数组
	//vector<vector<int>>vv();//vector里面存vector，就是二维数组
	vector<int>v(5, 1);
	vector<vector<int>>vv(10, v);//10个v,v是v(5,1)
	//vv[2][1] = 2;//访问第二行第一个并且将其修改为2    ///看图！！！
	//编译器实例化了两个vector，
	vv.operator[](2).operator[](1) = 2;//等价于vv[2][1]=2;
	for (size_t i = 0; i < vv.size(); i++)
	{
		for (size_t j = 0; j < vv[i].size(); j++)
		{
			cout << vv[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;

}

clase Solution{
public:
	vector<vector<int>>generate(int numsRow)
	{
		vector<vector<int>>vv(numsRow);//开n行
		for (size_t i = 0; i < numsRow; ++i)
		{
			vv[i].resize(i + 1, 0);//第0行（索引）有1个，第1行（索引）有2个，每个数据默认给0
			//vv[i][0]=vv[i][vv[i].size(）-1]=1;
			vv.front = vv.back = 1;
		}
		for (int i = 2; i < vv.size(); ++i)//第0行和第1行不需要
		{
			for (int j = 1; j < vv[i].size()-1; ++j)//避开每一行的第一个数据和组后一个数据
			{
				vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];//上一行的当前位置+上一行的前一个位置
			}
		}
		return vv;
	}
}

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
namespace Keda
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;//使用typedef为T*（指向模板类型T的指针）定义了一个
		//别名iterator，用于遍历容器中的元素。表示vector类的迭代器是一个指向T类型的指针
		typedef const T* const_iterator;//const不可修改型

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

		const_iterator begin()const
		{
			return _start;
		}
		const_iterator end()const
		{
			return _finish;
		}
		size_t size()const
		{
			return _finish - _start;
		}
		size_t capacity()const
		{
			return _end_of_storage - _start;
		}

		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;//用于判断是否需要扩容，意为空间用完了
	};
}

//模板
template<class T>
void print_vector(const vector<T>& v)//const对象就要用const迭代器
{
	//在没有实例化的类模板里面取东西，规定：没有实例化的类模板里面取东西
	//编译器不能区分这里的const_iterator是类型还是静态成员变量
	//typename vector<T>::const_iterator it = v.begin();//也可以直接由编译器自己推导
	//静态成员变量不需要有类型
	auto it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

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

void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t old_size = size();
		T* tmp = new T[n];//开新的空间
		memcpy(tmp, _start, size() * sizeof(T));//拷贝旧空间的数据给新的空间
		delete[]_start;//释放掉旧的空间

		_start = tmp;//指向新的空间
		_finish = tmp + old_size;
		_end_of_storage = tmp + n;
	}

}

void push_back(const T& x)
{
	if (_finish != _end_of_storage)
	{
		*_finish = x;
		++_finish;
	}
	else
	{
		reserve(capacity() == 0 ? 4 : capacity() * 2);
		*_finish = x;
		++_finish;
	}
	iterator insert(iterator pos, const T& x)
	{
		if (_finish == _end_of_storage)
		{
			size_t len = pos - _start;
			reserve(capacity() == 0 ? 4 : 2 * capacity());
			pos = len + _start;
		}

		iterator end = _finish - 1;
		while (end >= pos)//可以等于0
		{
			*(end + 1) = *(end);
			--end;
		}
	*pos = x;
	++_finish;
	return pos;
}

void test_vector2()
{
	vector<int>v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	//v.push_back(5);
	print_vector(v);

	v.insert(v.begin() + 3, 45);
	print_vector(v);

	//迭代器区间要求传左闭右开
	int x;
	cin >> x;
	auto pos = find(v.begin(), v.end(), x);
	if (pos != v.end())
	{
		//v.insert(pos, 40);
		//查找x,找到之后让pos*=10,假如pos=2，我们乘等10，应该输出20
		//(*pos) *= 10;//实际上输出400，为什么？这里也是迭代器失效的问题，所以insert以后pos就失效了，不要访问
		//pos还指向的是旧空间，再解引用就是越界的野指针，即使在insert里面做了改变，已经更新过了，但是毕竟是在内部，实参的改变不影响形参


		//那要是一定要哦访问呢？？？
		//这里可以将insert操作完之后在内部操作的值pos返回，iterator insert (iterator pos,const T& s); 下面return pos
		//在测试中：pos=v.insert(pos,40); (*(p+1)) *=10

		pos = v.insert(pos, 40);
		(*(pos+1) ) *= 10;
	}
	print_vector(v);

}

bool empty()
{
	return _start == _finish;
}
void pop_back()
{
	assert(!empty());
	--_finish;
}