开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> 【C++STL】第二篇：vector类的介绍及模拟实现 -> 正文阅读

[C++知识库]【C++STL】第二篇：vector类的介绍及模拟实现

一、标准库中的vector类

vector类的文档介绍
1、vector是表示可变大小数组的序列容器。
2、就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
3、本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
4、vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
5、因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
6、与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和forward_lists统一的迭代器和引用更好。

二、vector的使用及模拟实现

📖vector()

vector()	无参构造，构造一个空容器，没有元素

简单的模拟实现，通过vector()来构造一个空的容器，没有元素

模拟实现：

#include<iostream>
using namespace std;
namespace cxy
{
	template <class T>//类模板
	class vector
	{
		public:
			typedef T* iterator;
			typedef const T* conat_iterator;
			vector()
				:_start(nullptr)
				, _finish(nullptr)
				, _endOfStorage(nullptr)
			{}
		private:
			iterator _start;
			iterator _finish;
			iterator _endOfStorage;
	};
}

_start：指向vector的第一个元素。
_finish：指向vector最后一个元素的后一个位置。
__endOfStorage：指向vector容量的后面位置。
在这里插入图片描述

📖vector（size_type n, const value_type& val = value_type()）

vector（size_type n, const value_type& val = value_type()）	构造并初始化n个val

构建一个带有n元素的容器。每个元素都是val的复制品。

使用：

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	vector<int> v1(10,1);
	for(auto& e:v1)
	{
		cout<<e<<" ";
	}
	cout<<endl;
	return 0;
}

在这里插入图片描述
模拟实现：

#include<iostream>
using namespace std;
namespace cxy
{
	template <class T>//类模板
	class vector
	{
		public:
			typedef T* iterator;
			typedef const T* conat_iterator;
			
			vector(size_t n, const T& val = T())//T()缺省参数//拷贝构造
				:_start(nullptr)
				, _finish(nullptr)
				, _endOfStorage(nullptr)
			{
				T* tmp = new T[n];
				_start = tmp;
				_finish = _start + n;
				_endOfStorage = _start + n;
				T* it = _start;
				while (it!=_finish)
				{
					*it = val;
					it++;
				}
			}
		private:
			iterator _start;
			iterator _finish;
			iterator _endOfStorage;
	};
}

📖vector (const vector& x)

vector (const vector& x)	拷贝构造

以相同的顺序构建一个容器，其中每个元素的副本为x。

使用：

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	vector<int> v1(10,1);
	vector<int> v2(v1);
	for(auto& e:v2)
	{
		cout<<e<<" ";
	}
	cout<<endl;
	return 0;
}

在这里插入图片描述
模拟实现：

#include<iostream>
using namespace std;
namespace cxy
{
	template <class T>//类模板
	class vector
	{
		public:
			typedef T* iterator;
			typedef const T* conat_iterator;
			
			vector(const vector<T>& v)
				:_start(nullptr)
				, _finish(nullptr)
				, _endOfStorage(nullptr)
			{
				T*temp = new T[v.capacity()];
				_start = temp;
				for (size_t i = 0;i<v.size();i++)
				{
					_start[i] = v._start[i];
				}	
				_finish = _start + v.size();
				_endOfStorage = _start + v.size();
			}			
		private:
			iterator _start;
			iterator _finish;
			iterator _endOfStorage;
	};
}

📖~vector()

~vector()	清理数据

模拟实现：

#include<iostream>
#include<assert.h>
using namespace std;
namespace cxy
{
	template <class T>//类模板
	class vector
	{
		public:
			typedef T* iterator;
			typedef const T* conat_iterator;
			~vector()
			{
				assert(!empty());
				delete[]_start;
				_start = _finish = _endOfStorage = nullptr;
			}			
		private:
			iterator _start;
			iterator _finish;
			iterator _endOfStorage;
	};
}

📖 iterator begin()和iterator const_iterator begin()

iterator begin()	获取第一个数据位置
iterator const_iterator begin()	获取第一个数据位置，但是不能修改

模拟实现：

#include<iostream>
#include<assert.h>
using namespace std;
namespace cxy
{
	template <class T>//类模板
	class vector
	{
		public:
			typedef T* iterator;
			typedef const T* conat_iterator;
			iterator begin()
			{
				return _start;
			}
			conat_iterator begin()const
			{
				return _start;
			}
		private:
			iterator _start;
			iterator _finish;
			iterator _endOfStorage;
	};
}

在这里插入图片描述

📖iterator end()和iterator const_iterator end()

iterator end()	获取最后一个数据位置
iterator const_iterator end()	获取最后一个数据位置，但是不能修改

模拟实现：

#include<iostream>
#include<assert.h>
using namespace std;
namespace cxy
{
	template <class T>//类模板
	class vector
	{
		public:
			typedef T* iterator;
			typedef const T* conat_iterator;
			iterator end()
			{
				return _finish;
			}
			conat_iterator end()const
			{
				return _finish;
			}
		private:
			iterator _start;
			iterator _finish;
			iterator _endOfStorage;
	};
}

在这里插入图片描述

📖size() const

size() const;	获取数据个数

返回vector中的元素数。这是载体中实际物体的数量，不一定等于其存储容量。

使用：

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	vector<int> v1(10,1);
	cout<<v1.size()<<endl;
	return 0;
}

在这里插入图片描述
模拟现实：

#include<iostream>
#include<assert.h>
using namespace std;
namespace cxy
{
	template <class T>//类模板
	class vector
	{
		public:
			typedef T* iterator;
			typedef const T* conat_iterator;
			size_t size()const
			{
				return _finish - _start;
			}
		private:
			iterator _start;
			iterator _finish;
			iterator _endOfStorage;
	};
}

📖 capacity() const

capacity() const	获取容量大小

返回目前分配给vector的存储空间的大小

模拟实现：

#include<iostream>
#include<assert.h>
using namespace std;
namespace cxy
{
	template <class T>//类模板
	class vector
	{
		public:
			typedef T* iterator;
			typedef const T* conat_iterator;
			size_t capacity()const
			{
				return _endOfStorage - _start;
			}
		private:
			iterator _start;
			iterator _finish;
			iterator _endOfStorage;
	};
}

📖empty() const

empty() const	判断是否为空

返回vector是否为空（即其大小是否为0）

模拟实现：

#include<iostream>
#include<assert.h>
using namespace std;
namespace cxy
{
	template <class T>//类模板
	class vector
	{
		public:
			typedef T* iterator;
			typedef const T* conat_iterator;
			bool empty()
			{
				return _start == _finish;
			}
		private:
			iterator _start;
			iterator _finish;
			iterator _endOfStorage;
	};
}

📖void reserve (size_type n)

void reserve (size_type n)	改变vector的capacity

要求vector容量至少足以包含n元素。
如果 n 大于当前vector容量，则函数会导致容器重新分配其存储，使其容量增加到 n（或更高）。
在所有其他情况下，函数调用不会导致重新分配，并且vector容量不受影响。
此功能对矢量大小没有影响，无法更改其元素.

使用：

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	vector<int> v1(10,1);
	cout<<"vector当前容量："<<v1.capacity()<<endl;
	for (auto& e : v1)
	{
		cout << e << " ";
	}
	cout<<endl;
	v1.reserve(12);
	cout<<"情况一，12>vector当前容量"<<v1.capacity()<<endl;
	for (auto& e : v1)
	{
		cout << e << " ";
	}
	cout<<endl;
	cout <<"用reserve扩容不会改变vector里的元素" << endl;
	return 0;
}

在这里插入图片描述

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	vector<int> v1(10,1);
	cout<<"vector当前容量："<<v1.capacity()<<endl;
	v1.reserve(8);
	cout<<"情况一，8<vector当前容量"<<v1.capacity()<<endl;
	cout <<"当n<vector当前容量,vector容量不受影响" << endl;
	cout<<endl;
	return 0;
}

在这里插入图片描述
模拟实现：

#include<iostream>
#include<assert.h>
using namespace std;
namespace cxy
{
	template <class T>//类模板
	class vector
	{
		public:
			typedef T* iterator;
			typedef const T* conat_iterator;
			void reserve(size_t n)//temp是临时变量，当这个函数执行结束时，temp自动销毁
			{
				if (n > capacity())
				{
					size_t sz=size();
					T* tmp = new T(n);//开辟n个T类型的连续的空间
					if (_start)
					{
						for (size_t i = 0; i < sz; i++)
						{
							tmp[i] = _start[i];//这里要用for循环来赋值
						}
						delete[]_start;
					}
					//指针指向新开辟的空间
					_start = tmp;
					_finish = _start + sz;
					_endOfStorage = _start + n;
			}
		}
		private:
			iterator _start;
			iterator _finish;
			iterator _endOfStorage;
	};
}

注意：在实现reserve()时，我用了for循环来给新开辟的空间赋值，而不是用memcpy。
如果在reserve中使用memcpy来给新开辟的空间赋值的话，在一些情况下会有bug。例如，当vector中是存放着字符串时，然后用reserve开辟更多的空间，就会时新开辟的空间里的_start指向一处被释放的空间，原数据被清理了。
在这里插入图片描述
memcpy会把指向string的指针拷贝到新开辟的空间中，但不会把存放字符串的空间一起拷贝下来，使得在reserve后，旧空间存放字符串的数据被清理了。
而使用for循环来赋值，则是因为通过赋值运算符来调用string中的重载来进行深拷贝。
总结：T如果是内置类型或者是浅拷贝自定义类型（Date），我们可以用memcpy。但T是深拷贝自定义类型（string）就不能使用memcpy，应使用 for+赋值。

📖void resize (size_type n, value_type val = value_type())

void resize (size_type n, value_type val = value_type())	改变vector的size

调整容器大小，使其包含n元素。
如果 n 小于当前容器大小，则内容将减少到其第一个 n 元素，删除超出（并销毁它们）的内容。
如果 n 大于当前容器大小，则内容通过在末端插入尽可能多的元素来扩展，以达到 n 的大小。
如果Val被指定，则新元素将初始化为val的副本，否则，它们将具有价值初始化。如果 n 也大于当前的容器容量，则会自动重新分配分配的存储空间。

模拟实现：

#include<iostream>
#include<assert.h>
using namespace std;
namespace cxy
{
	template <class T>//类模板
	class vector
	{
		public:
			typedef T* iterator;
			typedef const T* conat_iterator;
			void resize(size_t n, const T& value = T())
			{
				if (n < size())
				{
					_finish = _start + n;
				}
			else
				{
					if (n>capacity())
					{
						reserve(n);
					}
					while (_finish<_start+n)
					{
						*_finish = value;
						++_finish;
					}
				}
			}	
		private:
			iterator _start;
			iterator _finish;
			iterator _endOfStorage;
	};
}

📖void push_back (const value_type& val)

void push_back (const value_type& val)	尾插

在vector末端添加一个新的元素，在它当前的最后一个元素之后

代码实现：

#include<iostream>
#include<assert.h>
using namespace std;
namespace cxy
{
	template <class T>//类模板
	class vector
	{
		public:
			typedef T* iterator;
			typedef const T* conat_iterator;
			void push_back(const T& x)
			{
				if (_finish == _endOfStorage)
				{
					int _capacity = 0 == capacity() ? 4 : capacity() * 2;
					reserve(_capacity);
				}
				*_finish = x;
				_finish++;
		}
		private:
			iterator _start;
			iterator _finish;
			iterator _endOfStorage;
	};
}

📖void pop_back()

void pop_back()	尾删

去除载体中的最后一个元素，有效地将容器大小减小一个。

模拟实现：

#include<iostream>
#include<assert.h>
using namespace std;
namespace cxy
{
	template <class T>//类模板
	class vector
	{
		public:
			typedef T* iterator;
			typedef const T* conat_iterator;
			void pop_back()
			{	
				if (empty())
				--_finish;
			}
		private:
			iterator _start;
			iterator _finish;
			iterator _endOfStorage;
	};
}

在这里插入图片描述

📖iterator insert (iterator position, const value_type& val)

iterator insert (iterator position, const value_type& val)	在position之前插入val

模拟实现：

#include<iostream>
#include<assert.h>
using namespace std;
namespace cxy
{
	template <class T>//类模板
	class vector
	{
		public:
			typedef T* iterator;
			typedef const T* conat_iterator;
		void insert(iterator pos, const T& v)
		{
			assert(pos <= _finish);
			if (_finish==_endOfStorage)
			{
				size_t len = pos - _start;
				size_t _capacity = 0 == _capacity() ? 1 : capacity() * 2;

				reserve(_capacity);
				pos = _start + len;
			}
			iterator end = _fiish - 1;
			while (end>=pos)
			{
				*(end + 1) = *end;
				--end;
			}
			*pos = v;

			_finish++;
		}
		private:
			iterator _start;
			iterator _finish;
			iterator _endOfStorage;
	};
}

📖iterator erase(iterator pos)

iterator erase(iterator pos)	删除position位置的数据

模拟实现：

#include<iostream>
#include<assert.h>
using namespace std;
namespace cxy
{
	template <class T>//类模板
	class vector
	{
		public:
			typedef T* iterator;
			typedef const T* conat_iterator;
		iterator erase(iterator pos)
		{
			iterator it = pos + 1;
			while (it != _finish)
			{
				*(it - 1) = *it;
				++it;
			}

			--_finish;

			return pos;
		}
		private:
			iterator _start;
			iterator _finish;
			iterator _endOfStorage;
	};
}

📖void swap (vector& x)

void swap (vector& x);	交换两个vector的数据空间

模拟实现：

#include<iostream>
#include<assert.h>
using namespace std;
namespace cxy
{
	template <class T>//类模板
	class vector
	{
		public:
			typedef T* iterator;
			typedef const T* conat_iterator;
		void swap(vector<T>& v)
		{
			::swap(_start, v._start);
			::swap(_finish, v._finish);
			::swap(_endofstorage, v._endofstorage);
		}

		private:
			iterator _start;
			iterator _finish;
			iterator _endOfStorage;
	};
}

📖 reference operator[] (size_type n)

reference operator[] (size_type n)	像数组一样访问

模拟实现：

#include<iostream>
#include<assert.h>
using namespace std;
namespace cxy
{
	template <class T>//类模板
	class vector
	{
		public:
			typedef T* iterator;
			typedef const T* conat_iterator;
			T& operator[](size_t i)
			{
			assert(i < size());

			return _start[i];
			}
		private:
			iterator _start;
			iterator _finish;
			iterator _endOfStorage;
	};
}