vector模拟实现

需要注意的是，insert插入数据时需要将后面的数据一个个的挪动，这就导致除了尾插以外的插入效率低下，使用时需要注意。reserve只有一个形参n，并且reserve只会在n大于容器空间时进行扩容，其它情况下不做处理。当n小于容器空间时进行缩容，并且在缩容的过程中进行可能的数据删除操作。需要注意的是，在对成员变量包含指针类型的对象时需要警惕使用memcpy造成浅拷贝问题。删除元素后同样需要将后面的

风居住的街道837

508人浏览 · 2025-09-01 17:10:34

风居住的街道837 · 2025-09-01 17:10:34 发布

4、pop_back、empty和clear

一、vector容器中的迭代器

vector中的迭代器可以直接使用指针来实现。

template <class T>
class vector
{
	typedef T* iterator;
	typedef const T* const_iterator；
  //……………………
}；

并且在vector源代码里，vector类的成员变量并不像是以往的_str、_size、_capacity三件套，而是：

	private:
		iterator _start;
		iterator _finish;
		iterator _endofstorage;

上面三个成员变量全是迭代器类型，_start表示数据存储的起始位置；_finish指向存储数据的后一个位置；_endofstorage指向vector有效空间的后一个位置。（迭代器的前闭后开）

二、常用接口

1、push_back

当容器空间足够时插入数据，不够时进行扩容在插入数据。

		void push_back(const T& x)
		{
			if (_finish == _endofstorage)//判断是否需要扩容
			{
				reserve(capacity() == 0 ? 4:2 * capacity());
			}
			*_finish = x;
			_finish++;
		}

2、end、begin迭代器

注意一下存在const和非const版本

		iterator begin()
		{
			return _start;//返回值是编译器拷贝的一个临时对象！
		}

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

		const_iterator end()const
		{
			return _finish;
		}

3、size和capacity

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

4、pop_back、empty和clear

pop_back在实现时需要注意容器内是否存有数据，如果对空容器进行删除操作会产生越界行为。

clear清理容器数据只用将_finish迭代器指向_start。

		void pop_back()
		{
			if(!empty())
			_finish--;
		}

		bool empty()
		{
			return _start == _finish;
		}

		void clear()
		{
			_finish = _start;
		}

5、resize

我们先看resize的两个传参：n表示期望的容器大小；val是期望的初始值。

当n大于容器空间时进行扩容；当n小于容器空间时进行缩容，并且在缩容的过程中进行可能的数据删除操作。

val的缺省值value_type()使用到了匿名对象这个知识点。另外，C++ 标准库为内置类型提供了类风格的操作接口和包装类。

这意味着我们也可以使用匿名对象创建一个内置类型对象。

例如：

resize实现代码：

	//C++中内置类型也有构造函数
	//例如： int a(19);int b=int();int c=int(2);
	void resize(size_t n, T val = T())//创建匿名对象作为缺省值，实现泛型编程
	{
		if (n > capacity())
		{
			reserve(n); //复用reserve扩容
			while (_finish != _start + n)//初始化
			{
				*_finish = val;
				*_finish++;
			}
		}
		else
		{
			_finish = _start + n;
		}
	}

6、reserve

resize跟reserve长得很像，但两者的功能又存在不少差别。

reserve只有一个形参n，并且reserve只会在n大于容器空间时进行扩容，其它情况下不做处理。

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				T* tmp = new T[n];
				size_t oldsize = size();
                //注意：因为后面_start会发生改变但是_finish还是旧值，
				//这样size()函数就发生逻辑错误，故需要提前存储原本的size个数
				if (_start)
				{
					//memcpy(tmp, _start, sizeof(T) * oldsize);
					//当使用 memcpy 对包含指针成员的自定义类型对象进行复制时，
					// 它只会按字节原样复制内存内容。
					// 这就导致源对象和目标对象中的指针成员指向同一块内存区域，形成浅拷贝。

					//解决方案：
					for (size_t i = 0; i < oldsize; i++)
					{
						*(tmp + i) = *(_start + i);
					}
					delete[]_start;
				}
				_start = tmp;
				_finish = _start + oldsize;
				_endofstorage = _start + n;
			}
		}

7、insert

我们目前只看第一个版本。

insert是在position位置添加一个元素val。

需要注意的是，insert插入数据时需要将后面的数据一个个的挪动，这就导致除了尾插以外的插入效率低下，使用时需要注意。

		iterator insert(iterator pos,const T& val)
		{
			assert(_finish >= _start);
			assert(_finish <= _endofstorage);

			size_t npos = pos - _start;

			if (_finish >= _endofstorage)
			{
				reserve(capacity() == 0 ? 4 : 2 * capacity());
			}

			//扩容后_start、_finish、_endofstorage都会发生改变，（因为复用了reservve）
            //但是pos指针迭代器并没有发生改变就导致迭代器失效
			//故需要重新定位pos迭代器
			pos = _start + npos;
			iterator end = _finish - 1;
			while (end>=pos)
			{
				*(end + 1) = *end;
				end--;
			}
			*pos = val;
			_finish++;
			return pos;
		}

8、erase

我们目前只看第一个版本。删除指定位置的元素。

删除元素后同样需要将后面的元素一个一个的往前挪，导致除尾删以外的删除效率不高。

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

			iterator old = pos + 1;

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