Basic implementation of vector

vector模拟实现

memcpy对reserve影响

关于VectorPlease check this website for details（https://m.cplusplus.com/reference/vector/vector/）

1️⃣

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

构造函数

1.默认构造函数：Empty container construction

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

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

3.范围构造函数:构造一个容器,The number and range of its elements [first,last） 相同,Each element is constructed in the same order from the corresponding element in the area

template<class InputIterator>
		vector(InputIterator first, InputIterator last)
			: _start(nullptr)
			, _finish(nullptr)
			, _endofstoage(nullptr)
		{
    
			while (first!=last)
			{
    
				push_back(*first);
					++first;
			}
		}

析构函数

All container elements will be destroyed,and use its allocator to free all storage allocated by the vector

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

运算符=

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

vector<T>& operator=(vector<T> v)
		{
    
			swap(v);
			return *this;
		}

这里swapThis function is used
void swap( vector& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstoage, v._endofstoage);
}

迭代器

1.begin
An iterator pointing to the beginning of the sequence container.
返回An iterator pointing to the first element in the vector.

		iterator begin()
		{
    
			return _start;
		}
		const_iterator begin() const
		{
    
			return _start;
		}

这边我使用了2One is readable thereconstOne is readable and writable Noneconst.
2.end
Iterator of elements past the end of the sequence.
返回一个迭代器,This iterator refers to the post-apocalyptic elements in the vector container.

		iterator end()
		{
    
			return _finish;
		}
		const_iterator end() const
		{
    
			return _finish;
		}

这边我使用了2One is readable thereconstOne is readable and writable Noneconst.

容量

1.size
The number of elements in the container.
Returns the number of elements in the vector.

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

2.capacity
Returns the size of the storage space currently allocated for the vector.

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

3.resize
调整容器大小,使其包含 n 个元素.
如果 n 小于当前容器大小,则内容将减少到其前 n 个元素,delete beyond（并销毁）的元素.

如果 n 大于当前容器大小,is achieved by inserting the required number of elements at the end n size to expand the content.如果指定了 val,则新元素将初始化为 val 的副本,否则,They will be value-initialized.

如果 n 也大于当前容器容量,The allocated storage space is automatically reallocated.

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

		}

4.reserve
The request vector capacity is at least sufficient to contain n 个元素.
如果 n greater than the current vector capacity,则该函数会导致容器重新分配其存储,将其容量增加到 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;

		}

5.运算符[]
访问元素:Returns the position in the vector container n A reference to the element at .

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

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

• 增加功能
  -Add additions, deletions, check, and so on
  1.swap
  通过 x 的内容交换容器的内容,x is another vector object of the same type.

void swap( vector<T>& v)
		{
    
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstoage, v._endofstoage);
		}

2.push_back
at the end of the vector,Adds a new element after its current last element.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);

		}

3.pop_back
Removes the last element in the vector and reduces the container by one.

void pop_back()
		{
    
			/*if (_finish > _start) { --_finish; }*/
			erase(end() - 1);
		}

4.insert插入
By inserting a new element at the specified position before the element.Increase the container size by the number of inserted elements.

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

5.erase擦除
从向量中删除单个元素（位置）或一系列元素（[first,last））.
Returns an iterator pointing to the new position of the element after the last element erased by the function call.如果操作擦除了序列中的最后一个元素,则这是容器结束.

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

			--_finish;

			return pos;
		}

6.clear
Remove all elements from the vector\使容器的大小为 0.

void clear()
		{
    
			_finish=_start;
		}

2️⃣

memcpy对reserve影响

memcpy将一段内存空间中内容原封不动的拷贝到另外一段内存空间中.但如果拷贝的是自定义类型元素,并且
自定义类型元素中涉及到资源管理时,就会出错,因为memcpy的拷贝实际是浅拷贝.We verify by reality.


Through the picture we can find the problem,指向的地址一样,指向的空间释放.Random values ​​are generated.Therefore, we generate wild pointers when we use them.If we have to deal with this problem.You can choose to store through the new space,freeing up the original space.So the problem is solved.

以上是我对vector的理解,可能有所不足.