【STL】容器分类及用法(图文+代码详解)-创新互联
顺序容器(sequence containers)
成都创新互联公司坚持“要么做到,要么别承诺”的工作理念,服务领域包括:网站设计、成都做网站、企业官网、英文网站、手机端网站、网站推广等服务,满足客户于互联网时代的连山网站设计、移动媒体设计的需求,帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴!1.vector
结构如下图所示
只可通过push_back()从尾部添加元素vector
vec; 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可以从两端添加 deque
deq={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 list
mylist = {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,并指向itrmylist1.splice(itr,mylist2,itr_a,itr_b);//O(1),
4.forward list:单向链表,只有一个后继指针
5.array比普通数组更安全,功能更强大
//Array详解------------------------------ int a[3] = {3,4,5}; array
a = {3,4,5}; //array的大小不可变 关联容器(associative containers)
是基于红黑树来实现的,没有push_back/front操作且不会有重复元素,容器有序
1.set
set详解(代码举例介绍)int main(){set
myset; //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没有重复的键值 map
mymap; 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_set
myset = {"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_map
day={{'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()操作
试分析下列代码
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://scyanting.com/article/ddphih.html