vector的模拟实现

vector就是一个顺序表而已，只不过它是类模板，可以实例化出不同的模板类。下面我们通过模拟实现来进一步的熟悉vector。

vector的成员变量

与顺序表的成员不一样，顺序表的成员变量是指向数组的一个指针，实际数据的大小，空间的容量。而vector的成员变量都是指针，三个指针，分别为指向所开空间的头，指向实际数据的尾，指向空间的尾。那么size,capacity也都可以很容易的表示出来。

	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
	private:
		iterator start;
		iterator finish;//这里的finish指向的是最后一个数的下一个位置
		iterator end_of_storage;
	};
1
2
3
4
5
6
7
8
9
10

计算它的大小size，容量capaticy

size=finish-start,capacity=end_of_storage-start

		size_t size()cosnt
		{
			return finish - start;
		}
		size_t capacity()const 
		{
			return end_of_storage - start;
		}
1
2
3
4
5
6
7
8

首尾的标志begin，end,首尾元素front,back

begin就直接返回第一个元素的地址，end返回最后一个元素的地址。

                iterator begin()
		{
			return start;
		}
		iterator end()
		{
			return finish;
		}
1
2
3
4
5
6
7
8

front,back

		T& front()
		{
			return *start;
		}
		T& back()
		{
			return *(finish - 1);
		}
1
2
3
4
5
6
7
8

[]运算符的重载

首先要判断一下位置是否合法。同时还要返回引用，因为可能会对数据进行修改。

		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

判断是否为空empty

只需要判断头尾是否相等就可以，相等就是空，不相等就不为空。

		bool empty()
		{
			return start == finish;
		}
1
2
3
4

构造，析构函数

构造函数

无参的拷贝构造,对应无参的构造函数直接都初始化为空指针就可以。

		vector()
			:start(nullptr)
			, finish(nullptr)
			, end_of_storage(nullptr)
		{}
1
2
3
4
5

含参的构造
把n个数据都初始为一个值。

		vector(size_t n, const T& val = T())
			:start(nullptr),finish(nullptr),end_of_storage(nullptr)
			//写这句话的目的就是因为开始的时候指针都没有初始化，都是野指针，当开辟空间的时候会出现错误。
		{
			reserve(n);
			for (size_t i = 0; i < n; ++i)
			{
				start[i] = val;
			}
			finish = start + n;
		}
1
2
3
4
5
6
7
8
9
10
11

const T& val = T(),对于这个参数，读者们可能看不懂，T()生成的是匿名对象，对于内置类型，它生成的是0。

用一段区间去初始化构造

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

拷贝构造

拷贝构造要考虑深浅拷贝的问题，不能单纯的进行值的拷贝。

		vector(const vector<T>& v)
		{
			start = new T[v.size()];
			for (size_t i = 0; i < v.size(); ++i)
			{
				start[i] = v.start[i];
			}
			finish = start + v.size();
			end_of_storage = finish;
		}
1
2
3
4
5
6
7
8
9
10

析构函数

对申请的空间进行释放

		~vector()
		{
			delete[] start;
			start = finish = end_of_storage = nullptr;
		}
1
2
3
4
5

改变容量的大小reserve

对于reserve，当给的参数小于等于实际空间大小的时候，此操作是不容许的，所以不会有什么操作，只有当大于实际空间的时候才会进行扩容。

void reserve(size_t n)
{
if (n > capacity())
{
    size_t sz = size();
    T* tmp = new T[n];
    if (start)
    {
        for (size_t i = 0; i < sz; ++i)
        {
            tmp[i] = start[i];//要注意这里，当这里是自定义类型的时候，这里就是赋值（赋值运算符的重载，要自己实现一下）
        }
        delete[] start;
    }
    start = tmp;
    finish = start + sz;//这里需要改变数据结尾指针的指向，因为空间重新开辟了。
    end_of_storage = start + n;//当然，空间的指针指向也需要改变
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

resize改变元素的个数n

当n小于容器个数的时候，直接把个数减少到n，空间的大小不变。
当n大于容器个数的时候，我们需要开空间，把多开的空间默认初始化尾0，当然要把之前的元素拷贝到新的空间里面，是深拷贝哦。

	void resize(size_t n, const T& val = T())
	{
		if (n < size())
		{
			finish = start + n;
		}
		else if (n > size())
		{
			iterator temp = new T[n];
			for (size_t i = 0; i < n; ++i)
			{
				if (i < size())
					temp[i] = start[i];
				else
					temp[i] = val;
			}
			delete[] start;
			start = temp;
			finish = start + n;
			end_of_storage = finish;
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

尾插

尾插的时候需要注意什么呢？
尾插需要注意是否要进行扩容，对插入的类型需要考虑。

		void push_back(const T& x)
		{
			if (size() == capacity())
			{
				//扩容
				size_t len = size() == 0 ? 4 : size() * 2;
				reserve(len);
			}
			*finish = x;
			finish++;
		}
1
2
3
4
5
6
7
8
9
10
11

尾删

直接进行删除就可以，删除的时候要判断数据是否为空。

		void pop_back()
		{
			assert(size());
			--finish;
		}
1
2
3
4
5

任意位置删除

	iterator erase(iterator pos)
	{
		assert(pos < finish);
		assert(pos >= start);
		iterator cur = pos;
		while (cur != finish)
		{
			*cur = *(cur + 1);
			cur++;
		}
		finish--;
		return pos;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13

任意位置插入

	iterator insert(iterator pos, const T& x)
	{
		assert(pos <= finish);
		assert(pos >= start);
		size_t p = pos - start;
		if (finish == end_of_storage)
		{
			reserve(capacity() + 1);
		}
		for (size_t i = size()-1; i>p; --i)
		{
			start[i] = start[i - 1];
		}
		start[p] = x;
		return start + p;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

赋值运算符的重载

赋值也会涉及深拷贝，要注意，当然，如果自己进行赋值，就是没有必要的，所以要判断一下。

	vector<T>& operator=(const vector<T>& v)
	{
		if (start != v.start)
		{
			iterator temp = new T[v.size()];
			for (size_t i = 0; i < v.size(); ++i)
			{
				temp[i] = v.start[i];
			}
			delete[] start;
			start = temp;
			finish = start + v.size();
			end_of_storage = finish;
		}
		return *this;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16