【C++】vector_memcpy对vector赋值

目录

1. vector介绍

1.1. 什么是vector

1.2. vector常用接口

2. vector常用接口模拟实现

2.1. 构造函数+析构函数+operator=

2.2. 迭代器

2.3. 其他常用接口

2.4. 迭代器失效 and memcpy问题

2.4.1.pos位置之前插入

2.4.2erase删除pos位置

2.4.3.memcpy问题

---

1. vector介绍

1.1. 什么是vector

1. vector是表示可变大小数组的序列容器。

2. 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素 进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自 动处理。

3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小 为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是 一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大 小。

4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存 储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是 对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。

5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增 长。

6. 与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在 末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。

1.2. vector常用接口

2. vector常用接口模拟实现

对于像vector这样的模板容器，一般不采用声明和定义分离的形式实现！

2.1. 构造函数+析构函数+operator=

对于vector在STL源代码的SGI版本中，不同于string的实现，在定义类中的私有变量时不会定义一个指针两个整形的方法；而是定义三个指针，分别指向数组的开头，最后一个有效元素的下一个位置，数组末尾。

#pragma once
#include<iostream>
#include<assert.h>
#include<algorithm>
using namespace std;
 
namespace wt
{
	template<class T>
	class vector
	{
	public:
 
		vector() // 空构造
			:_start(nullptr)
			,_finish(nullptr)
			,_endofstorage(nullptr)
		{}
 
		template<class Intputiterator> // 迭代器构造
		vector(Intputiterator first, Intputiterator last)
			:_start(nullptr)
			,_finish(nullptr)
			,_endofstorage(nullptr)
		{
			while (first != last)
			{
				push_back(*first); // 这里不能采用直接赋值指针的方法，需一个一个尾插
				++first;
			}
		}
 
        void swap(vector<T>& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstorage, v._endofstorage);
		}
 
		vector(const vector<T>& v) //拷贝构造
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			vector<T> tmp(v.begin(), v.end()); // 利用迭代器构造临时对象
			swap(tmp); // 将临时对象与目标对象交换 
		}
 
		~vector() // 析构函数
		{
			delete[] _start;
			_start = _finish = _endofstorage = nullptr;
		}
 
		
		vector<T>& operator=(vector<T> v) // 赋值运算符重载
		{
			swap(v); // 这使用的是传值传参，所以直接将临时对象交换给目标对象即可
			return *this;
		}
	private:
		iterator _start; // 记录数组起始位置
		iterator _finish; // 记录最后一个有效元素下一个位置
		iterator _endofstorage; // 记录数组最大容量位置
	};

2.2. 迭代器

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

2.3. 其他常用接口

		// 重载[]
        T& operator[](size_t i)
		{
			return *(_start + i);
		}
 
		const T& operator[](size_t i)const
		{
			return *(_start + i);
		}
 
        // 返回vector有效元素个数
        size_t size()const 
		{
			return _finish - _start;
		}
 
        // 返回vector容量
		size_t capacity()const
		{
			return _endofstorage - _start;
		}
 
        // 改变vector有效元素个数
		void resize(size_t n, const T& val = T())
		{
			if (n < size())
			{
				_finish = _start + n;
				*_finish = val;
			}
			else
			{
				if (n > capacity()) // 容量不够需要扩容
				{
					reserve(n);
				}
				while (_finish != _start + n)
				{
					*_finish = val;
					++_finish;
				}
 
			}
		}
 
        // 扩容
		void reserve(size_t n)
		{
			if (n > capacity())
			{
				T* tmp = new T[n]; // 创建临时数组
				if (_start)
				{
					memcpy(tmp, _start, sizeof(T) * size()); // 将原vector中的数据拷贝到tmp中
					delete[] _start; // 释放原vector
				}
				size_t sz = size();
				_start = tmp; // 将tmp赋值给vector
				_finish = _start + sz;
				_endofstorage = _start + n;
			}
		}
 
        // 尾插
		void push_back(T val)
		{
			if (_finish == _endofstorage) // 检查容量
			{
				reserve(capacity() == 0 ? 4 : capacity() * 2);
			}
			*_finish = val;
			++_finish;
		}
 
        // 尾删
		void pop_back()
		{
			assert(_finish != _start); // vector不能为空
			--_finish;
		}
 
        // pos位置之前插入
		iterator insert(iterator pos, T val)
		{
			assert(pos >= _start);
			assert(pos <= _finish);
			if (_finish == _endofstorage)
			{
				size_t len = pos - _start;
				reserve(capacity() == 0 ? 4 : capacity() * 2);
			}
 
			iterator end = _finish + 1;
			while (end > pos)
			{
				*end = *(end - 1);
				--end;
			}
			*pos = val;
			return pos;
		}
 
        // 删除pos位置
		iterator erase(iterator pos)
		{
			assert(pos >= _start);
			assert(pos < _finish);
			iterator begin = pos;
			while (begin < _finish)
			{
				*begin = *(begin + 1);
				++begin;
			},
			--_finish;
			return pos;
		}

2.4. 迭代器失效 and memcpy问题

2.4.1.pos位置之前插入

当使用insert时，如果涉及到增容，上面的insert就会出现问题。

例如：

void test()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.insert(v.end(), 5);
		vector<int>::iterator it = v.begin();
		while (it != v.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

因为，在增容之后，原来的空间被释放掉了，申请了新空间，而迭代器pos没有改变，依然指向原来的位置，就成了野指针！所以，在扩容之后，需改变pos指针！

iterator insert(iterator pos, T val)
		{
			assert(pos >= _start);
			assert(pos <= _finish);
			if (_finish == _endofstorage)
			{
				size_t len = pos - _start;
				reserve(capacity() == 0 ? 4 : capacity() * 2);
				pos = _start + len; // 扩容后迭代器会失效
			}
 
			iterator end = _finish + 1;
			while (end > pos)
			{
				*end = *(end - 1);
				--end;
			}
			*pos = val;
			return pos;
		}

2.4.2erase删除pos位置

erase也会导致迭代器失效的问题：

void test5()
	{
		vector<int> v;
		v.push_back(1);
		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;
		}
		while (it != v.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

所以，在使用erase时，删除了元素就不移动迭代器！

void test()
	{
		vector<int> v;
		v.push_back(1);
		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);
			}
			else
			{
				++it;
			}
		}
		for (auto& e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}

 

2.4.3.memcpy问题

在上面扩容时，使用了memcpy，在这里会存在一些问题。

例如：在vector中存放字符串

void test6()
	{
		vector<string> v;
		v.push_back("111111111");
		v.push_back("111111111");
		v.push_back("111111111");
		v.push_back("111111111");
 
		for (auto& e : v)
		{
			cout << e << endl;
		}
	}

现在是没有问题的

再继续尾插时，就会开始增容，增容时会出现崩溃：

	void test6()
	{
		vector<string> v;
		v.push_back("111111111");
		v.push_back("111111111");
		v.push_back("111111111");
		v.push_back("111111111");
		v.push_back("111111111");
 
		for (auto& e : v)
		{
			cout << e << endl;
		}
	}

这是因为在扩容时使用了memcpy，而memcpy只是简单的浅拷贝，如果拷贝像string这样的类，在析构时会导致一块空间被析构两次！

所以扩容时不能使用memcpy，可通过其类型自己的赋值运算符重载完成拷贝。

void reserve(size_t n)
		{
			if (n > capacity())
			{
				T* tmp = new T[n];
				if (_start)
				{
					for (size_t i = 0; i < size(); ++i)
					{
						tmp[i] = _start[i];
					}
					delete[] _start;
				}
				size_t sz = size();
				_start = tmp;
				_finish = _start + sz;
				_endofstorage = _start + n;
			}
		}