移情别恋c++ ദ്ദി˶ｰ̀֊ｰ́ ) ——6.vector（模拟实现）

用户11286441

发布于 2024-09-23 19:32:24

630

发布于 2024-09-23 19:32:24

文章被收录于专栏：学习

1.存储结构

https://cplusplus.com/reference/vector/vector/

namespace zone
{
	template<class T>   //需要模板
	class vector
	{
	   public:


       private:

	iterator _start;
	iterator _finish;
	iterator _endofstorage;
    };
}

可见，vector内核是由三个指针实现的

2.默认成员函数

2.1.构造函数

1.初始化列表

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

2.拷贝构造

//v1(v2)
vector(const vector<T>& t)      
	:_start(nullptr)
	, _finish(nullptr)
	, _endofstorage(nullptr)
{
	for (auto& arr : t)
	{
		push_back(arr);
	}
}





// v1=v2
void swap( vector<T>& t)//swap要求参数是&，且不带const
{
	std::swap(_start, t._start);
	std::swap(_finish, t._finish);
	std::swap(_endofstorage, t._endofstorage);
}



vector<T>& operator=(vector<T> t) // 这里不能用const，因为要调用swap，如果是const会造成权限放大
{
	swap(t);
	return *this;
}

3.迭代器区间构造

template <class InputIterator>     //在类模板中再次使用模板
vector(InputIterator first, InputIterator last)
{
	while (first != last)          //记得是!=  不能写成<=,因为存储空间不一定连续！！！！！
	{
		push_back(*first);
		first++;
	}
}                   //可以使用别的类型的迭代器区间去初始化vector，不一定要用vector<T>类型

2.2.析构函数

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

3.容量操作函数

3.1.reserve（设置空间大小）

void reserve(size_t n)
{
	if (n > capacity())
	{
		T* tmp = new T[n];
		size_t sz = size();
		
		if (_start)
		{
			//memcpy(tmp, _start, sizeof(T) * sz);     //若类型为string，memcpy会调用浅拷贝，_start和tmp指向同一块空间，然后delete对于自定义类型调用析构函数，销毁空间
			for (size_t i = 0; i < sz; i++)
			{
				tmp[i] = _start[i];          //若为string类型，相当于s1=s2;赋值，会调用拷贝构造，深拷贝
			}
			delete[]_start;
		}

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

3.2 resize（重新设置vector的长度）

void resize(size_t n, const T& val = T())     //若大于容量则扩容，并用val来填充扩容  //表达式会产生临时变量（！！！），有常性，需要用const &或者不用&
{
	if (n <= size())
	{
		_finish = _start + n;    //缩容
	}
	else
	{
		reserve(n);
		while (_finish < _start + n)
		{
			*_finish = val;
			++_finish;
		}
	}

}

3.3 获取size和capacity

size_t size() const
{
	return _finish - _start;
}

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

4.访问函数

4.1[]

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

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

5.插入类函数

5.1insert

void insert(iterator pos, const T& x)       //在pos位置插入x，
{
	assert(pos >= _start);
	assert(pos <= _finish);

	if (_finish == _endofstorage)
	{
		size_t len = pos - _start;
		reserve(capacity() == 0 ? 4 : capacity() * 2);
		pos = _start + len;//扩容会导致原空间被删除，如果没有len记录长度并重新赋值pos，会导致pos失效（pos依旧指向被删除空间的某个位置而不是新空间的某个位置）
	}


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

5.2 push_back

void push_back(const T& x)
{
	insert(_finish, x);
}

6.删除类函数（erase）

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

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

7.vector 空间增长问题

1.capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2 倍增长的！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。 2.reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。 3.resize在开空间的同时还会进行初始化，影响size。

8.内部刨析

8.1使用memcpy拷贝问题

假设模拟实现的vector中的reserve接口中，使用memcpy进行的拷贝，以下代码会发生什么问题？

int main()
{
 bite::vector<bite::string> v;
 v.push_back("1111");
 v.push_back("2222");
 v.push_back("3333");
 return 0;
}

问题分析： 1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中 2. 如果拷贝的是自定义类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。

8.2 动态二维数组理解

// 以杨慧三角的前n行为例：假设n为5
void test2vector(size_t n)
{
 // 使用vector定义二维数组vv，vv中的每个元素都是vector<int>
 bit::vector<bit::vector<int>> vv(n);
    
    // 将二维数组每一行中的vecotr<int>中的元素全部设置为1
 for (size_t i = 0; i < n; ++i)
 vv[i].resize(i + 1, 1);
    // 给杨慧三角出第一列和对角线的所有元素赋值
 for (int i = 2; i < n; ++i)
 {
   for (int j = 1; j < i; ++j)
  {
  vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
  }
 }
}