【C++】中的vector使用详解及重要部分底层实现

这篇具有很好参考价值的文章主要介绍了【C++】中的vector使用详解及重要部分底层实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【C++】中的vector使用详解及重要部分底层实现,C++,c++,开发语言  

 

  本篇文章会对vector的语法使用进行详解。同时,还会对重要难点部分的底层实现进行讲解。其中有vector的迭代器失效深拷贝问题。希望本篇文章的内容会对你有所帮助。

目录

一、vector 简单概述

1、1 C语言中数组的不便

1、2 C++中的动态数组容器vector 

二、vector的常用语法举例

2、1 vector的声明和定义

2、1 尾插 push_back

2、2 尾删 pop_back

2、3 设置容量大小 reserve

2、4 赋值 =

2、5 在pos位置插入

2、6 任意位置删除

2、7 访问vector中的元素

2、8 数组中的头和尾元素front()、back()

 三、部分重要底层实现及常见问题

3、1 拷贝构造的底层实现

3、2 insert的底层实现及迭代器失效

3、3  erase的底层实现及迭代器失效

3、4 vector中深拷贝的问题


🙋‍♂️ 作者:@Ggggggtm 🙋‍♂️

👀 专栏:C++  👀

💥 标题:vector讲解💥

 ❣️ 寄语:与其忙着诉苦,不如低头赶路,奋路前行,终将遇到一番好风景 ❣️  

【C++】中的vector使用详解及重要部分底层实现,C++,c++,开发语言

一、vector 简单概述

1、1 C语言中数组的不便

  在C语言中,我们所要存放一组类型相同的数据,我们可以选择数组。C语言中的数组是静态的,一旦声明后,其大小就是固定的,无法动态调整。这就导致使用起来并不方便。当然,我们也用malloc、calloc来动态申请空间。当我们不再使用此数组时,我们也要时刻注意是否已经释放我们所动态开辟的空间

1、2 C++中的动态数组容器vector 

   针对C语言中静态数组的不便,C++中引出了动态数组容器vector,vector有以下几个不同和优点:

  1. 可以根据需要自动调整大小,可以动态地添加或删除元素。
  2. 就像数组一样,vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问,和数组一样高效。但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自动处理。
  3. C++中的vector自动处理内存管理,无需手动指定大小或释放内存。
  4. C++中的vector提供了边界检查功能,能够确保在访问元素时不会发生越界错误。
  5. C++中的vector提供了丰富的函数和操作,如添加元素、删除元素、排序、查找等。这些功能能够更方便地操作和处理数组元素。

  本质讲,vector使用动态分配数组来存储它的元素。当新元素插入时候,这个数组需要被重新分配大小为了增加存储空间。其做法是,分配一个新的数组,然后将全部元素移到这个数组。就时间而言,这是 一个相对代价高的任务,因为每当一个新的元素加入到容器的时候,vector并不会每次都重新分配大小。

   只有概念并不能很好的使用vector,我们接下来看一下vector语法的讲解。 

二、vector的常用语法举例

#include <vector>
#include <iostream>
using namespace std;
int main()
{
	vector<int> v;
	vector<int> v1(10);
	vector<int> v2(10, 1);
	vector<int> v3(v2);


	v.push_back(10);
	v.push_back(20);

	v.pop_back();

	v.reserve(10);

	v = v1;

	v.insert(v.begin() + 2, 3);

	v.erase(v.begin() + 2);

	int sz = v.size();
	for (int i = 0; i < sz; i++)
	{
		cout << v[i] << " ";
	}
	cout << endl;

	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;

	for (auto it : v)
	{
		cout << it << " ";
	}
	cout << endl;

	v.clear();
    
    v.front();
    v.back();
	return 0;
}

   我们就上面的例子展开对vector的用法进行详解。

2、1 vector的声明和定义

  当我们想用vector时,我们首先要引入头文件:#include<vector>。当我们可展开命名空间std,也可选择不展开命名空间std。具体例子如下:

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

int main() 
{
    //std::vector<int> v;
	vector<int> v;
	vector<int> v1(10);
	vector<int> v2(10, 1);
	vector<int> v3(v2);
    return 0;
}   

  注意,上述中的变量v为空数组,空间大小为0。v1是开辟了一个大小为10个int的数组,这10个元素默认为0。v2是开辟了一个大小为10个int的数组,这10个元素初始化为1。v3是用v2中的元素来进行初始化的,也就是v3中的元素与v2中的元素相同。我们可看如下结果:

【C++】中的vector使用详解及重要部分底层实现,C++,c++,开发语言

2、1 尾插 push_back

  有了vector,我们想要往里添加元素,我们可使用push_back进行尾部插入元素。具体例子如下:

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int> v;
	vector<int> v1(10);
	vector<int> v2(10, 1);


	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
    return 0;
}

  运行结果如下:

【C++】中的vector使用详解及重要部分底层实现,C++,c++,开发语言

   我们发现,v数组不是空间大小为0吗,怎么还能插入元素呢?这个是因为vector是一个动态数组,底层就是一个动态的顺序表当空间容量不够时,会自动进行扩容

2、2 尾删 pop_back

   pop_back可对尾部元素进行删除。当然,尾删的前提是数组不为空。否则会程序会被终止。具体例子如下:‘

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int> v;
	//v.pop_back();
	vector<int> v1(10);
	vector<int> v2(10, 1);


	v.push_back(10);
	v.push_back(20);
	v.push_back(30);

	v.pop_back();
    return 0;
}

  我们先看看在空vector进行删除的结果:

【C++】中的vector使用详解及重要部分底层实现,C++,c++,开发语言

  我们再看看实际的尾删效果:

【C++】中的vector使用详解及重要部分底层实现,C++,c++,开发语言

2、3 设置容量大小 reserve

  当我们知道要存储的元素个数是多少时,我们可直接通过reserve来设置vector的容量大小。有人就说了,vector空间不够了可以自己进行扩容,为啥还要用reserve来设定容量大小呢?注意,扩容是有损耗的。频繁的扩容会大大的降低程序的运行效率。我们来看reserve的实际效果。

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int> v;

	v.push_back(10);
	v.push_back(20);
	v.push_back(30);

	v.pop_back();

	
	v.reserve(10);
    return 0;
}

  运行结果如下:

【C++】中的vector使用详解及重要部分底层实现,C++,c++,开发语言

  我们之前看到尾删后的容量(capacity)大小为3,当我们reserve()后,容量大小变为了10。size为当前vector中的实际有多少个元素。capacity为当前vector实际能够存储多少个元素。两者是不同的。

2、4 赋值 =

  当然,我们也可直接对不同的vector进行赋值操作。具体例子如下:

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int> v;
	vector<int> v1(10);

	v.push_back(10);
	v.push_back(20);
	v.push_back(30);

	v.pop_back();

	
	v.reserve(10);

	
	v = v1;
    return 0;
}

  运行结果如下:

【C++】中的vector使用详解及重要部分底层实现,C++,c++,开发语言

  赋值完后,v与v1完全相同。 

2、5 在pos位置插入

  我们发现尾插并不能很好的满足我们对插入的实现。insert就可以选择位置进行插入。当然,我们插入的位置必须是合法的位置。否则程序就会终止。我们看如下例子:

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int> v;
	vector<int> v1(10);

	v.push_back(10);
	v.push_back(20);
	v.push_back(30);

	v.pop_back();

	
	v.reserve(10);

	
	v = v1;

	
	v.insert(v.begin() + 2, 3);
    return 0;
}

  运行结果如下:

【C++】中的vector使用详解及重要部分底层实现,C++,c++,开发语言

  我们是在开始位置往后偏移两个元素的位置进行插入结果也正是如此。细心的同学也会发现,在插入的同时实现的扩容。 具体的扩容大小

2、6 任意位置删除

  尾删也并不能满足我们所需的删除功能。erase可进行任意位置删除。具体例子如下:

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int> v;
	vector<int> v1(10);

	v.push_back(10);
	v.push_back(20);
	v.push_back(30);

	v.pop_back();

	
	v.reserve(10);

	
	v = v1;

	
	v.insert(v.begin() + 2, 3);

	v.erase(v.begin() + 2);
    return 0;
}

   运行结果如下:

【C++】中的vector使用详解及重要部分底层实现,C++,c++,开发语言

   我们就是在之前所插入的位置进行了删除。

2、7 访问vector中的元素

   访问vector中的元素有两种:通过 []  + 下标索引 、迭代器。具体例子如下:

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int> v(10,2);
    int sz = v.size();
	for (int i = 0; i < sz; i++)
	{
		cout << v[i] << " ";
	}
	cout << endl;

	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;

	for (auto it : v)
	{
		cout << it << " ";
	}
	cout << endl;
    return 0;
}

  size()可返回vector中的元素个数。运行结果如下:

【C++】中的vector使用详解及重要部分底层实现,C++,c++,开发语言

  都能够很好的打印出vector中的元素。

2、8 数组中的头和尾元素front()、back()

   front()、back()函数可返回数组中的第一个元素和最后一个元素。当然,我们也可通过下标直接访问。所以这两个函数也并不常用。

 三、部分重要底层实现及常见问题

  vector的底层是由三个指针是私有成员变量。来记录数组的不同位置、大小、容量。实际如下:

	template<class T>

	class vector
	{
	public:
		typedef T* iterator;private:
    private:
		iterator start;
		iterator finish;
		iterator end_of_storage;
	};

  注意,底层使用类模板来试实现的。很好的解决了vector可以存储不同类型的数据问题。

3、1 拷贝构造的底层实现

  拷贝构造底层实现的方式有很多,但思路是大同小异的,具体如下:

		vector(const vector<T>& v)
			:start(nullptr)
			,finish(nullptr)
			,end_of_storage(nullptr)
		{
			iterator tmp = new T[v.size()];
			//memcpy(tmp, v.start, sizeof(T) * v.size());
			//T为自定义类型时,自定义类型自动调用赋值重载,完成深拷贝
			for (size_t i = 0; i < v.size(); i++)
			{
				tmp[i] = v.start[i];
			}

			start = tmp;
			finish = start + v.size();
			end_of_storage = start + v.size();
		}

		//vector(const vector<T>& v)
		//	:start(nullptr)
		//	, finish(nullptr)
		//	, end_of_storage(nullptr)
		//{
		//	reserve(v.size());
		//	for (auto it : v)
		//	{
		//		push_back(it);
		//	}
		//}

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

		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(const vector<T>& v)
			:start(nullptr)
			, finish(nullptr)
			, end_of_storage(nullptr)
		{
			vector<T> tmp(v.begin(), v.end());
			swap(tmp);
		}

3、2 insert的底层实现及迭代器失效

  在实现insert时,我们需要注意的是扩容后,释放掉原来的空间,原来的pos就变成了野指针!需要记录相对位置,更新pos。具体代码如下:

		iterator insert(iterator pos,const T& x)
		{
			assert(pos >= start);
			assert(pos <= finish);
			if (start == end_of_storage)
			{
				//注意,扩容后原来的pos就变为野指针,需要记录相对位置更新pos
				size_t len = pos - start;
				reserve(capacity() == 0 ? 4 : capacity() * 2);
				pos = start + len;
			}

			iterator end = finish - 1;
			while (end >= pos)
			{
				*(end+1) = *end;
				end--;
			}
			*pos = x;
			finish++;

			return pos;
		}
	void test()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		//v.push_back(5);

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

		vector<int>::iterator p = find(v.begin(), v.end(), 3);
		if (p != v.end())
		{
			// 在p位置插入数据以后,不要访问p,因为p可能失效了。
			v.insert(p, 30);

			//cout << *p << endl;
			//v.insert(p, 40);
		}

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

		v.insert(v.begin(), 1);
	}

  我们在用迭代器时,可能会出现很多意想不到的错误。上述代码中的变量 p 为例子,我们能一直在变量 p 位置插入数据吗?答案是不能!!!为什么呢?因为当我们扩容后,原指针 p 所指向的空间就会被释放,p 就变成了野指针!所以,在p位置插入数据以后,不要访问p,因为p可能失效了。这就是所谓的迭代器失效

3、3  erase的底层实现及迭代器失效

   erase的底层实现较为简单,直接更改finish指针即可。我们直接看代码:

		iterator erase(iterator pos)
		{
			assert(pos >= start);
			assert(pos < finish);

			iterator cur = pos + 1;
			while (cur < finish)
			{
				*(cur - 1) = *cur;
				cur++;
			}

			finish--;
			return pos;
		}

  erase并没有扩容,为啥会出现迭代器失效呢?我们先看个例子:

void test_vector4()
{
	// 正常运行
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);

	// 要求删除所有的偶数
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			v.erase(it);
		}

		++it;
	}

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

void test_vector4()
{
	// 崩溃
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

	// 要求删除所有的偶数
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			v.erase(it);
		}
		++it;
	}

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

void test_vector4()
{
	// 结果不对
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(4);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);

	// 要求删除所有的偶数
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			v.erase(it);
		}
			
		++it;
	}

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

   上述准确来说,第一个运行结果正确的为侥幸。为什么呢?注意,erase删除后,后面的元素就会向前移动。并且会返回当前所指向的位置,所以不用再 it++ 了。正确的代码如下:

	 //正确的方式
	void test_vector4()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(4);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);

		// 要求删除所有的偶数
		auto it = v.begin();
		while (it != v.end())
		{
			if (*it % 2 == 0)
			{
				it = v.erase(it);
			}
			else
			{
				++it;

			}
		}

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}

  总的来说,我们进行插入和删除后,就尽可能的不要再次去访问原指针了。很有可能已经失效了,会出现意想不到的效果。

3、4 vector中深拷贝的问题

  vector中,不管是赋值重载还是拷贝构造,都是需要进行深拷贝的。但是vector中元素也必须进行深拷贝。为什么呢?当vector中的元素为int、char等内置类型无所谓,如果是自定义类型,那问题就出来了。

  当vector中的元素为自定义类型,对元素进行先拷贝,元素还是指向的同一块空间。

  vector中存储的为string:

【C++】中的vector使用详解及重要部分底层实现,C++,c++,开发语言

   _str中存储的是string的地址,如果使用浅拷贝,在插入扩容时,就把原来的地址拷贝过来。

【C++】中的vector使用详解及重要部分底层实现,C++,c++,开发语言

  再释放掉原来的地址,就会导致新拷贝的地址变成野指针。具体如下:

 【C++】中的vector使用详解及重要部分底层实现,C++,c++,开发语言文章来源地址https://www.toymoban.com/news/detail-619160.html

到了这里,关于【C++】中的vector使用详解及重要部分底层实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C++】:STL源码剖析之vector类容器的底层模拟实现

    构造一个空vector size和capacity为0 将_start _finish _endofstorage 都置为空指针即可 传统写法 : 1). 新开辟一块和 v 同样容量的空间,更新 _start, _finish, _endofstorage 2). 将 v 中的数据拷贝到新开辟的空间中 注意 : 不要使用memcpy函数拷贝数据,如果数据是内置类型或浅拷贝的自定义类型

    2024年02月04日
    浏览(50)
  • C++中的Vector类详解

    本文详细介绍了C++中vector类的使用方法,包括其定义、迭代器的使用、空间函数、扩容问题以及增删查改操作,旨在帮助读者更好地理解和使用vector。

    2024年02月05日
    浏览(52)
  • 【C++历练之路】list的重要接口||底层逻辑的三个封装以及模拟实现

    W...Y的主页 😊 代码仓库分享💕  🍔前言: 在C++的世界中,有一种数据结构,它不仅像一个神奇的瑰宝匣,还像一位能够在数据的海洋中航行的智慧舵手。这就是C++中的list,一个引人入胜的工具,它以一种优雅而强大的方式管理着数据的舞台。想象一下,你有一个能够轻松

    2024年02月04日
    浏览(36)
  • C++中的vector类模拟实现

    目录 vector模拟实现 vector类设计 vector类构造函数 vector类根据个数构造函数 vector类根据迭代器区间构造函数 vector类拷贝构造函数 vector类赋值运算符重载函数 vector类析构函数 vector类获取有效数据个数函数 vector类获取容量大小函数 vector类begin()函数 vector类end()函数 vector类reser

    2024年04月13日
    浏览(37)
  • 【C++干货铺】解密vector底层逻辑

    ========================================================================= 个人主页点击直达: 小白不是程序媛 C++系列专栏: C++干货铺 代码仓库: Gitee ========================================================================= 目录 vector介绍 vector的使用 vector的定义和使用 vector的空间增长问题 vector的增删查改

    2024年02月05日
    浏览(35)
  • 【C++】vector 基本使用(详解)

    目录 一,vector 的介绍 二,vector 的定义 1,vector() 2,vector(size_type n, const value_type val = value_type()) 3,vector (const vector x) 4,vector (InputIterator first, InputIterator last); 三,vector iterator 的使用 1,begin + end 2,rbegin + rend  四,vector 空间增长问题 1,size 2,capacity 3,empty 4,reserve 5,

    2024年02月03日
    浏览(34)
  • 【C++入门】STL容器--vector底层数据结构剖析

    目录  前言  1. vector的使用       vector的构造  vector迭代器  vector空间相关的接口  vector 功能型接口  find  swap  insert  erase 2. vector内部数据结构剖析 reserve  push_back和pop_back size、capacity、empty、operator[ ];  insert和erase resize swap  拷贝构造和赋值重载 构造函数补充  迭代器

    2024年01月25日
    浏览(52)
  • 探索C++中的动态数组:实现自己的Vector容器

    🎉个人名片 : 🐼作者简介:一名乐于分享在学习道路上收获的大二在校生 🙈个人主页🎉:GOTXX 🐼个人WeChat:ILXOXVJE 🐼本文由GOTXX原创,首发CSDN🎉🎉🎉 🐵系列专栏:零基础学习C语言----- 数据结构的学习之路----C++的学习之路 🐓每日一句:如果没有特别幸运,那就请特

    2024年03月16日
    浏览(45)
  • 【C++初阶】STL详解(四)vector的模拟实现

    本专栏内容为:C++学习专栏,分为初阶和进阶两部分。 通过本专栏的深入学习,你可以了解并掌握C++。 💓博主csdn个人主页:小小unicorn ⏩专栏分类:C++ 🚚代码仓库:小小unicorn的代码仓库🚚 🌹🌹🌹关注我带你学习编程知识 注:为了防止与标准库当中的vector产生命名冲突

    2024年02月05日
    浏览(40)
  • 【C++心愿便利店】No.13---C++之探索vector底层原理

    👧个人主页:@小沈YO. 😚小编介绍:欢迎来到我的乱七八糟小星球🌝 📋专栏:C++ 心愿便利店 🔑本章内容:vector 记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~ 提示:以下是本篇文章正文内容,下面案例可供参考 STL(standard template libaray-标准模板库):是C++标准库的重要组成部

    2024年02月05日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包