当前位置：首页 > article >正文

vector结构刨析与模拟实现

article 2025/2/24 3:02:37

1.引言

2.C++模拟实现

2.1模拟实现构造函数

1）直接构造

2）拷贝构造

3）单一赋值构造

4）迭代器构造

2.2模拟实现析构函数

2.3模拟实现其他常规函数

1）capacity函数

2）size函数

3）begin/end函数

4）reserve函数

5）resize函数

6）push_back函数

7）pop_back函数

8）insert函数

9）erase函数

2.4模拟实现操作符重载函数

1）赋值操作符重载（深拷贝）

2）[]访问操作符重载（读写/只读）

3.完整vector

1.引言

先来说说为什么要模拟实现库里的vector？

我认为，模拟实现vector有以下几个意义和好处：

学习目的：通过模拟实现库里的vector，可以更深入地理解和学习该数据结构的内部实现原理。这有助于加深对数据结构和算法的理解，提高编程能力和思维能力。
实际应用：在某些情况下，可能需要针对特定需求对vector进行自定义的扩展或优化。通过模拟实现库里的vector，可以根据具体需求自定义实现相关功能，满足实际应用的需要。
提升技术水平：通过模拟实现库里的vector，可以锻炼自己的编程能力和逻辑思维能力，提升自己的技术水平和代码能力。同时也可以通过与标准库的vector进行对比测试，验证自己实现的正确性和效率。

2.C++模拟实现

提前声明，由于vector中不同类型的函数重载太多太杂，且内存池等内容太过超前，本篇仅仅模拟实现简单的构造，析构，操作符重载，深浅拷贝，增删查改等部分函数的介绍，感谢读者的支持！

建议先创建一个vector.hpp头文件，单独创建一个命名空间，防止已经展开了std的命名空间，实现的vector与库中vector发生冲突。

我们就定义命名空间为drw，先设置一个模板类T，将T*重命名成iterator迭代器，将vector的私有成员变量分别定义为：

iterator _start;
iterator _finish;
iterator _end_of_storage;

为什么是这样子的私有成员变量？我们截取一部分STL中关于vector的实现源码看看：

protected:
  typedef simple_alloc<value_type, Alloc> data_allocator;
  iterator start;
  iterator finish;
  iterator end_of_storage;
  void insert_aux(iterator position, const T& x);
  void deallocate() {
    if (start) data_allocator::deallocate(start, end_of_storage - start);
  }

看来标准库中的vector就是这么实现的，那么此处沿用库中的写法。

2.1模拟实现构造函数

1）直接构造

思路：

因为这里的私有成员变量都是iterator迭代器类型的，其本质就是一种指针，那么这里用初始化列表置为nullptr空指针就行
至于申请空间这里先不做处理

实现：

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

2）拷贝构造

思路：

拷贝构造，即用vector构造新的vector，这里就需要考虑开辟空间的问题了
先进行一下初始化，使用初始化列表，这里与直接构造相同
再开辟出参数vector t相同的空间用来存放数据，使用[]操作符重载函数和=操作符重载函数依次填入新空间，这两种函数的实现放在后面！
修改_finish和_end_of_storage的值

实现：

//拷贝构造函数
vector(const vector<T>& t)
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	_start = new T[t.capacity()];
	for (size_t i = 0; i < t.size(); i++)
	{
		*(_start + i) = t[i];
	}
	_finish = _start + t.size();
	_end_of_storage = _start + t.capacity();
}

补充：

为什么要使用[]操作符重载函数和=操作符重载函数进行赋值，而不像string的模拟实现中的使用memcpy直接拷贝呢？

答案：因为如果vector中装的是string这种自定义类型的成员的话，那么直接memcpy就会连同地址一并拷贝，这种拷贝是浅拷贝，有多个指针指向同一块空间，那么程序结束就会调用两次析构函数，会是报错的！

3）单一赋值构造

思路：

先使用初始化列表进行初始化
再调用resize函数调整vector的存储大小以及存储内容，resize放在后面讲解

实现：

vector(int n, const T& t)
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	resize(n, t);
}

补充：

这里使用的是int n，STL标准库里也是这样实现的，那么为什么不使用size_t呢？

这是因为如果我们直接传参10，1代表用10个1构造一个vector，但是编译器在调用构造函数时会去调用接下来要讲到的迭代器构造函数，而不会调用含有参数size_t的构造函数，这是因为将int类型的10转换为size_t需要一定代价，而直接将10看作迭代器的代价更小，因此这里使用的是int类型。

4）迭代器构造

思路：

在类外已经有模板类T的情况下，我们在类内部再定义一个Inputiterator模板类，这是为了接收传过来的各种迭代器
使用初始化列表进行初始化
调用push_back函数直接将解引用的成员进行尾插即可，尾插函数后面讲解

实现：

template<class Inputiterator>
vector(Inputiterator begin, Inputiterator end)
	:_start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	while (begin != end)
	{
		push_back(*begin++);
	}
}

2.2模拟实现析构函数

思路：

析构函数较简单，如果_start存在的话就delete[] 数据
将三个私有成员变量赋值nullptr

实现：

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

2.3模拟实现其他常规函数

1）capacity函数

思路：

该函数会返回vector中容量大小，我们直接将_end_of_storage-_start就行

实现：

size_t capacity()const//const能带就带不然会出错
{
	return _end_of_storage - _start;
}

2）size函数

思路：

size函数是返回vector中已经占用的空间容量大小，直接将_finish-_start就行

实现：

size_t size()const//const修饰的vector调用const修饰函数
{
	return _finish - _start;
}

3）begin/end函数

思路：

begin函数用来返回第一个成员迭代器位置，就代表迭代器_start的值
end函数返回最后一个成员下一个位置的迭代器，就代表迭代器_finish的值
begin/end代表左闭右开的区间
分别有两个版本，分别是可读可写版本和可读不可写版本
不要忘记在vector中提前重定义

实现：

iterator begin()
{
	return _start;
}

iterator end()
{
	return _finish;
}

const_iterator begin()const
{
	return _start;
}

const_iterator end()const
{
	return _finish;
}

4）reserve函数

思路：

reserve函数用来提前为vector开辟一块空间，可以减少拷贝的次数，提高代码的运行效率
如果参数大于capacity时就扩容，如果小于在windows环境下不会缩容
开辟一块大小为n的新空间，先用sz记录一下原vector的size大小以便于后续改变新vector的_finish
如果_start存在的话就进行赋值拷贝，这里不能使用memcpy与前面拷贝构造一样的原理
将_start赋值新地址，前面的sz派上用场，_finish就是_start+sz，_end_of_storage就是_start+n

实现：

void reserve(size_t n)
{
	if (n > capacity())
	{
		iterator newstart = new T[n];
		//memcpy(newstart, _start, sizeof(T) * size());
		//这里memcpy发生的是浅拷贝，为了防止自定义类型浅拷贝，采用赋值形式，这样可以调用赋值重载
		size_t sz = size();
		if (_start)
		{
			for (size_t i = 0; i < size(); i++)
			{
				*(newstart + i) = *(_start + i);
			}
			delete[] _start;
		}
		_start = newstart;
		_finish = _start + sz;
		_end_of_storage = _start + n;
	}
}

5）resize函数

思路：

与reserve有异曲同工之处，在第一个参数大于原vector的_capacity之后再扩容，如果小于是不需要扩容的，这时候代表删除数据
第一种不需要扩容的情况：删除数据，直接将_finish进行调整就行了
第二种需要扩容的情况：直接用reserve函数扩容，再初始化新开辟的空间，这里有默认缺省值为T()，(这里把一些内置类型上升到类，匿名对象赋值默认去调用他们的拷贝构造函数)
将多开辟出来的空间赋值t即可

实现：

void resize(size_t n, const T& t = T())
{
	if (n <= size())
	{
		_finish = _start + n;
	}
	else
	{
		reserve(n);
		while (_finish != _start + n)
		{
			*_finish++ = t;
		}
	}
}
//匿名对象，以便任何类型都可以调用拷贝构造
//这里内置类型也做了处理，默认有拷贝构造函数，如int默认为0

6）push_back函数

思路：

首先需要检查扩容，如果_finish == _end_of_storage需要扩容，这里采用简单的扩容方式：二倍扩容，如果提前vector没有任何内容，capacity为0，那么就扩容4
对最后一个元素下一个位置赋值尾插元素

实现：

void push_back(const T& t)
{
	if (_finish == _end_of_storage)
	{
		size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newcapacity);
	}
	*_finish++ = t;
}

7）pop_back函数

思路：

直接将_finish--即可，简单实现

实现：

void pop_back()
{
	_finish--;
}

8）insert函数

思路：

insert函数有很多重载类型，这里只实现指定迭代器位置插入数据
首先检查pos位置是否合法
再需要检查扩容，如果_finish == _end_of_storage需要扩容，请注意这里传参的pos位置是相对原来的vector的，如果扩容那么就改变了vector的地址，正确的pos位置也应该发生改变，切忌使用原来错误的pos！为了解决这个问题用len记录一下原来pos相对于_start的位置即可
将数据后移，插入即可
最后是返回值问题：这里要返回插入的数据的位置，因为如果发生扩容pos就改变了，如果使用者还需要使用，那么就需要新的pos地址

实现：

iterator insert(iterator pos, const T& t)
{
	assert(_start <= pos && pos < _finish);
	if (_finish == _end_of_storage)
	{
		size_t len = pos - _start;
		size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newcapacity);
		pos = _start + len;
	}
	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *end;
		end--;
	}
	*pos = t;
	_finish++;
	return pos;
}
//这里如果要扩容，pos指向的地址在释放空间后就失效了，所以要先记录位置
//为了防止外部迭代器失效，返回一个迭代器指针更新外部的迭代器

9）erase函数

思路：

首先检查要删除的位置是否合法
将pos位置后面的成员依次往前移动一格即可

实现：

iterator erase(iterator pos)
{
	assert(_start <= pos && pos < _finish);
	iterator it = pos + 1;
	while (it != _finish)
	{
		*(it - 1) = *it;
		it++;
	}
	_finish--;
	return pos;
}
//删除也有迭代器失效的问题，调用erase之后就不能再对迭代器进行访问了
//vs上直接通过断言拒绝，但g++上某些可以跑过，这里返回删除的下一个位置的迭代器

补充：

erase之后的pos指针就不能够再次使用了，visual studio通过断言直接拒绝了这种访问操作！

2.4模拟实现操作符重载函数

1）赋值操作符重载（深拷贝）

思路：

直接用传参的方式去拷贝构造一个参数vector t
将t与*this的三个私有成员变量进行交换
函数栈帧销毁后，原vector自动调用析构函数销毁

实现：

vector<T>& operator=(vector<T> t)
{
	swap(_start,t._start);
	swap(_finish, t._finish);
	swap(_end_of_storage, t._end_of_storage);
	return *this;
}

2）[]访问操作符重载（读写/只读）

思路：

对pos位置检查一下是否合法
解引用对应位置的成员，返回即可

实现：

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

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

3.完整vector

这里给出完整的实现代码：

#include<iostream>
#include<string.h>
#include<vector>
#include<assert.h>
#include<algorithm>
using namespace std;

namespace drw
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;
		vector()
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
		}

		//拷贝构造函数
		vector(const vector<T>& t)
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			_start = new T[t.capacity()];
			for (size_t i = 0; i < t.size(); i++)
			{
				*(_start + i) = t[i];
			}
			_finish = _start + t.size();
			_end_of_storage = _start + t.capacity();
		}

		vector(int n, const T& t)//不用size_t,否则会直接匹配迭代器构造函数
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			resize(n, t);
		}

		template<class Inputiterator>
		vector(Inputiterator begin, Inputiterator end)
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			while (begin != end)
			{
				push_back(*begin++);
			}
		}

		vector<T>& operator=(vector<T> t)
		{
			swap(_start,t._start);
			swap(_finish, t._finish);
			swap(_end_of_storage, t._end_of_storage);
			return *this;
		}

		iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		const_iterator begin()const
		{
			return _start;
		}

		const_iterator end()const
		{
			return _finish;
		}

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

		size_t capacity()const//const能带就带不然会出错
		{
			return _end_of_storage - _start;
		}
		
		size_t size()const//const修饰的vector调用const修饰函数
		{
			return _finish - _start;
		}

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

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

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				iterator newstart = new T[n];
				//memcpy(newstart, _start, sizeof(T) * size());
				//这里memcpy发生的是浅拷贝，为了防止自定义类型浅拷贝，采用赋值形式，这样可以调用赋值重载
				size_t sz = size();
				if (_start)
				{
					for (size_t i = 0; i < size(); i++)
					{
						*(newstart + i) = *(_start + i);
					}
					delete[] _start;
				}
				_start = newstart;
				_finish = _start + sz;
				_end_of_storage = _start + n;
			}
		}

		void push_back(const T& t)
		{
			if (_finish == _end_of_storage)
			{
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newcapacity);
			}
			*_finish++ = t;
		}

		void pop_back()
		{
			_finish--;
		}

		iterator insert(iterator pos, const T& t)
		{
			assert(_start <= pos && pos < _finish);
			if (_finish == _end_of_storage)
			{
				size_t len = pos - _start;
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newcapacity);
				pos = _start + len;
			}
			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				end--;
			}
			*pos = t;
			_finish++;
			return pos;
		}
		//这里如果要扩容，pos指向的地址在释放空间后就失效了，所以要先记录位置
		//为了防止外部迭代器失效，返回一个迭代器指针更新外部的迭代器

		iterator erase(iterator pos)
		{
			assert(_start <= pos && pos < _finish);
			iterator it = pos + 1;
			while (it != _finish)
			{
				*(it - 1) = *it;
				it++;
			}
			_finish--;
			return pos;
		}
		//删除也有迭代器失效的问题，调用erase之后就不能再对迭代器进行访问了
		//vs上直接通过断言拒绝，但g++上某些可以跑过，这里返回删除的下一个位置的迭代器

		void resize(size_t n, const T& t = T())
		{
			if (n <= size())
			{
				_finish = _start + n;
			}
			else
			{
				reserve(n);
				while (_finish != _start + n)
				{
					*_finish++ = t;
				}
			}
		}
		//匿名对象，以便任何类型都可以调用拷贝构造
		//这里内置类型也做了处理，默认有拷贝构造函数，如int默认为0

	private:
		iterator _start;
		iterator _finish;//指向最后一个元素下一个位置
		iterator _end_of_storage;
	};
}

查看全文

http://www.kler.cn/a/558348.html