189 8069 5689

【STL】容器分类及用法(图文+代码详解)-创新互联

STL容器
  • 顺序容器(sequence containers)

    成都创新互联公司坚持“要么做到,要么别承诺”的工作理念,服务领域包括:网站设计、成都做网站、企业官网、英文网站、手机端网站、网站推广等服务,满足客户于互联网时代的连山网站设计、移动媒体设计的需求,帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴!

    1.vector
    结构如下图所示
    在这里插入图片描述
    只可通过push_back()从尾部添加元素

    vectorvec;
    	vec.push_back(2);
    	vec.push_back(1);
    	vec.push_back(8);

    获取元素时

    cout<

    遍历vector的三种操作

    //vector可以像遍历数组一样被遍历
    	for(int i=0;i::iterator itr=vec.begin();itr!=vec.end();++itr)cout<<*itr<

    所有容器都具备的5个功能函数

    if(vec.empty()){cout<<"impossible"<vec2(vec);//3)复制整个容器
    	
    	vec.clear();//4)清除容器中所有元素,此时vec.size()==0
    	
    	vec2.swap(vec);//5)交换两个数组中的元素
    	//此时vec2.size()==0,vec.size()==3
    

    2.deque(double-ended queue)
    结构如英文,是一个双端队列
    在这里插入图片描述
    deque可从两端添加元素,效率极高,复杂度为O(1),但从中间添插入元素的复杂度为O(n),查询的时间复杂度也为O(n)

    //deque详解-------------------------------
    	
    	//deque与vector的区别就是vector只能从尾部添加元素,而deque可以从两端添加
    	dequedeq={4,1,7};
    	
    	deq.push_front(2);//deq:{2,4,1,7}
    	
    	deq.push_back(10);//deq:{2,4,1,7,10}
    	
    

    deque特点:慢插入(中间)O(n)/慢查询 O(n)

    3.list
    结构如图
    在这里插入图片描述
    如图,list是一个双向链表

    //List详解--------------------------------
    	//--double linked list
    	listmylist = {5,2,9};
    	mylist.push_back(6);//mylist:{5,2,9,6}
    	mylist.push_front(4);//mylist:{4,5,2,9,6}
    	list::iterator itr = find(mylist.begin(),mylist.end(),2);//itr 此时指向mylist中2的位置
    	mylist,insert(itr,8);//mylist:{4,5,8,2,9,6}//list插入的复杂度是O(1),快插入
    	itr++;//插入是在itr所指向的2的前一个位置发生的,itr扔指向2,itr++后itr指向9
    	mylist.erase(itr);//删除itr所指向的元素9,mylist:{4,5,8,2,6}	
    

    list特征:快插入,慢查询O(n)
    没有像vector、deque一样的[]操作符;
    因为list的存储结构是链表,不是顺序存储,使用list时,高速缓存cache命中率低,list的查询时间复杂度虽然是O(n)但实际上更慢。
    由于list的每一个元素都包含了两个指针,所以list的内存占用相比vector更多
    list有一个独占的优势功能,splice切分mylist2中itr_a到itr_b中的元素并复制到mylist1,并指向itr

    		mylist1.splice(itr,mylist2,itr_a,itr_b);//O(1),
    		

    4.forward list:单向链表,只有一个后继指针

    5.array比普通数组更安全,功能更强大

    //Array详解------------------------------
    	
    	int a[3] = {3,4,5};
    	arraya = {3,4,5};
    	//array的大小不可变
    	
  • 关联容器(associative containers)
    是基于红黑树来实现的,没有push_back/front操作且不会有重复元素,容器有序
    1.set
    在这里插入图片描述
    set详解(代码举例介绍)

    int main(){setmyset;
    	//set的插入时间复杂度是O(logn)
    	myset.insert(3);//myset:{3}
    	myset.insert(1);//myset:{1,3}
    	myset.insert(7);//myset:{1,3,7}
    	set::iterator it;
    	//set的查找(search)时间复杂度也是O(logn)
    	it = myset.find(7);//it->7,顺序容器没有find函数
    	pair::iterator,bool>ret;
    	ret = myset.insert(3);//因为 myset中已经有 3,所以插入失败,没有新元素被插入
    	if(ret.second==false){//因为插入失败,所以现在ret.second==false
    		it=ret.first;//it现在指向myset中的3
    	}
    	myset.insert(it,9);//成功插入,此时myset:{1,3,7,9},不会插入在it指向的位置,而是9在排序后应该在的位置,跟it指向哪没有关系
    	//但如果it正好指向应该插入的地方,那么会大大降低复杂度,O(logn)->O(1)
    	myset.erase(it);//此时myset:{1,7,9}
    	myset.erase(7);//此时myset:{1,9}
    	//能够直接删除值而不是迭代器,这是顺序容器所不具有的删除方式
    
    	//set:元素的值是不能被修改的
    	*it = 10;//*it类型为只读类型
    	//set的遍历相对于vector和deque会慢很多,且没有[]操作符,元素都有序

    2.map
    在这里插入图片描述
    map详解

    //map详解--------------------------------------------------------------------
    	//map维护一个键值对,第一个元素为key值,map没有重复的键值
    	mapmymap;
    	mymap.insert(pair('a',100));//类模板需要声明数据类型
    	mymap.insert(make_pair('z',200));//函数模板不需要声明数据类型
    	map::iterator it = mymap.begin();
    	mymap.insert(it,pair('b',300));
    	it = mymap.find('z'); //O(logn)
    	for(it=mymap.begin();it!=mymap.end();it++){cout<<(*it).first<<"=>"<<(*it).second<

    3.multiset/multimap

    //multiset允许有重复元素
    		//set/multiset:元素的值是不能被修改的
    		*it = 10;//*it类型为只读类型
    		//set/multiset的遍历相对于vector和deque会慢很多,且没有[]操作符,元素都有序
    		//与multiset类似,multimap允许有重复的键值,且键值都只读,不可被修改*it:pair
  • 无序容器(unordered containers )
    C++11新增的容器,通过哈希表实现
    在这里插入图片描述

    1.unordered_set
    详解

    unordered_setmyset = {"res","green","blue"};
    	unordered_set::const_iterator itr = myset.find("green");//查找时间复杂度O(1)
    	if(itr!=myset.end()){cout<<*itr<vec={"purple","pink"};
    	myset.insert(vec.begin(),vec.end());
    	//哈希表独有的api
    	cout<

    哈希冲突会导致性能下降,性能会从O(1)下降到O(n)(最坏的情况就是当所有元素都放在一个桶里),因此不如map、set稳定,因为map,set用的是平衡树。
    2.unordered_map

    //无序set和map的键值和元素值都不能被修改
    	//例如:
    	unordered_mapday={{'S',"Sunday"},{'M',"Monday"}};
    	cout<vec = {1,2,3};
    	vec[5]=5;//编译错误
    	day['W']="Wednesday";//编译成功,插入{'W',"Wednesday"}
    	day.insert(make_pair('F',"Friday"));//插入{'F',"Friday"}
    	cout<<"测试"<

    对于const类型的unorder_map,在访问值时必须要使用迭代器

    void foo(const unordered_map&m){m['S']="SUNDAY";//会报错,因为const所以不能修改
    	cout<//注意判断
    		cout<<*itr<
基于基础容器类型拓展的适配器类

1.stack,栈:后进先出,有push(),pop(),top()操作
2.queue,队列:先进先出,有push(),pop(),front(),back()操作
3.priority queue,优先队列:最高级别的元素先进先出,有push(),pop(),top()操作

容器总结:顺序存储(vector,deque),链表存储(list,associate,unordered)

试分析下列代码

vectorvec={1,2,3,4};
int *p=&vec[2];//*p=3
vec.insert(vec.begin(),0);//此时vec:{0,1,2,3,4}
cout<<*p<

此时会输出什么?
第一次运行结果
在这里插入图片描述
第二次运行:
在这里插入图片描述
可以看出输出的值似乎是随机的,因为STL的内存管理机制会因为vector内存不足开辟新内存并将vec中的值复制到新内存中,导致p指针指向不确定
如果运气好,*p会输出2,如果发生了内存复制,*p的值会是一个随机值(如上所示的两次运行),甚至有可能导致程序崩溃
这种行为是不可预测的,这也是顺序存储结构的缺点,而链表存储就不会有这种问题

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


名称栏目:【STL】容器分类及用法(图文+代码详解)-创新互联
文章出自:http://cdxtjz.cn/article/ddphih.html

联系我们

您好HELLO!
感谢您来到成都网站建设公司,若您有合作意向,请您为我们留言或使用以下方式联系我们, 我们将尽快给你回复,并为您提供真诚的设计服务,谢谢。
  • 电话:028- 86922220 18980695689
  • 商务合作邮箱:631063699@qq.com
  • 合作QQ: 532337155
  • 成都网站设计地址:成都市青羊区锣锅巷31号五金站写字楼6楼

小谭建站工作室

成都小谭网站建设公司拥有多年以上互联网从业经验的团队,始终保持务实的风格,以"帮助客户成功"为已任,专注于提供对客户有价值的服务。 我们已为众企业及上市公司提供专业的网站建设服务。我们不只是一家网站建设的网络公司;我们对营销、技术、管理都有自己独特见解,小谭建站采取“创意+综合+营销”一体化的方式为您提供更专业的服务!

小谭观点

相对传统的成都网站建设公司而言,小谭是互联网中的网站品牌策划,我们精于企业品牌与互联网相结合的整体战略服务。
我们始终认为,网站必须注入企业基因,真正使网站成为企业vi的一部分,让整个网站品牌策划体系变的深入而持久。