【C++】STL标准容器之顺序容器

【C++】STL标准容器之顺序容器,第1张

一、标准容器 1、顺序容器 vector

向量容器

底层数据结构:动态开辟的数组,每次以原来空间大小的2倍进行扩容的

#include 

//定义:
vector<int> vec;

//增加:
vec.push_back(20);  
//在容器末尾添加元素20,O(1),可能导致容器扩容:会在新内存上拷贝构造原来内存上的对象,再把原来内存上的对象一一析构,然后free原来的内存
vec.insert(it, 20);  
//在it迭代器指向的位置前插入元素,返回指向插入的元素的迭代器,后面的元素会向后挪动,O(n),也可能导致扩容

//删除:
vec.pop_back();  //末尾删除元素,O(1)
vec.erase(it);   //删除it迭代器指向的元素,后面的元素会向前移动,O(n)

//查询:
vec[3]; //有operator[]函数,可以通过下标实现随机访问,O(1)
通过iterator迭代器进行遍历
泛型算法find,for_each
foreach => 底层就是通过iterator实现

注意:
对容器进行连续插入或者删除 *** 作(insert/erase),一定要更新迭代器,否则第一次insert或者erase完成,迭代器就失效了

常用方法介绍:
size()  //返回元素个数
empty()  //判空
reserve(20);  //预留空间,只给容器底层开辟指定大小的空间,并不会添加新的元素,size()元素个数仍为0
resize(20);  //重置大小,容器扩容用的,不仅给容器底层开辟指定大小的空间,还会添加新的元素
swap;  //两个容器进行元素交换
函数功能
reserve预分配空间,不初始化
resize重新调整空间大小,会初始化空间
assign清除掉以前的内容,放置新内容

代码示例:

#include 
#include 
using namespace std;

int main()
{
	vector<int> vec; // vector vec; 0 1 2 4 8 16 32 64
	//vec.reserve(20); // 给vector容器预留空间
	vec.resize(20);

	cout << vec.empty() << endl;
	cout << vec.size() << endl; // int()

	for (int i = 0; i < 20; ++i)
	{
		vec.push_back(rand()%100 + 1);
	}

	cout << vec.empty() << endl;
	cout << vec.size() << endl;

	// vector的operator[]运算符重载函数
	int size = vec.size();
	for (int i = 0; i < size; ++i)
	{
		cout << vec[i] << " ";
	}
	cout << endl;

	// 把vec容器中所有的偶数全部删除
	auto it2 = vec.begin();
	while (it2 != vec.end())
	{
		if (*it2 % 2 == 0)
		{
			it2 = vec.erase(it2);  //第一次erase,it2就已经失效了,所以每次都要重新给it2赋值,erase的返回值是删除的元素的下一个元素,所以继续判断下一个元素,如果不能被2整除,++it2
		}
		else
		{
			++it2;
		}
	}

	// 通过迭代器遍历vector容器
	auto it1 = vec.begin();
	for (; it1 != vec.end(); ++it1)
	{
		cout << *it1 << " ";
	}
	cout << endl;

	// 给vector容器中所有的奇数前面都添加一个小于奇数1的偶数   44 45    56 57
	for (it1 = vec.begin(); it1 != vec.end(); ++it1)
	{
		if (*it1 % 2 != 0)
		{
			it1 = vec.insert(it1, *it1-1);//注意迭代器失效,每次都要更新迭代器
			++it1;//insert返回指向插入元素的迭代器,所以要加两次
		}
	}

	for (it1 = vec.begin(); it1 != vec.end(); ++it1)
	{
		cout << *it1 << " ";
	}
	cout << endl;
    
    return 0;
}
deque

双端队列容器

底层数据结构:动态开辟的二维数组,第一维度以2个开始,以2倍的方式进行扩容,每次扩容后,原来第二维的数组从新的第一维数组的下标oldsize/2开始存放,上下都预留相同的空行,以方便支持dequeue的首尾元素的添加,如下列图

一般队列:头删尾插

双端队列:队头队尾都可插可删,初始first,last在容器中间


#include 

//定义:
deque<int> deq;

//增加: 
deq.push_back(20);  //从尾部添加元素,O(1),可能引起扩容
deq.push_front(20);  //从首部添加元素,O(1) 注意:vector没有push_front方法,可以这样实现首部添加vec.insert(vec.begin());
deq.insert(it, 20);  //it迭代器指向的位置添加元素,O(n),后面的元素依次向后挪动

//删除:
deq.pop_back();  //从末尾删除元素,O(1)
deq.pop_front();  //从首部删除元素,O(1)
deq.erase(it);  //从it指向的位置删除元素,O(n)

//查询搜索:
使用iterator,注意连续insert/erase要考虑迭代器失效问题
list

链表容器

底层数据结构:双向的循环链表,链表结点:pre,data,next

增加删除查询 *** 作和deque一样

#include 

//定义:
list<int> li;

//增加: 
li.push_back(20);  //从尾部添加元素,O(1)
li.push_front(20);  //从首部添加元素,O(1) 
li.insert(it, 20);  //it迭代器指向的位置添加元素,O(1),链表中进行insert的时候,经常先要进行一个query查询 *** 作,对于链表来说,查询 *** 作效率比较慢

//删除:
li.pop_back();  //从末尾删除元素,O(1)
li.pop_front();  //从首部删除元素,O(1)
li.erase(it);  //从it指向的位置删除元素,O(1)

//查询搜索:
使用iterator,注意连续insert/erase要考虑迭代器失效问题

dequeue和list比vector多出来的增加删除接口:

push_front和pop_front,因为对于vector来说这两个方法效率太低,O(n),所以干脆就不给提供了

向量、双端队列、链表对比

容器的纵向考察:容器掌握的深度:使用、底层原理

容器的横向考察:各个相似容器之间的对比

vector和deque之间的区别?

vector特点:动态数组,内存是连续的,2倍的方式进行扩容,vector vec,定义一个向量数组,该vec容量是0,有插入 *** 作会扩容到1,0-1-2-4-8… ,可以reserve(20)

deque特点:双端队列,动态开辟的二维数组空间,第二维是固定长度的数组空间,扩容的时候是把第一维的数组进行二倍扩容

答:

  • 底层数据结构的区别:vector动态数组,deque动态开辟的二维数组
  • 前中后插入删除元素的时间复杂度:中间插入都是O(n),末尾插入都是O(1),deque前插O(1),vector没有push_front方法,可以vec.insert(vec.begin());是O(n)
  • 对于内存的使用效率:vector低,vector需要的内存空间必须是连续的,而deque可以分块进行数据存储,只需要分段连续,不需要一大片都连续,所以deque对于内存的利用效率更高些
  • 在中间进行insert或者erase,vector和deque它们的效率谁能好一点?谁能差一点?虽然时间复杂度都是O(n),但是vector由于它整片都是连续的,所以挪动起来更方便,效率相比deque更好

deque底层内存是否是连续的?

答:不是,每一个第二维内部是连续的,但是二维与二维之间并不是连续的,因为第二维是动态扩容开辟,分段连续

vector和list之间的区别?

  • 底层数据结构:vector动态数组,list双向循环链表
  • 数组增加删除是O(n),涉及元素的移动,链表增加删除结点是O(1)
  • 数组查询O(n),随机访问arr[i],O(1),而链表查询也是O(n),但不支持随机访问

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/676056.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-19
下一篇 2022-04-19

发表评论

登录后才能评论

评论列表(0条)

保存