C++ | STL vector容器

news/2024/7/10 18:23:28 标签: vector, 迭代器, 容器, vector容器, stl

目录

vector%E5%AE%B9%E5%99%A8-toc" style="margin-left:80px;">一.简述vector容器

vector%E7%9A%84%E5%88%9B%E5%BB%BA%E6%96%B9%E5%BC%8F-toc" style="margin-left:80px;">二.vector的创建方式

vector%E5%AE%B9%E5%99%A8%E7%9A%84%E6%8F%92%E5%85%A5%E5%92%8C%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C-toc" style="margin-left:80px;">三.vector容器的插入和删除操作

vector%E5%AE%B9%E5%99%A8%E7%9A%84%E6%89%A9%E5%AE%B9%E6%93%8D%E4%BD%9C-toc" style="margin-left:80px;"> 四.vector容器的扩容操作

vector%E5%AE%B9%E5%99%A8">一.简述vector容器

vector是一个矢量容器，其在底层为一个数组，所需要的头文件为#include<vector>

我们知道数组的逻辑地址和物理地址都是连续的，所以我们可以使用指针的直接跳转来访问数组的任意一个位置，例如

arr[1]=>*(arr+1)  

arr[0]=>*arr

牢记这一点是非常重要的，因为后续我们可以使用类似的方法，来使用迭代器对vector容器进行操作。（我们可以吧迭代器简单的理解为一个指向某一容器的指针）,而且并不是所有的容器的逻辑和物理地址都是连续的。

vector%E7%9A%84%E5%88%9B%E5%BB%BA%E6%96%B9%E5%BC%8F">二.vector的创建方式

#include<iostream>
#include<vector>//vector容器的头文件
#include<iterator>//迭代器的头文件

int main()
{
	std::vector<int> vec1;//默认构造函数  所有容器  都有默认构造函数 

	std::vector<int> vec2(10);//10(count)个大小的数据，0 

	std::vector<int> vec3(10, 20);//10(count)，20(val)   

	int arr[] = { 123, 2, 343, 423, 54, 5, 7 };
	int len = sizeof(arr) / sizeof(arr[0]);
	std::vector<int> vec4(arr, arr + len);//按迭代器的插入

        std::vector<int> vec5(vec4.begin(),vec4.end());

	return 0;
}

在构造vector容器vec1时，调用的是vector类中默认的构造函数，（所有的容器中都有默认的构造函数），且构造的同时没有做任何事情。

在构造vector容器vec2时，我们显式的给定了这个容器的初始大小10，并且将这10个大小的数据置为0。

在构造vector容器vec3时，我们显式的给定了这个容器的初始大小10，且显式的将这10个大小的数据置为20。即我们给vec3中插入了10个值为20的数据。

在构造vector容器vec4时，我们将数组arr的首地址（第一个元素的地址）和arr的尾地址（最后一个元素的后一个地址）传给vec4

我们知道在数组arr中arr+len已经越界了，所以此时arr+len指向了无效的区间，而这正好构成了迭代器所需要的半开半闭的区间。所以这里的arr和arr+len可以当做迭代器来理解，也就是说将数组arr中的数据全部插入到vector容器vec4当中。这种插入方式叫做按迭代器区间插入。

构造vec5的方式与构造vec4的方式相同。

我们使用迭代器来遍历容器，避免暴露容器的内部，保护了数据的安全。

vector%E5%AE%B9%E5%99%A8%E7%9A%84%E6%8F%92%E5%85%A5%E5%92%8C%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C">三.vector容器的插入和删除操作

#include<iostream>
#include<vector>
#include<algorithm>

template<typename Iterator>
void Show(Iterator first, Iterator last)
{
	for (first; first != last; first++)
	{
		std::cout << *first << " ";
	}
	std::cout << std::endl;
}

int main()
{
	std::vector<int> vec;

	for (int i = 0; i < 5; i++)
	{
		vec.push_back(i + 1);
	}
	Show(vec.begin(), vec.end());

	vec.insert(vec.begin() + 1, 10);
	Show(vec.begin(), vec.end());

	vec.pop_back();
	vec.erase(vec.begin() + 3);
	Show(vec.begin(), vec.end());

	return 0;
}

 

vector容器不支持头部插入和头部删除，因为vector容器的底层是数组，是矢量容器，即一端固定。

push_back()代表在vector容器的尾部插入元素（尾插），参数为要插入的值，时间复杂度为O(1)

insert()代表按位置插入，第一个参数为要插入的位置，第二个参数为要插入的值，时间复杂度为O(n)，因为当在某一位置插入一个数据时，当前位置的数据以及后面的数据全部都要向后移。

pop_back()代表尾删，即删除尾部的元素，时间复杂度为O(1)

erase()，代表按位置删除，参数为要删除元素的位置，时间复杂度为O(n)，因为当删除某一位置的数据时，当前位置后面的数据全部都要往前移。

访问，即Show()函数的时间复杂度为O(1)。

所以vector容器的特点为 “尾部快速的插入或删除，可以直接访问任何元素”，缺点为“按位置插入或删除的效率低”。

泛型算法1

#include<iostream>
#include<vector>
#include<iterator>//迭代器的头文件
#include<algorithm>//泛型算法的头文件

//泛型算法
template<typename Iterator,
	typename Valty>
	Iterator Find(Iterator first, Iterator last, Valty val)
{
	for (first; first != last; first++)
	{
		if (*first == val)
		{
			break;
		}
	}
	return first;
}
/*
	打印任意容器中的数据   打印函数  泛型算法
*/
template<typename Iterator>
void Show(Iterator first, Iterator last)
{
	for (first; first != last; first++)
	{
		std::cout << *first << " ";
	}
	std::cout << std::endl;
}
int main()
{
	int arr[] = { 123, 2, 35, 46, 756, 8, 79 };
	int len = sizeof(arr) / sizeof(arr[0]);
	std::vector<int> vec(arr, arr + len);
	Show(vec.begin(), vec.end());
	Show(vec.begin(), vec.begin() + 3);
	/*
		查vec中的某个值
	*/
	std::vector<int>::iterator fit = Find(vec.begin(), vec.end(), 46);
	if (fit != vec.end())
	{
		std::cout << *fit << std::endl;
	}
	return 0;
}

我们知道遍历一个容器是用迭代器来进行的，所以在上述的泛型算法Show和Find当中，我们定义了模板类型参数Iterator来实现这两个泛型算法，当我们调用这两个函数时，分别将某个容器的迭代器区间传入，接着就可以进行打印或者查找操作了。

vector%E5%AE%B9%E5%99%A8%E7%9A%84%E6%89%A9%E5%AE%B9%E6%93%8D%E4%BD%9C"> 四.vector容器的扩容操作

#include<iostream>
#include<vector>
#include<iterator>//迭代器的头文件
#include<algorithm>//泛型算法的头文件

int main()
{
	std::vector<int> vec;
	for (int i = 0; i < 10; i++)
	{
		vec.push_back(i + 1);
	}
	std::cout << vec.size() << std::endl;
	std::cout << vec.max_size() << std::endl;//最大可插入的元素个数
	
	return 0;
}

 

push_back的意思是向vec中插入数据（尾部插入），因为vector容器的底层实现是一个数组，当我们使用vector容器时，系统并不知道我们要给vector开辟的大小是多少，如果系统一开始给vector设置的大小非常大，但使用者仅仅使用了一小块，那么就会浪费大量的内存空间，相反，如果设置vector的大小小了，而使用者需要非常大的空间，就会出现不够用的现象出现，因此vector拥有自己的扩容机制。

首先让栈上的一个指针（这个指针就是vector中的一个指针）指向堆上的一块内存，例如在上述代码中，首先插入的元素为1，当要插入2时，发现空间不足了，那么系统就会开辟一个新的空间，这块新空间的大小是原来的2倍，接着将旧空间中的数据拷贝到新空间中，然后释放掉旧的内存空间，最后让指针ptr指向新的内存空间。

现在我们就可以插入2了。

综上所述vector容器的扩容机制为：

  1. 以倍数的形式开辟更大的空间
  2. 旧的数据拷贝到新的空间
  3. 释放旧的空间
  4. 指针指向新的空间

这里的max_size为1073741823是因为4294967294是2^32，也就是用一个int表示长度，能表示的最大值。1073741823是上一个值的1/4，如果有什么原因它需要的存储是前者的4倍的话，那么最大值就是1/4。这个应该是C++编译器/标准库规范/操作系统决定的， 不是电脑配置决定的。

泛型算法2

#include<iostream>
#include<vector>
#include<algorithm>

template<typename Iterator>
void Show(Iterator first, Iterator last)
{
	for (first; first != last; first++)
	{
		std::cout << *first << " ";
	}
	std::cout << std::endl;
}

template<typename Iterator>
void Sort_High(Iterator first, Iterator last)
{
	Iterator i = first;
	Iterator j = first;
	int k = 0;
	for (i = first; i < last - 1; i++, k++)
	{
		for (j = first; j < last - k - 1; j++)
		{
			if (*j > *(j + 1))
			{
				typename Iterator::value_type tmp = *j;
				*j = *(j + 1);
				*(j + 1) = tmp;
			}
		}
	}
}

int main()
{
	int arr[] = { 12, 3, 234, 3, 6, 4 };
	int len = sizeof(arr) / sizeof(arr[0]);
	std::vector<int> vec(arr, arr + len);
	std::sort(vec.begin(), vec.end(), std::greater<int>());
	Show(vec.begin(), vec.end());
	return 0;
}

上述代码是利用泛型算法编写的一个关于vector的冒泡排序，我们知道遍历一个容器是利用迭代器来实现的，但在上述代码中我们要特别注意在第二层for循环中，j<last - k -1 而不是 j<last - i - 1，因为此时i是一个迭代器，而last-i就是迭代器与迭代器相减，得到的是偏移，最后就变成了 j<偏移，而这里的j也是一个迭代器，而迭代器是不能与偏移左比较的，所以我们要额外定义一个变量k，让j<last-k-1，这样才是正确的。

代码中typename Iterator::value_type tmp 表示的意思是迭代器所迭代到的类型，也就是此时容器中存放的元素的类型。此时tmp的类型就与容器中存放着的数据的类型一致了。

当然vector容器的底层也有给定的排序方法，sort()

#include<iostream>
#include<vector>
#include<algorithm>

template<typename Iterator>
void Show(Iterator first, Iterator last)
{
	for (first; first != last; first++)
	{
		std::cout << *first << " ";
	}
	std::cout << std::endl;
}

int main()
{
	int arr[] = { 12, 3, 234, 3, 6, 4 };
	int len = sizeof(arr) / sizeof(arr[0]);
	std::vector<int> vec(arr, arr + len);
	std::sort(vec.begin(), vec.end(), std::greater<int>());
	Show(vec.begin(), vec.end());
	return 0;
}

sort()函数中的第三个参数std::greater<int>()表示从大到小排序，相反std::less<int>()就代表从小到大排序。

#include<iostream>
#include<vector>
#include<algorithm>

template<typename Iterator>
void Show(Iterator first, Iterator last)
{
	for (first; first != last; first++)
	{
		std::cout << *first << " ";
	}
	std::cout << std::endl;
}

int main()
{
	int arr[] = { 12, 3, 234, 3, 6, 4 };
	int len = sizeof(arr) / sizeof(arr[0]);
	std::vector<int> vec(arr, arr + len);
	std::sort(vec.begin(), vec.end(), std::less<int>());
	Show(vec.begin(), vec.end());
	return 0;
}

当然你也可以不写第三个参数，这是sort会默认从小到大排序。

#include<iostream>
#include<vector>
#include<algorithm>

template<typename Iterator>
void Show(Iterator first, Iterator last)
{
	for (first; first != last; first++)
	{
		std::cout << *first << " ";
	}
	std::cout << std::endl;
}

int main()
{
	int arr[] = { 12, 3, 234, 3, 6, 4 };
	int len = sizeof(arr) / sizeof(arr[0]);
	std::vector<int> vec(arr, arr + len);
	std::sort(vec.begin(), vec.end());
	Show(vec.begin(), vec.end());
	return 0;
}


http://www.niftyadmin.cn/n/1629347.html

相关文章

最新编程语言排行榜

最新编程语言排行榜

前10名编程语言走势图 20到50名语言排行 PositionProgramming LanguageRatings21MATLAB0.573%22D0.539%23Logo0.535%24SAS0.517%25Visual Basic .NET0.481%26COBOL0.476%27Scheme0.427%28C shell0.422%29R0.422%30NXT-G0.410%31Fortran0.381%32Go0.375%33ABAP0.369%34Erlang0.3…
阅读更多...
微信小程序——radio/radio大小改变

微信小程序——radio/radio大小改变

css样式改变大小&#xff1a;transform:scale(.7);转载于:https://www.cnblogs.com/lemon-flm/p/8572136.html
阅读更多...
C++ | STL list容器

C++ | STL list容器

目录 一.简述list容器 二.list容器创建方式 三.list容器的插入和删除操作 四.关于list容器迭代器的使用方法 五.关于list容器的sort 一.简述list容器 list是双向链表容器&#xff0c;也就是说它的底层是一个双向循环链表。所需头文件#include<list> 因为list是双向链…
阅读更多...
一致性hash算法 - consistent hashing

一致性hash算法 - consistent hashing

一致性hash算法&#xff08;consistent hashing&#xff09; 张亮 consistent hashing算法早在1997年就在论文Consistent hashing and random trees中被提出&#xff0c;目前在cache系统中应用越来越广泛&#xff1b; 1基本场景 比如你有N个cache服务器&#xff08;后面简称…
阅读更多...
spring 实现定时任务

spring 实现定时任务

spring实现定时任务超级简单。比使用quartz简单&#xff0c;比使用timer强大。如下是一个简单的springboot任务&#xff0c;启用了定时任务 SpringBootApplicationComponentScanEnableScheduling //这里添加注解public class Application implements CommandLineRunner { //…
阅读更多...
C++ | STL deque容器

C++ | STL deque容器

目录 一.简述deque容器 二.deque的创建方式 三.deque容器的插入和删除操作 四.deque的底层形式以及扩容方式。 五.deque容器底层内存连续的实现方法 一.简述deque容器 deque是一个双端队列容器&#xff0c;其在底层为一个双端队列&#xff0c;所需要的头文件为#include&l…
阅读更多...
Linux┊RPM 的介绍和应用

Linux┊RPM 的介绍和应用

摘要&#xff1a;RPM 是 Red Hat Package Manager 的缩写&#xff0c;原意是Red Hat 软件包管理&#xff1b;本文介绍RPM&#xff0c;并结合实例来解说RPM手工安装、查询等应用&#xff1b;正文&#xff1a;RPM 是 Red Hat Package Manager 的缩写&#xff0c;本意是Red Hat 软…
阅读更多...
ReactNative学习笔记（六）集成视频播放

ReactNative学习笔记（六）集成视频播放

概述 视频播放可以自己写原生代码实现&#xff0c;然后注入JS。如果对视频播放没有特殊要求的话&#xff0c;可以直接使用现成插件。 到官方推荐的插件网站搜索找到下载量第一的插件&#xff1a;react-native-video。 安装 安装很简单&#xff1a; npm install -g react-native…
阅读更多...
最新文章

Copyright @ 2022~2023