STL—— vector(2)

图片名称

博主首页: 有趣的中国人

专栏首页: C++专栏


    本篇文章主要讲解 vector模拟实现的相关内容

    1. STL中vector的模式

    在STL中vector是靠三个迭代器来维护的:

    1. start
    2. finish
    3. end_of_storage

    如下图所示,其中size是现在有多少元素,而capacity是现在的空间有多少:

    在这里插入图片描述

    因此很容易看出:

    1. size = finsih - start;
    2. capacity = end_of_storage - start;

    所以可以写出vector类中的成员变量:

    namespace d1
    {
    	template<class T>
    	class vector
    	{
    	public:
    		typedef T* iterator;
    		typedef const T* const_iterator;
    	private:
    		iterator start = nullptr;
    		iterator finish = nullptr;
    		iterator end_of_storage = nullptr;
    	};
    }
    

      2. 插入相关操作的模拟

      2.1 push_back()


      push_back就是尾插操作,既然插入肯定要用到扩容,代码如下:

      size_t size() const
      {
      	return finish - start;
      }
      
      size_t capacity() const
      {
      	return end_of_storage - start;
      }
      void push_back(const T& val)
      {
      	if (end_of_storage == finish)
      	{
      		// 注意这里要记录以下原始size的大小,要不然找不到新的finish和end_of_storage的位置
      		size_t old_size = size();
      		size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
      		T* tmp = new T[newcapacity];
      		memcpy(tmp, start, old_size * sizeof(T));
      		delete[] start;
      		start = tmp;
      		finish = start + old_size;
      		end_of_storage = start + newcapacity;
      	}
      	*finish = val;
      	++finish;
      }
      

      这里尝试插入5个数据测试一下:
      在这里插入图片描述

      2.2 reserve()

      reserve 相当于就是扩容操作,刚才的尾插已经涉及到,把他放到reserve中即可:

      void reserve(size_t newcapacity)
      {
      	if (newcapacity > capacity())
      	{
      		size_t old_size = size();
      		T* tmp = new T[newcapacity];
      		memcpy(tmp, start, old_size * sizeof(T));
      		delete[] start;
      		start = tmp;
      		finish = start + old_size;
      		end_of_storage = start + newcapacity;
      	}
      }
      

      2.3 operator[]的重载 和 迭代器


      为了更好的访问vector和测试,我们可以先实现operator[]的重载 和 iterator

      1. operator[]的重载
      T operator[](size_t pos)
      {
      	assert(pos >= 0 && pos < size());
      	return start[pos];
      }
      
      1. iterator 和 const_iterator
      iterator begin()
      {
      	return start;
      }
      
      iterator end()
      {
      	return finish;
      }
      
      const_iterator begin() const
      {
      	return start;
      }
      
      const_iterator end() const
      {
      	return finish;
      }
      
      1. test代码:
      void vector_test1()
      {
      	vector<int> v;
      	v.push_back(1);
      	v.push_back(2);
      	v.push_back(3);
      	v.push_back(4);
      	v.push_back(5);
      	for (size_t i = 0; i < v.size(); ++i)
      	{
      		cout << v[i] << " ";
      	}
      	cout << endl;
      
      	vector<int>::iterator it = v.begin();
      	while (it != v.end())
      	{
      		cout << *it << " ";
      		++it;
      	}
      	cout << endl;
      }
      

      在这里插入图片描述

      1. 我们可以按照模板函数的方法将打印写成函数:
      • 这里有一点需要特别注意,注意仔细看注释。
      template<class T>
      void print_vector(const vector<T>& v)
      {
      	for (size_t i = 0; i < v.size(); ++i)
      	{
      		cout << v[i] << " ";
      	}
      	cout << endl;
      	// 注意这里:
      	// 编译器会无法分清你写的vector<T>::const_iterator是一个静态成员变量还是一个类型
      	// 因为此时并没有被实例化,编译器也不会在此时实例化
      	// 为了告诉编译器这里是一个类型,要在前面加上typename
      	// 一般嵌套模板都要加上typename
      	// vector<T>::const_iterator it = v.begin();
      	typename vector<T>::const_iterator it = v.begin();
      	while (it != v.end())
      	{
      		cout << *it << " ";
      		++it;
      	}
      	cout << endl;
      }
      

      2.4 insert()

      insert 允许你在任意位置插入元素,传入的是迭代器类型,这里需要注意是否需要扩容,如果需要扩容,就要更新pos的位置,模拟实现代码如下:

      void insert(iterator pos, const T& val)
      {
      	assert(pos >= begin() && pos <= finish);
      	if (finish == end_of_storage)
      	{
      		size_t old_pos = pos - start;
      		size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
      		reserve(newcapacity);
      		pos = start + old_pos;
      	}
      	iterator end = finish - 1;
      	while (end >= pos)
      	{
      		*(end + 1)= *end;
      		--end;
      	}
      	*pos = val;
      	++finish;
      }
      

      测试代码:

      void vector_test1()
      {
      	vector<int> v;
      	v.push_back(1);
      	v.push_back(2);
      	v.push_back(3);
      	v.push_back(4);
      	v.push_back(5);
      	v.insert(v.begin(), 0);
      	v.insert(v.end(), 6);
      	v.insert(v.begin() + 1, 10);
      	print_vector(v);
      }
      

      在这里插入图片描述

      2.5 resize()

      resize 有三种情况:

      1. 小于size:删除数据
      2. 大于size,小于capacity:插入数据
      3. 大于capacity:扩容+插入数据
      void resize(size_t n, const T& val = T())
      {
      	if (n >= size())
      	{
      		reserve(n);
      		for (size_t i = size(); i < n; ++i)
      		{
      			start[i] = val;
      			++finish;
      		}
      	}
      	else
      	{
      		finish = start + n;
      	}
      }
      

      测试代码:

      void vector_test1()
      	{
      		vector<int> v;
      		v.push_back(1);
      		v.push_back(2);
      		v.push_back(3);
      		v.push_back(4);
      		v.push_back(5);
      		v.insert(v.begin(), 0);
      		v.insert(v.end(), 6);
      		v.insert(v.begin() + 1, 10);
      		v.insert(v.begin() + 1, 10);
      		v.insert(v.begin() + 1, 10);
      		v.insert(v.begin() + 1, 10);
      		v.resize(20);
      		print_vector(v);
      	}
      

      在这里插入图片描述


        3. 删除相关操作的模拟

        3.1 判空

        start==finish时,为空:

        bool Empty()
        {
        	return start == finish;
        }
        

        3.2 pop_back()

        尾删,直接 --finish 即可。

        void pop_back()
        {
        	assert(!Empty());
        	--finish;
        }
        

        3.3 erase()

        在任意位置删除,将后面的元素往前挪动即可,最后再--finish

        void erase(iterator pos)
        {
        	assert(!(Empty()));
        	assert(pos >= start && pos < finish);
        	iterator begin = pos + 1;
        	while (begin < finish)
        	{
        		*(begin - 1) = *begin;
        		++begin;
        	}
        	--finish;
        }
        

          4. 构造函数相关操作模拟

          4.1 拷贝构造的现代写法

          正常拷贝构造的写法:

          vector(const vector<T>& v)
          {
          	T* tmp = new T[v.capacity()];
          	memcpy(tmp, v.start, sizeof(T) * v.size());
          	start = tmp;
          	finish = start + v.size();
          	end_of_storage = start + v.capacity();
          }
          

          现代写法:

          1. 先开辟一块大小相同的空间;
          2. 尾插到此块空间即可。
          vector(const vector<T>& v)
          {
          	reserve(v.capacity());
          	for (auto& e : v)
          	{
          		push_back(e);
          	}
          }
          

          4.2 赋值重载现代写法

          1. 传值传参,调用拷贝构造,深拷贝一块空间;
          2. 进行交换。
          void swap(vector<T>& v)
          {
          	std::swap(start, v.start);
          	std::swap(finish, v.finish);
          	std::swap(end_of_storage, v.end_of_storage);
          }
          
          vector<T>& operator=(vector<T> v)
          {
          	swap(v);
          	return *this;
          }
          

          4.3 迭代器区间构造

          类模板的成员函数可以是函数模板。
          迭代器区间构造就是支持用一段**其他类型的迭代器区间**来进行初始化vector。

          template<class InputIterator>
          vector(InputIterator first, InputIterator last)
          {
          	while (first != last)
          	{
          		push_back(*first);
          		++first;
          	}
          }
          

          测试代码:

          void vector_test4()
          {
          	vector<int> v1;
          	v1.push_back(1);
          	v1.push_back(2);
          	v1.push_back(3);
          	v1.push_back(4);
          	print_vector(v1);
          
          	vector<int> v2(v1.begin() + 1, v1.end() - 1);
          	print_vector(v2);
          
          	string str("abcd");
          	vector<int> v3(str.begin(), str.end());
          	print_vector(v3);
          }
          

          在这里插入图片描述

          4.4 代参的构造函数

          我这里实现的是用n个数来构造vector

          1. 首先申请一块空间;
          2. 然后对这n个数依次尾插即可。
          vector(size_t n, const T& val = T())
          {
          	reserve(n);
          	for (size_t i = 0; i < n; ++i)
          	{
          		push_back(val);
          	}
          }
          

          但是当运行以下的代码时,会报错:

          void vector_test5()
          {
          	vector<int> v1(10,1);
          	print_vector(v1);
          }
          

          在这里插入图片描述

          他报错的位置并不是我们上面写的代码,而是跑到了迭代器区间构造那里,因为编译器认为迭代器区间构造更匹配,因为编译器认为这里的10int类型,不是size_t类型,假如我们给10加上u(无符号整数),或者构造成char类型,就不会报错:

          void vector_test5()
          {
          	vector<int> v1(10u,1);
          	print_vector(v1);
          	vector<char> v2(10, 'a');
          	print_vector(v2);
          }
          

          为了解决这个问题,其实直接加个重载函数即可:

          vector(size_t n, const T& val = T())
          {
          	reserve(n);
          	for (size_t i = 0; i < n; ++i)
          	{
          		push_back(val);
          	}
          }
          vector(int n, const T& val = T())
          {
          	reserve(n);
          	for (size_t i = 0; i < n; ++i)
          	{
          		push_back(val);
          	}
          }
          

          这样编译器在调用函数的时候会先调用int参数的这个重载函数,因为这个最匹配。


            5. initializer_list

            C语言中我们构造数组通常是这样的:

            int a[] = { 0 };
            

            但是在C++中,倘若我们右大括号来定义一个变量,那么它的类型将不是数组,而是initializer_list,我们可以测试一下:

            void vector_test6()
            {
            	auto x = { 1,2,3,4,5 };
            	cout << typeid(x).name() << endl;
            }
            

            在这里插入图片描述
            那么initializer_list 究竟是什么呢?

            • initializer_list是C++中的一种容器,用于初始化同一类型的元素列表。它是C++11引入的一个特性,旨在简化初始化容器的过程。
              在这里插入图片描述
            • 我们知道单参数类型的构造函数支持隐式类型转换,例如:
            void vector_test6()
            {
            	// 构造 + 拷贝构造 -> 优化 直接构造
            	string str1 = "11111";
            	// 这里加引用引用的是"2222"临时拷贝出来的空间,临时变量具有常性,因此要加const
            	const string& str2 = "22222";
            	vector<string> v;
            	v.push_back(str1);
            	v.push_back(str2);
            	// 甚至可以用匿名对象进行隐式类型转换
            	v.push_back(string("hello"));
            	// 也能这样
            	v.push_back("world");
            	print_vector(v);
            }
            
            • 了解了以上内容,那我们就可以用这个来初始化我们的vector,因为initializer_list会隐式类型转换成vector<int>类型:
            void vector_test6()
            {
            	/*auto x = { 1,2,3,4,5 };
            	cout << typeid(x).name() << endl;*/
            	std::vector<int> v = { 1,2,3,4,5,6 };
            }
            
            • 也可以直接构造:
            vector<int> v2({ 10,20,30,40 });
            

              6. 有关memcpy的问题

              我们尝试运行以下这段代码:

              void vector_test7()
              {
              	vector<string> v;
              	v.push_back("11111");
              	v.push_back("22222");
              	v.push_back("33333");
              	v.push_back("44444");
              	v.push_back("55555");
              	v.push_back("66666");
              	v.push_back("77777");
              	v.push_back("88888");
              	v.push_back("99999");
              
              	for (auto& e : v)
              	{
              		cout << e << " ";
              	}
              	cout << endl;
              }
              

              在这里插入图片描述
              为什么会发生运行错误呢?我们可以调试一下:
              在这里插入图片描述

              • 如果我们尝试传入string类型,在扩容的时候用memcpy来拷贝一个自定义类型,实际上也是把string原来的地址传过去了,相当于虽然vector类型是深拷贝,但是string类型是浅拷贝,下图是存储示意图。
                在这里插入图片描述

              拷贝后:
              在这里插入图片描述

              • 因此我们要用for循环来取代memcpy就可以完美的解决这个问题:
              void reserve(size_t newcapacity)
              {
              	if (newcapacity > capacity())
              	{
              		size_t old_size = size();
              		T* tmp = new T[newcapacity];
              		//memcpy(tmp, start, old_size * sizeof(T));
              		for (size_t i = 0; i < size(); ++i)
              		{
              			// 这里对于string这样的类型进行的是赋值重载,也是深拷贝。
              			tmp[i] = start[i];
              		}
              		delete[] start;
              		start = tmp;
              		finish = start + old_size;
              		end_of_storage = start + newcapacity;
              	}
              }
              

                7. 迭代器失效问题

                • 迭代器失效,实际就是迭代器底层对应指针所指向的空间被销毁了,而使用一块已经被释放的空间,造成的后果是程序崩溃(即如果继续使用已经失效的迭代器,程序可能会崩溃)。
                • 带有扩容的操作都可能导致迭代器失效,例如push_back(),例如:
                void vector_test8()
                {
                	vector<int> v1;
                	vector<int>::iterator it = v1.begin();
                
                	v1.push_back(1);
                	v1.push_back(2);
                	v1.push_back(3);
                	v1.push_back(4);
                	v1.push_back(5);
                	v1.push_back(6);
                	v1.push_back(7);
                	v1.push_back(8);
                	print_vector(v1);
                	v1.insert(it, 40);
                
                	print_vector(v1);
                }
                
                • 这里插入八个数据空间已经满了,这时候再插入数据就会扩容,v1.begin()的地址就会变,但是迭代器是在开头定义的,他不会变,所以一般在insert以后,不建议使用迭代器。

                以下示例也会导致迭代器失效:

                void vector_test9()
                {
                	vector<int> v1;
                	v1.push_back(1);
                	v1.push_back(2);
                	v1.push_back(3);
                	v1.push_back(4);
                	v1.push_back(4);
                	v1.push_back(5);
                	//v1.push_back(4);
                
                	// 删除偶数 -- 迭代器失效以后,不要直接使用,如果要使用按规则重新更新后使用
                	//std::vector<int>::iterator it = v1.begin();
                	vector<int>::iterator it = v1.begin();
                	while (it != v1.end())
                	{
                		if (*it % 2 == 0)
                		{
                			it = v1.erase(it);
                		}
                		else
                		{
                			++it;
                		}
                	}
                
                	//print_vector(v1);
                	for (auto e : v1)
                	{
                		cout << e << " ";
                	}
                	cout << endl;
                }
                

                相关推荐

                1. 作业2.2

                  2024-04-01 20:14:02       16 阅读
                2. <span style='color:red;'>2</span>.<span style='color:red;'>2</span>作业

                  2.2作业

                  2024-04-01 20:14:02      18 阅读
                3. 2.2作业

                  2024-04-01 20:14:02       19 阅读
                4. 假期作业 2.2

                  2024-04-01 20:14:02       18 阅读
                5. 2024/2/2

                  2024-04-01 20:14:02       16 阅读
                6. 作业2024/2/2

                  2024-04-01 20:14:02       20 阅读

                最近更新

                1. leetcode705-Design HashSet

                  2024-04-01 20:14:02       5 阅读
                2. Unity发布webgl之后打开streamingAssets中的html文件

                  2024-04-01 20:14:02       5 阅读
                3. vue3、vue2中nextTick源码解析

                  2024-04-01 20:14:02       6 阅读
                4. 高级IO——React服务器简单实现

                  2024-04-01 20:14:02       5 阅读
                5. 将图片数据转换为张量(Go并发处理)

                  2024-04-01 20:14:02       4 阅读
                6. go第三方库go.uber.org介绍

                  2024-04-01 20:14:02       6 阅读
                7. 前后端AES对称加密 前端TS 后端Go

                  2024-04-01 20:14:02       7 阅读

                热门阅读

                1. 配置一个nginx的server, 提供获取ip的服务

                  2024-04-01 20:14:02       4 阅读
                2. 标题:AI大模型学习:解放智能的未来之路

                  2024-04-01 20:14:02       5 阅读
                3. 深入探秘Python生成器:揭开神秘的面纱

                  2024-04-01 20:14:02       6 阅读
                4. 计算机网络目录

                  2024-04-01 20:14:02       4 阅读
                5. ChatGPT助力学术论文写作:方法与实践

                  2024-04-01 20:14:02       5 阅读
                6. PostgreSQL中json_to_record函数的神秘面纱

                  2024-04-01 20:14:02       5 阅读