vector的基本实现

vector模拟实现

memcpy对reserve影响

关于Vector的介绍具体的请查看该网站（https://m.cplusplus.com/reference/vector/vector/）

1️⃣

• 基本框架
  -构造、析构、运算符、迭代器、容量、运算符

构造函数

1.默认构造函数：空容器构造

vector()
			:_start(nullptr)
			,_finish(nullptr)
			,_endofstoage(nullptr)
		{}
1
2
3
4
5

2.填充构造：n个元素的容器，每个元素都是val的副本

vector(size_t n, const T& val = T())
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstoage(nullptr)
		{
			reserve(n);
			for (size_t i = 0; i < n; ++i)
			{
				push_back(val);
			}
		}
1
2
3
4
5
6
7
8
9
10
11

3.范围构造函数:构造一个容器，其元素数与范围 [first，last） 相同，每个元素都按相同的顺序从该区域中的相应元素构造

template<class InputIterator>
		vector(InputIterator first, InputIterator last)
			: _start(nullptr)
			, _finish(nullptr)
			, _endofstoage(nullptr)
		{
			while (first!=last)
			{
				push_back(*first);
					++first;
			}
		}
1
2
3
4
5
6
7
8
9
10
11
12

析构函数

将销毁所有容器元素，并使用其分配器释放矢量分配的所有存储容量

~vector()
		{
			if (_start)
			{
				delete[] _start;
				_start = _finish = _endofstoage = nullptr;
			}
		}
1
2
3
4
5
6
7
8

运算符=

将新内容分配给容器，替换其当前内容，并相应地修改其大小

vector<T>& operator=(vector<T> v)
		{
			swap(v);
			return *this;
		}
1
2
3
4
5

这里swap采用的是该函数
void swap( vector& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstoage, v._endofstoage);
}

迭代器

1.begin
指向序列容器开头的迭代器。
返回指向向量中第一个元素的迭代器。

		iterator begin()
		{
			return _start;
		}
		const_iterator begin() const
		{
			return _start;
		}
1
2
3
4
5
6
7
8

这边我使用了2种一种是可读的有const一种是可读可写的无const。
2.end
序列末尾后元素的迭代器。
返回一个迭代器，该迭代器引用矢量容器中的末日后元素。

		iterator end()
		{
			return _finish;
		}
		const_iterator end() const
		{
			return _finish;
		}
1
2
3
4
5
6
7
8

这边我使用了2种一种是可读的有const一种是可读可写的无const。

容量

1.size
容器中的元素数。
返回矢量中的元素数。

size_t size() const
		{
			return _finish - _start;
		}
1
2
3
4

2.capacity
返回当前为向量分配的存储空间的大小。

size_t capacity() const
		{
			return _endofstoage - _start;
		}
1
2
3
4

3.resize
调整容器大小，使其包含 n 个元素。
如果 n 小于当前容器大小，则内容将减少到其前 n 个元素，删除超出（并销毁）的元素。

如果 n 大于当前容器大小，则通过在末尾插入所需数量的元素以达到 n 的大小来扩展内容。如果指定了 val，则新元素将初始化为 val 的副本，否则，它们将进行值初始化。

如果 n 也大于当前容器容量，则会自动重新分配分配的存储空间。

void resize(size_t n,T val=T())
		{
			if (n > capacity())
			{
				reserve(n);
			}
			if (n > size())
			{
				while (_finish < _start + n)
				{
					*_finish=val;
						++_finish;//不理解
				}
			}
			else
			{
				_finish=_start+n;
			}

		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

4.reserve
请求向量容量至少足以包含 n 个元素。
如果 n 大于当前矢量容量，则该函数会导致容器重新分配其存储，将其容量增加到 n（或更大）。但不会进行初始化。这点和resize不同。

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

		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

5.运算符[]
访问元素:返回对矢量容器中位置 n 处的元素的引用。

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

		const T& operator[](size_t pos) const
		{
			assert(pos < size());
			return _start[pos];
		}
1
2
3
4
5
6
7
8
9
10
11

• 增加功能
  -增加增删查改等
  1.swap
  通过 x 的内容交换容器的内容，x 是同一类型的另一个向量对象。

void swap( vector<T>& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstoage, v._endofstoage);
		}
1
2
3
4
5
6

2.push_back
在矢量的末尾，在其当前的最后一个元素之后添加一个新元素。val 的内容被复制（或移动）到新元素。

void push_back(const T& x)
		{
		/*	if (_finish == _endofstoage)
			{
				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(_endofstoage);
			}
			*_finish = x;
			++_finish;*/
			insert(end(),x);

		}
1
2
3
4
5
6
7
8
9
10
11
12

3.pop_back
删除矢量中最后一个元素并且容器减少一给。

void pop_back()
		{
			/*if (_finish > _start)
			{
				--_finish;
			}*/
			erase(end() - 1);
		}
1
2
3
4
5
6
7
8

4.insert插入
通过在元素之前的指定位置插入新元素.将容器大小增加插入的元素数。

		iterator insert(iterator pos, const T& x)
		{
			assert(pos >= _start && pos <= _finish);
			if (_finish == _endofstoage)
			{
				size_t n = pos - _start;
				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newCapacity);
				pos = _start + n;
			}
			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				--end;
			}
			*pos = x;
			++_finish;
			return pos;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

5.erase擦除
从向量中删除单个元素（位置）或一系列元素（[first，last））。
返回时指向函数调用擦除的最后一个元素后面的元素的新位置的迭代器。如果操作擦除了序列中的最后一个元素，则这是容器结束。

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

			--_finish;

			return pos;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

6.clear
从矢量中删除所有元素\使容器的大小为 0。

void clear()
		{
			_finish=_start;
		}
1
2
3
4

2️⃣

memcpy对reserve影响

memcpy将一段内存空间中内容原封不动的拷贝到另外一段内存空间中。但如果拷贝的是自定义类型元素，并且
自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。我们通过实际进行验证。


通过图我们可以发现问题，指向的地址一样，指向的空间释放。产生了随机值。因此我们在使用的时候产生了野指针。我们如果要处理这个问题。可以选择通过新空间来存放，在释放原有空间。这样问题就处理了。

以上是我对vector的理解，可能有所不足。