开发者

C++模拟如何实现vector

开发者 https://www.devze.com 2023-02-06 10:55 出处:网络 作者: 安河桥畔
目录一、迭代器定义普通迭代器const类型迭代器二、构造类构造函数拷贝构造函数赋值运算符重载析构函数三、容量相关操作size、capacityemptyresize⭐reserve三、元素访问[ ]重载frontback四、修改类接口push_backpop_
目录
  • 一、迭代器
    • 定义
    • 普通迭代器
    • const类型迭代器
  • 二、构造类
    • 构造函数
    • 拷贝构造函数
    • 赋值运算符重载
    • 析构函数
  • 三、容量相关操作
    • size、capacity
    • empty
    • resize
    • ⭐reserve
  • 三、元素访问
    • [ ]重载
    • front
    • back
  • 四、修改类接口
    • push_back
    • pop_back
    • insert
    • erase
    • clear
    • swap
  • 五、成员变量
    • 总结

      一、迭代器

      定义

      vector类型的迭代器就是原生态的指针,对T*进行重命名即可

      typedef T* iterator;
      typedef const T* const_iterator;
      

      普通迭代器

      iterator begin()
      {
      	return start;
      }
      iterator end()
      {
      	return finish;
      }
      

      const类型迭代器

      const类型迭代器可以访问const成员变量

      const iterator cbegin()const
      {
      	return start;
      }
      const iterator cend()const
      {
      	return finish;
      }
      

      二、构造类

      构造函数

      构造空对象

      在初始化列表中对三个成员变量进行初始化

      vector()
      	:start(nullptr)
      	, finish(nullptr)
      	, endOfStorage(nullptr)
      {}
      

      n个T类型

      开辟空间以后,对finish进行自增,在空间填充元素

      vector(size_t n, const T& value = T())
      	:start(new T[n])
      	, finish(start)
      	, endOfStorage(start + n)
      {
      	for (int i = 0; i < n; i++)
      	{
      		*finish++ = value;
      	}
      }
      

      重载前一个构造函数,将第一个参数设置为int类型

      vector(int n, const T& value = T())
      	:start(new T[n])
      	, finish(start)
      	, endOfStorage(start + n)
      {
      	for (int i = 0; i < n; i++)
      	{
      		*finish++ = value;
      	}
      }
      

      之所以要对这种类型的构造函数进行重载,是因为在调用构造函数时,如果实参传两个整型数字,编译器会默认为int类型数据,进行推演之后与前面的size_t类型不匹配,则会调用下面的区间构造的方法,导致程序报错,如图:

      C++模拟如何实现vector

      迭代器构造

      将构造方法中迭代器的类型写成模板类型,这样便可以接收其它类型的迭代器,如:T类型为char,Iterator迭代器为string类型,便可以从字符串中截取字符,构造vector<char>类型的对象。

      //写成函数模板,可以接受任意类型的迭代器
      template<typename Iterator>
      vector(Iterator first, Iterator last)
      {
      	size_t n = ZH::distance(first, last);//获取长度
      	start = new T[n];
      	finish = start;
      	endOfStorage = start + n;
      	while (first != last){
      		*finish = *first;
      		first++;
      		finish++;//完成赋值的同时也移动了finish的位置
      	}
      }
      

      将distance方法写到另一个.hpp头文件中

      template<typename Iterator>
      //此处的Iterator是模板参数,表示可以传任意类型的迭代器
      size_t distance(Iterator first, Iterator last)
      {
      	//获取元素个数,暂时只考虑底层空间连续的情况
      	int count = 0;
      	while (first != last)
      	{
      		first++;
      		count++;
      	}
      	return count;
      }
      
      

      拷贝构造函数

      拷贝构造函数的形参必须是const类对象的引用,必须使用const类型的迭代器才能访问,复用迭代器构造的方法定义一个临时变量temp,交换temp与当前对象

      //此处拷贝构造函数的形参是const类型
      vector(const vector<T>& v)
      	:start(nullptr)
      	, finish(nullptr)
      	, endOfStorage(nullptr)
      {
      	//▲用const类型的迭代器访问const变量
      	vector<T> temp(v.cbegin(), v.cend());
      	this->swap(temp);
      }
      

      赋值运算符重载

      形参设置为类类型对象,调用赋值运算符重载函数时,形参会拷贝实参,交换当前对象与形参的值。

      vector<T>&编程客栈 operator=(const vector<T> v)
      {
      	this->swap(v);
      	return *this;
      }
      

      析构函数

      释放空间,将三个迭代器赋值为空

      ~vector()
      {
      	delete[]start;
      	start = nullptr;
      	finish = nullptr;
      	endOfStoragephp = nullptr;
      }
      

      三、容量相关操作

      size、capacity

      size_t size()
      {
      	return finish - start;
      }
      size_t capacity()
      {
      	return endOfStorage - start;
      }
      

      empty

      判断fiinsh与start是否相等即可,相等则为空

      size_t empty()
      {
      	return finiandroidsh == start;
      }
      

      resize

      定义一个变量保存旧的size的值‘判断是减小还是增加size;判断是否需要扩容,需要则调用reserve函数,从旧空间的结束位置开始,给新增加的空间填充元素;最后改变finish的值。

      void resize(size_t newsize, const T& value = T())
      {
      	size_t oldsize = size();
      	if (newsize > oldsize){
      		if (newsize > capacity()){
      			reserve(newsize);
      		}
      		for (size_t i = oldsize; i < newsize; i++)
      		{
      			start[i] = value;
      		}
      	}
      	finish = start + newsize;//不用考虑增加或减小
      }
      

      ⭐reserve

      reserve的步骤:申请新空间,拷贝旧空间的元素,释放旧的空间。

      void reserve(size_t newcapacity)
      {
      	size_t oldcapacity = capacity();
      	if (newcapacity > oldcapacity)
      	{
      		size_t n = size();//保存size()的值
      		T* temp = new T[newchttp://www.开发者_JS教程devze.comapacity];
      		//start不为空时才进行拷贝旧空间元素和释放的操作
      		if (start)
      		{
      			//memcpy浅拷贝,当vector中存放的对象内部设计资源管理
      			// 会有内存泄漏和野指针问题
      			//memcpy(temp, start, sizeof(T) * n);
      
      			for (size_t i = 0; i < n; i++)
      			{
      				temp[i] = start[i];//调用赋值运算符重载
      			}
      			delete[] start;
      		}
      		start = temp;
      		//▲此处不能用satart+size(),因为size方法中有finish-start,而start值已经改变
      		finish = start + n;
      		endOfStorage = start + newcapacity;
      	}
      }
      

      ▲易错点:

      • 判断start的值是否为空 ,如果原来的start为空,则不需要再拷贝元素和释放
      • 浅拷贝问题

      C++模拟如何实现vector

      finish更新问题

      C++模拟如何实现vector

      size()的方法内部finish-start,而此时start已经发生改变,finish还是旧的,所以要提前定义一个临时变量保存size()的值

      三、元素访问

      [ ]重载

      重载成普通类型和const类型,const类型可以访问const成员

      T& operator[](size_t index)
      {
      	assert(index < size());
      	return start[index];
      }
      
      const T& operator[](size_t index)const
      {
      	assert(index < size());
      	return start[index];
      }
      

      front

      返回动态数组第一个元素

      T& front()
      {
      	return start[0];
      }
      const T& front()const
      {
      	return start[0];
      }
      

      back

      返回最后一个位置前一个元素

      T& back()
      {
      	return *(finish - 1);
      }
      const T& back()const
      {
      	return *(finish - 1);
      }
      

      四、修改类接口

      push_backjs

      插入前先判断空间是否已满,空间若满则进行扩容,扩容时,要原来的空间容量为0的情况;将value放置到末尾位置,并将finish向后移动一个单位

      void push_back(const T& value)
      {
      	if (finish == endOfStorage)
      	{
      		//因为原来的capacity可能为0,所以要+3
      		reserve(capacity() * 2 + 3);
      	}
      	*finish++ = value;
      }
      

      pop_back

      尾删,先判断对象是否为空,若不为空则将finish位置前移一个单位

      void pop_back()
      {
      	if (empty())
      	{
      		return;
      	}
      	finish--;
      }
      

      insert

      任意位置插入,insert的返回值为新插入的第一个元素位置的迭代器;因为插入可能会进行扩容,导致start的值改变,所以先定义一个变量保存pos与start的相对位置;判断是否需要扩容;从插入位置开始,将所有元素向后搬移一个位置;将pos位置的值置为要插入的值;更新finish的值。

      //第二个参数用const修饰,常量引用
      //不用const修饰则为非常量引用
      iterator insert(iterator pos, const T& value)
      {
      	int index = pos - start;
      	assert(pos >= start && pos < finish);
      	//判断空间是否足够
      	if (finish == endOfStorage)
      	{
      		reserve(capacity() * 2);
      	}
      	pos = start + index;
      	for (auto it = finish; it > pos; it--)
      	{
      		*it = *(it - 1);
      	}
      	*pos = value;
      	finish++;
      	return pos;
      }
      

      erase

      判断下标合法性;从pos位置下一个位置开始,将所有元素向前搬移一个位置;更新finish的值

      iterator erase(iterator pos)
      {
      	assert(pos >= start && pos < finish);
      
      	auto it = pos;
      	while (it < finish - 1)
      	{
      		*it = *(it + 1);
      		it++;
      	}
      	finish--;
      	return pos;
      }
      

      clear

      清空所有元素,令finish=start即可

      void clear()
      {
      	finish = start;
      }
      

      swap

      vector内置的swap函数,调用标准库中的swap交换vector的三个成员变量的值

      void swap(vector<T>& v)
      {
      	std::swap(start, v.start);
      	std::swap(finish, v.finish);
      	std::swap(endOfStorage, v.endOfStorage);
      }
      

      五、成员变量

      private:
      	iterator start;
      	iterator finish;
      	iterator endOfStorage;
      

      vector内部有三个成员变量,start表示起始位置,finish表示有效元素的末尾位置,endOfStorage表示空间的末尾位置;通过这三个成员变量可以得到size和capacity等值,如图:

      C++模拟如何实现vector

      总结

      以上为个人经验,希望能给大家一个参考,也希望大家多多支持我们。

      0

      精彩评论

      暂无评论...
      验证码 换一张
      取 消

      关注公众号