c++还原简单的vector

vector

vecotor的介绍

1.vector是表示可变大小数组的序列容器

2.就像数组一样，vector也采用连续存储空间来存储元素，意味着可以采用下标对vector的元素进行访问。（和数组一样高效）

3.vector使用动态分配数组来存储元素，当新元素插入时，而旧的空间不够时，一般分配一个新的数组，然后把全部元素移到新的数组，再进行新元素的插入。

4.vector会分配一些额外的空间来适应可能的增长，因此存储空间比实际需要的存储空间更大。

库里vector

vector的模拟实现

类的框架

namespace Vect
{
    template<typename T>//模板参数
    class vector
    {
public:
        
    成员函数
    ......
private:
        
    成员变量
    ......
    };
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

成员变量

	private:

		iterator _start;//从0开始
		iterator _finish;//最后一个成员变量的下一个位置
		iterator _endofstorage;//容量
1
2
3
4
5

迭代器

这里的迭代器iterator可看作为指针

typedef T*iterator;
typedef const T* const_iterator;
iterator begin()
{
return _start; 
}

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

const_iterator end() const
{
return _finish;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

构造函数

vector()//构造函数
    //这里用初始化列表比较方便
			:_start(nullptr)
			,_finish(nullptr)
			,_endofstorage(nullptr)
		{}
1
2
3
4
5
6

析构函数

~vector()//析构函数
		{
			delete[] _start;
			_start = _finish = _endofstorage = nullptr;
		}
1
2
3
4
5

size()

指针相减 得指针之间成员个数

size_t size() const//size---有效成员个数
		{
		return 	_finish - _start;
		}
1
2
3
4

capacity()

	size_t capacity()const//capacity---容量
		{
			return _endofstorage - _start;
		}
1
2
3
4

operator[]重载

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

const T& operator[](size_t pos) const
		{
			assert(pos < size());
			return T[pos];
		}
1
2
3
4
5
6
7
8
9
10
11

扩容

void reserve(size_t n)
{
  if (n > capacity())
  {
  size_t oldsize = size();//记录成员个数
  T* tmp = new T[n];//开辟新空间
  if (_start)//如果_start指向的空间不为空就要拷贝数据
  {
         //把_start的数据拷贝到tmp上面
		//memcpy(tmp, _start, sizeof(T) * oldsize);//这里实现了浅拷贝
                    //后面会谈到memcpy的弊端
      for(size_t i=0;i<oldsize;i++)
           {
                   tmp[i]=_start[i];//这里实现深拷贝
           }
		//删除旧空间-空间不为空才需要释放
          delete[]_start;
	}
		_start = tmp;//指向新空间
//原来的size=_finish-_start,而此时的_start是新空间的_start,   //_finish是旧空间的_finish，相减得出不是之间成员个数了；所以我们要用oldsize()来记录先前的成员个数，用新的_start+oldsize()得出新的_finish
				_finish = _start + oldsize;
				_endofstorage = _start + n;
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

resize()

void resize(size_t n, T val = T())//value_type val 给匿名对象
//n
//size()
//n>capacity():扩容且用val初始化有效成员以外的成员变量；		
{
    
			if (n > capacity())//n大于容量
			{
				reserve(n);//扩容
			}
			if (n > size())
			{
				while (_finish < _start + n)
				{//用val初始化有效成员以外的成员变量；
					*_finish = val;
					++_finish;
				}
			
			}
			else
			{
				_finish = _start + n;//缩size（）
			}
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

尾插

void push_back(const T& x)//尾插
		{
			if (_finish == _endofstorage)//扩容
			{
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newcapacity);
			}
			*_finish = x;
			++_finish;
		}
1
2
3
4
5
6
7
8
9
10

验证是否为空

bool empty()const
		{
			return _start == _finish;
		}
1
2
3
4

尾删

void pop_back()
		{
			assert(!empty());
			--_finish;
		}
1
2
3
4
5

clear 清除

void clear()//清理---不影响容量
		{
			_finish = _start;
		}
1
2
3
4

swap交换

void swap(vector<T>& v)//交换
{//这里要指明是std库里的swap，因为头文件展开后从上往下找swap函数不一定先找到的是std库里的swap，还可能是vector的swap
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstorage,v._endofstorage);
		}
1
2
3
4
5
6

insert插入

这里我们实现第一个接口

//迭代器失效：当插入时要扩容，pos指针指向原来的空间，而_start指向新空间，在挪动数据时会出问题
		iterator insert(iterator pos, const T& val)
		{//pos要在_start和_finish之间
			assert(pos >= _start);
			assert(pos < _finish);

			//_start为空时插入要扩容或者容量满了都要扩容
			if (  _finish==_endofstorage)
			{
				size_t len = pos - _start;//记录pos的相对位置
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newcapacity);
				pos = _start + len;//针对迭代器失效要对pos更新
			}
			iterator end = _finish - 1;
			while (end >= pos)//挪动数据
			{
				*(end + 1) = *(end);
				--end;
			}
			*(pos) = val;
			++_finish;	
            return pos;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

erase删除

这里我们实现第一个接口

	iterator erase(iterator pos)
		{
			assert(pos >= _start);
			assert(pos < _finish);
			iterator begin=pos+1;
			while (begin<_finish)
			{
				*(begin-1) = *(begin );
				++begin;
			}
			--_finish;
			return pos;//返回迭代器
		}
1
2
3
4
5
6
7
8
9
10
11
12
13

在这里我们创建一个vector往里面尾插1234；之后我们删除4；并且打印删除后的迭代器位置

这里我们运行了看起来没有问题，实际上问题很大！删除4后容器的数据只有123，而我们访问到了4—野指针越界访问！ 这里我们实现的模拟跟Linux系统下相似，所以在Linux系统下也不会报错；但我们如果删除的是2或者是3呢？会越界吗？换句话说：迭代器会失效吗？答：在Linux系统下迭代器可能会失效也可能不会！但在vs下必然失效！

这里我们换库里面的vector的erase试一下

果然在vs下对迭代器做了更严格的检查，读都不给读，更何况是写；—迭代器失效了吗？？？好像失效了，这里有人会说你这个删除4肯定是越界了，那我删除别的对象不就不越界了嘛？

好现在我们删除2

照样报错！所以我们使用完迭代器之后最好就不要再用迭代器了

如果硬要用就更新迭代器！

删除4—会被断言出越界

删除2—更新了迭代器不会报错

现在在vs还是Linux下都不会发生迭代器失效了，若越界直接断言！

迭代器区间初始化构造函数

		template <class InputIterator>
		vector(InputIterator first, InputIterator last)
            //构造函数：用迭代器区间去初始化
			: _start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
1
2
3
4
5
6
7
8
9
10
11
12
13

拷贝构造

	vector(const vector<T>& v)//拷贝构造
		:_start(nullptr)
		, _finish(nullptr)
		, _endofstorage(nullptr)//因为要扩容，所以要提前初始化三个迭代器
{
vector<T> tmp(v.begin(),v.end());//用迭代器构造tmp；因为是用的const+引用所以要有中间者tmp
			
			swap(tmp);//this和临时对象tmp交换
			
}
1
2
3
4
5
6
7
8
9
10

赋值运算符重载

vector<T>& operator=( vector<T> v)//传值
		{
//赋值的时候如果容量满了会扩容，就算是自己赋值給自己也会扩容；先后经过后者拷贝构造临时对象，拷贝构造时用到迭代器区间构造临时对象，//然后构造时就用到尾插push_back，尾插时就验证要不要扩容！
			swap(v);//this和v交换
			return *this;
		}
1
2
3
4
5
6

n个val构造函数

		vector(size_t n, const T& val = T())//库里面給的是size_t n
			: _start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			reserve(n);//扩容
			for (size_t i = 0; i < n; i++)
			{
				push_back(val);
			}
		}

		vector(int n, const T& val = T())
  //int模式构造函数的n重载size_t模式构造函数的n
			: _start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			reserve(n);//扩容
			for (int i = 0; i < n; i++)
			{
				push_back(val);
			}
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

上面出现了size_t n的构造函数和int n的构造函数

我们做个实验，把int n的构造函数注释掉；然后用10个5初始化构造v

运行后发现报错了，原因是非法的间接寻址。这是为啥呢？

我们看到上面10个5初始化，类型为**（int ,int)** ；而n个val的参数类型为**（size_t ,int)**

另一个迭代器区间初始化的参数类型为**（InputIterator first, InputIterator last）**

分别为两个参数模板类型，而int参数也可以作为参数模板；

（int,int)参数类型进到**(size_t,int)参数类型前者int还需要整形提升**；而对于（InputIterator first, InputIterator last）类型(int,int)可以直接进入。但到后面的地址解引用就是非法寻址了！

所以我们还需要在写一个(int,int)参数类型的构造函数重载(size_t ,int)构造函数

再谈构造函数

这里我们创建一个4个vectorint>>,給vector<int>序列初始化为11

然后我们打印出来

我们打印四个vector<int>，没毛病。我们打印五个：报错了！

这是为啥呢？我们前面写到构造函数扩容，size达到4时要扩容，前者四个没报错而后者5个报错了！这说明扩容有问题！

构造函数用到push_back，数量达到4个要扩容，而这里的扩容是先new一块8个对象(类型为vector<int>)大的新空间tmp（类型为vectorint>>)，把旧空间的vector<int>的_start一个个拷贝（这里是memcpy-浅拷贝）到新空间；再delete旧空间vv（先依次析构v再析构空间vv）；再把 vv的 _start指向新空间tmp；这时我们发现vv扩容为tmp是完成了深拷贝（把v的 _start一个个拷贝到tmp上），而v却还是浅拷贝（ v的 _start 还是指向原来的空间，而原来的空间已经被析构了—属于野指针越界访问！）这里配合着下图理解

所以我们要换种方式扩容拷贝

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t oldsize = size();
				T* tmp = new T[n];//开辟新空间
				if (_start)//如果_start指向的空间不为空就要拷贝数据
				{
					for (size_t i = 0; i < oldsize; ++i)
					{
						tmp[i] = _start[i];//复用运算符重载=完成深拷贝
                    }
                    delete[]_start;//删除旧空间-空间不为空才需要释放
				}
				_start = tmp;//指向新空间
				_finish = _start + oldsize;
				_endofstorage = _start + n;
			}
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

好啦，vector的模拟实现就到这了。小伙伴们要多多实现加深印象噢！