重庆分公司,新征程启航
为企业提供网站建设、域名注册、服务器等服务
顺序容器(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()操作
试分析下列代码
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元起,快前往官网查看详情吧