vector使用&模拟实现

1.vector拷贝构造

 vector使用如下：
vector是一个存储数据的顺序表。push_back进行插入数据，vector是模版定义的,可以存储任何数据：vector<数据类型>变量名；

void test_vector1()
{
	//string 
	//vector<char> 
	//
	vector<string> v3;
	vector<double> v2;

	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	for (size_t i = 0; i < v1.size(); i++)
	{
		cout << v1[i] << " ";
	}
	cout << endl;
	//在vector中定义的，要指明来处
	vector<int> :: iterator it1 = v1.begin();
	while (it1 != v1.end())
	{
		cout << (*it1) << " ";
		it1++;
	}
	cout << endl;
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;
}

2.其它接口

 operator=是赋值

 begin、end是迭代器

 size:获取数据个数 capacity：获取容量
 resize:指定数据个数 reserve:设置容量

 operator[]:按下标访问数据
 front:获得第一个数据
 back:获得最后一个数据



 push_back尾插，pop_back尾删

 insert在某个地址插入数据，其他数据向后面移动，注意的是用迭代器传参

//void push_back(const string& s)
//{}
void test_vector2()
{
	vector<string> v1;
	string s1("张三");
	v1.push_back(s1);
	v1.push_back(string("李四"));
	v1.push_back("王五");
	v1[0] += "猪";
	for (const auto& e : v1)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << v1.front() << endl;
	cout << v1.back() << endl;
}

void test_vector3()
{
	vector<int> v1;
	v1.push_back(10);
	v1.push_back(2);
	v1.push_back(30);
	v1.push_back(4);
	v1.push_back(44);
	v1.push_back(4);
	v1.push_back(40);
	v1.push_back(4);
	//仿函数
	greater<int> gt;
	//默认是升序
	//传gt,降序，具体为什么，不知道
	//sort(v1.begin(), v1.end(),gt);
	// 一般这么用
	//greater<int>() -->传匿名对象
	sort(v1.begin(), v1.end(), greater<int>());
	//sort(v1.begin(), v1.begin() + v1.size() / 2);
	for (auto e : v1)
	{
		cout << e << " ";
	}
}

 sort(RandomAccessIterator first,RandomAccessIterator last,Compare comp)
 sort默认是排升序，传迭代器进行排序，若排降序，则用仿函数greater<数据类型>，可以传匿名对象，greaterv< int >()

 find在算法中可查找任何一个数据的迭代器

3、vector模拟实现

 基本框架如下： _star指向第一个位置，_finish指向存储数据的下一个位置，这样_finish-_start就是数据个数，_end_of_storage申请一段空间的最后一个字节的下一个位置，_end_of_storage-_start就是整个空间的容量

namespace wyj
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T*  const_iterator;
	private:
		iterator _start = nullptr;
		iterator _finish = nullptr;
		iterator _end_of_storage = nullptr;
	};
}

 先把_start,_finish,_end_of_storage置nullptr，调用默认构造时，会初始化成员会nullptr,在写push_back,要尾插，在写一些预备接口，capacity，size，reserve.具体如下。

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)
{
	return _start[i];
}

const T& operator[](size_t i)const
{
	return _start[i];
}

void reserve(size_t n)
{
	if (capacity() < n)
	{
		//这儿是使用迭代器（指针）来标记位置
		//只要申请新的空间，空间地址就会变了
		//因此先存储_start到_finish的距离
		size_t old_size = size();
		T* tmp = new T[n];
		if (_start)
		{
			//memcpy不能传nullptr
			memcpy(tmp, _start, sizeof(T) * n);
			delete[] _start;
		}
		_start = tmp;
		_finish = _start + old_size;
		_end_of_storage = _start + n;
	}
}

 具体上面接口如下，简单的接口不做解释，看看reserve还是那一套，先申请一个指定的空间，把内容拷贝到指定空间，在更新成员变量即可，需要注意的是，上面写法不行，浅拷贝可以，深拷贝不行，假设存储vector < string> v1,存的是string，再扩容时，发生浅拷贝，只是把string里面成员的值拷贝过来，真正字符串在堆上存的空间已经调用析构函数销毁了，这个是不行的，只有赋值调用string的拷贝构造才行。

 写push_back、pop_back

//这儿插入的时候参数为const T& val,考虑到自定义类型，数据过大
void push_back(const T& val)
{
	if (_finish == _end_of_storage)
	{
		size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
		reserve(newcapacity);
	}
	*_finish = val;
	_finish++;
}

void pop_back()
{
	assert(size() > 0);
	--_finish;
}

 写insert、erase

iterator insert(iterator pos,const T& val)
{
	assert(pos >= _start && pos <= _finish);
	if (_finish == _end_of_storage)
	{
		//扩容有问题，导致pos地址会变化
		size_t len = pos - _start;
		size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
		reserve(newcapacity);
		pos = _start + len;
	}
	iterator end = _finish;
	while (end > pos)
	{
		*end = *(end - 1);
		end--;
	}
	*pos = val;
	++_finish;
	return pos;
}

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

 iterator insert(iterator pos,const T& val),在插入数据的时候发生扩容，导致pos地址发生变化，在函数外面出来时，访问pos位置，原来pos地址所在的空间已销毁，要更新pos,因此返回pos的地址，来更新pos，所谓的迭代器失效问题。
 还有erase问题，一些编译器出于安全考虑，删除的位置，将不会被访问，这也是迭代器失效的一种。
 测试代码如下

void test3()
{
	vector<int>v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	//删除2，先记住2的地址
	vector<int> ::iterator it = v1.begin() + 1;
	v1.erase(it);
	//在访问保存的这个地址
	cout << (*it) << endl;
}

 构造函数接口如下

template<class InputItrator>
vector(InputItrator first, InputItrator 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++)
	{
		this->push_back(val);
	}
}

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

vector(const vector<T>& v)
{
	reserve(v.size());
	for (size_t i = 0; i < v.size(); i++)
	{
		this->push_back(v[i]);
	}
}

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

void swap(vector<T>&v)
{
	std::swap(_start, v._start);
	std::swap(_finish, v._finish);
	std::swap(_end_of_storage, v._end_of_storage);
}
//强制默认构造
vector() = default;
~vector()
{
	if (_start)
	{
		delete[] _start;
		_start = _finish = _end_of_storage = nullptr;
	}
}

//v是一份临时拷贝
vector<T>& operator=( vector<T>v)
{
	this->swap(v);
	return *this;
}

 先写拷贝构造，vector(const vector& v)取v的元素直接尾插即可。
 支持迭代器的构造函数，用模版来写，初始化时，直接可以放任何迭代器访问的数据。
template < class InputItrator>
vector(InputItrator first, InputItrator last)
 介绍下下面这个构造函数



 关于template< class T>class initializer_list的详细介绍看这个博客！
 <initializer_list> 头文件中的一个模板类。它可以用于接收花括号初始化列表（例如 {1, 2, 3}）作为参数。

#include <initializer_list>
#include <iostream>
 
void print(std::initializer_list<int> ilist) {
    for (auto elem : ilist) {
        std::cout << elem << ' ';
    }
    std::cout << std::endl;
}
 
int main() {
    print({1, 2, 3, 4, 5}); // 输出：1 2 3 4 5
    return 0;
}

  用于表示某种特定类型的值的数组，和vector一样，initializer_list也是一种模板类型。
 反正怎么说，initializer_list可以看做能存储任何数据类型的模版数组。
 

#define  _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <iostream>
#include <algorithm>
#include <assert.h>
using namespace std;

namespace wyj
{
	template<class T>
	class vector
	{
	public:
		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;
		}
		size_t size()const
		{
			return _finish - _start;
		}

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

		T& operator[](size_t i)
		{
			return _start[i];
		}

		const T& operator[](size_t i)const
		{
			return _start[i];
		}

		template<class InputItrator>
		vector(InputItrator first, InputItrator 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++)
			{
				this->push_back(val);
			}
		}

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

		vector(const vector<T>& v)
		{
			reserve(v.size());
			for (size_t i = 0; i < v.size(); i++)
			{
				this->push_back(v[i]);
			}
		}

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

		void swap(vector<T>&v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_end_of_storage, v._end_of_storage);
		}
		//强制默认构造
		vector() = default;
		~vector()
		{
			if (_start)
			{
				delete[] _start;
				_start = _finish = _end_of_storage = nullptr;
			}
		}

		//v是一份临时拷贝
		vector<T>& operator=( vector<T>v)
		{
			this->swap(v);
			return *this;
		}

		void reserve(size_t n)
		{
			if (capacity() < n)
			{
				size_t old_size = size();
				T* tmp = new T[n];
				if (_start)
				{
					//memcpy不能传nullptr
					memcpy(tmp, _start, sizeof(T) * n);
					delete[] _start;
				}
				_start = tmp;
				_finish = _start + old_size;
				_end_of_storage = _start + n;
			}
		}

		//这儿插入的时候参数为const T& val,考虑到自定义类型，数据过大
		void push_back(const T& val)
		{
			if (_finish == _end_of_storage)
			{
				size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
				reserve(newcapacity);
			}
			*_finish = val;
			_finish++;
		}

		void pop_back()
		{
			assert(size() > 0);
			--_finish;
		}

		iterator insert(iterator pos,const T& val)
		{
			assert(pos >= _start && pos <= _finish);
			if (_finish == _end_of_storage)
			{
				//扩容有问题，导致pos地址会变化
				size_t len = pos - _start;
				size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
				reserve(newcapacity);
				pos = _start + len;
			}
			iterator end = _finish;
			while (end > pos)
			{
				*end = *(end - 1);
				end--;
			}
			*pos = val;
			++_finish;
			return pos;
		}

		void erase(iterator pos)
		{
			assert(pos >= _start && pos < _finish);
			iterator end = pos + 1;
			while (end != _finish)
			{
				*(end - 1) = *end;
				++end;
			}
			_finish--;
		}
	private:
		iterator _start = nullptr;
		iterator _finish = nullptr;
		iterator _end_of_storage= nullptr;
	};
	
	void vector_test1()
	{
		vector<int>v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		v1.push_back(5);
		v1.push_back(6);
		for (size_t i = 0; i < v1.size(); i++)
		{
			cout << v1[i] << " ";
		}
		cout << endl;
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;
		v1.pop_back();
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;
		v1.insert(v1.begin(), 0);
		v1.insert(v1.begin(), -1);
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;
		v1.erase(v1.begin());
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

		vector<int>v2 = v1;
		for (auto e : v2)
		{
			cout << e << " ";
		}
		cout << endl;

	}
	
	void vector_test2()
	{
		vector<int>v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		v1.push_back(5);
		v1.push_back(6);
		vector<int>v2(v1.begin(), v1.end()-1);
		for (auto e : v2)
		{
			cout << e << " ";
		}
		cout << endl;
		vector<string>v3(3, "hello ");
		for (auto e : v3)
		{
			cout << e << " ";
		}
		cout << endl;
		vector<string>v4;
		v4 = v3;
		for (auto e : v3)
		{
			cout << e << " ";
		}
		cout << endl;
		vector<int>v5(2, 1);
		for (auto e : v5)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void vector_test3()
	{
		vector<int>v1 = { 1,2,3,4,5 };
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;
	}
}