deque:全称double-endedqueue,双端队列
适合栈和队列的操作,不过同样支持random access#include <iostream> #include <deque> using namespace std; int main(){ deque<int> values; values.push_back(19); //push_back(T) values.push_front(21); //push_front(T) values.push_front(9); for(int i=0;i<values.size();i++){ cout<<values[i]<<endl; //operator[] } cout<<values[0]<<endl; values.pop_front(); //pop_front() cout<<values[0]<<endl; cout<<values[values.size()-1]<<endl; values.pop_back(); //pop_back() cout<<values[values.size()-1]<<endl; return 0; }
priority_queue:实现最小堆和最大堆
注意:
即使最小堆中元素为基本类型(如,int),也不能直接声明
priority_queue<int>qmax;
因为,priority_queue<int>默认按照 < 运算符 的定义比较堆中的元素,并且默认是堆的根部为 <运算符 比较得到的最大元素 (即默认最大堆实现)。
为了简化实现,只要记住统一将 堆中元素设置为自定义的struct 即可!
#include<iostream> #include<queue> using namespace std; struct MAX { int x; }t; struct MIN { int x; }s; bool operator<(const MAX &a,const MAX &b) { return a.x<b.x; }//大根堆 bool operator<(const MIN &a,const MIN &b) { return a.x>b.x; }//小根堆 priority_queue<MAX>qmax; priority_queue<MIN>qmin; int a,n,i; int main() { cout<<"输入n"<<endl; cin>>n; cout<<"输入n个数"<<endl; for(i=1;i<=n;i++) { cin>>a; t.x=a; qmax.push(t); s.x=a; qmin.push(s); } while(!qmax.empty()) { a=qmax.top().x; cout<<a<<" "; qmax.pop(); } cout<<endl; while(!qmin.empty()) { a=qmin.top().x; cout<<a<<" "; qmin.pop(); } cout<<endl; system("pause"); return 0; }
map:
需要#include <map>
定义map<int, int> m;
#include <map> #include <iostream> #include <string> using namespace std; int main(void){ map<int,int> m; if(m.find(3)==m.end()){ cout<<"none: "<<m[3]<<endl; m[3]=1; cout<<m[3]<<endl; }else{ cout<<m[3]<<endl; m[3]++; cout<<m[3]<<endl; } if(m.find(3)==m.end()){ cout<<"none: "<<m[3]<<endl; m[3]=1; cout<<m[3]<<endl; }else{ cout<<m[3]<<endl; m[3]++; cout<<m[3]<<endl; } m[1]=5; m[2]=0; cout<<endl; map<int,int>::iterator iter; for(iter=m.begin();iter!=m.end();iter++){ cout<<(*iter).first<<", "<<(*iter).second<<endl; } //system("pause"); return 0; }
vector:最好不要模拟栈和队列,因为底层是数组实现
这里从虚函数的应用引出vector的使用,看看vector如何来模拟普通队列和栈的使用的:)
#include <iostream> #include <vector> using namespace std; class A{ public: virtual void f(){ cout<<"A f()"<<endl; } }; class B: public A{ public: virtual void f(){ cout<<"B f()"<<endl; } }; int main(){ //1. 虚函数的经典使用 //vector vector<A*> v; v.push_back(new A()); v.push_back(new B()); v[0]->f(); v[1]->f(); //array A* v2[5]; v2[0]=new B(); v2[1]=new A(); v2[2]=new B(); v2[0]->f(); v2[1]->f(); v2[2]->f(); //2. 刚才用到了vector,现在拓展一下,顺便来看看stl中的vector //queue cout<<"queue implemented by vector==>"<<endl; vector<int> q; q.push_back(3); //入队 q.push_back(4); q.push_back(5); cout<<q[0]<<endl; //访问队首 q.erase(q.begin(), q.begin()+1); //出队 cout<<q[0]<<endl<<endl; //stack cout<<"stack implemented by vector==>"<<endl; vector<int> s; s.push_back(3); //入栈 s.push_back(4); s.push_back(5); cout<<s[s.size()-1]<<endl; //访问栈顶 s.pop_back(); //出栈 cout<<s[s.size()-1]<<endl; s.pop_back(); return 0; }
使用 sort( v.begin() , v.end() ) 和 vector::operator[],举求中位数例子:
#include <iostream> #include <algorithm> #include <vector> using namespace std; int main(){ vector<double> scores; scores.push_back(91); scores.push_back(93); scores.push_back(95); scores.push_back(96); sort(scores.begin(),scores.end()); cout<<"median="; if((scores.size()%2)==1){ cout<<scores[scores.size()/2]<<endl; }else{ double scores1=scores[scores.size()/2-1]; double scores2=scores[scores.size()/2]; cout<<(scores1+scores2)/2<<endl; } return 0; }
注意:将element插入container是复制,不是插入引用!
#include <iostream> #include <vector> using namespace std; int main(){ vector<int> q; int arr[]={3,4,5,6}; q.push_back(arr[0]); q.push_back(arr[1]); q.push_back(arr[2]); q.push_back(arr[3]); //insert一个element到container是"复制"的方式,因此修改原对象不影响insert的对象. //换言之,"原对象"和"insert的对象"完全独立,只是在插入时候调用了copy constructor(???实践) arr[2]=999; vector<int>::const_iterator it; for(it=q.begin();it!=q.end();it++){ cout<<*it<<" "; } return 0; }
set:
/* set/multiset会根据待定的排序准则,自动将元素排序。两者不同在于前者不允许元素重复,而后者允许。 1) 不能直接改变元素值,因为那样会打乱原本正确的顺序,要改变元素值必须先删除旧元素,则插入新元素 2) 不提供直接存取元素的任何操作函数,只能通过迭代器进行间接存取,而且从迭代器角度来看,元素值是常数 3) 元素比较动作只能用于型别相同的容器(即元素和排序准则必须相同) set模板原型://Key为元素(键值)类型 template <class Key, class Compare=less<Key>, class Alloc=STL_DEFAULT_ALLOCATOR(Key) > 从原型可以看出,可以看出比较函数对象及内存分配器采用的是默认参数,因此如果未指定,它们将采用系统默认方式, 另外,利用原型,可以有效地辅助分析创建对象的几种方式 */ #include <iostream> #include <string> #include <set> using namespace std; struct strLess { bool operator() (const char *s1, const char *s2) const { return strcmp(s1, s2) < 0; } }; void printSet(set<int> s) { copy(s.begin(), s.end(), ostream_iterator<int>(cout, ", ") ); // set<int>::iterator iter; // for (iter = s.begin(); iter != s.end(); iter++) // //cout<<"set["<<iter-s.begin()<<"]="<<*iter<<", "; //Error // cout<<*iter<<", "; cout<<endl; } void main() { //创建set对象,共5种方式,提示如果比较函数对象及内存分配器未出现,即表示采用的是系统默认方式 //创建空的set对象,元素类型为int, set<int> s1; //创建空的set对象,元素类型char*,比较函数对象(即排序准则)为自定义strLess set<const char*, strLess> s2( strLess); //利用set对象s1,拷贝生成set对象s2 set<int> s3(s1); //用迭代区间[&first, &last)所指的元素,创建一个set对象 int iArray[] = {13, 32, 19}; set<int> s4(iArray, iArray + 3); //用迭代区间[&first, &last)所指的元素,及比较函数对象strLess,创建一个set对象 const char* szArray[] = {"hello", "dog", "bird" }; set<const char*, strLess> s5(szArray, szArray + 3, strLess() ); //元素插入: //1,插入value,返回pair配对对象,可以根据.second判断是否插入成功。(提示:value不能与set容器内元素重复) //pair<iterator, bool> insert(value) //2,在pos位置之前插入value,返回新元素位置,但不一定能插入成功 //iterator insert(&pos, value) //3,将迭代区间[&first, &last)内所有的元素,插入到set容器 //void insert[&first, &last) cout<<"s1.insert() : "<<endl; for (int i = 0; i <5 ; i++) s1.insert(i*10); printSet(s1); cout<<"s1.insert(20).second = "<<endl;; if (s1.insert(20).second) cout<<"Insert OK!"<<endl; else cout<<"Insert Failed!"<<endl; cout<<"s1.insert(50).second = "<<endl; if (s1.insert(50).second) {cout<<"Insert OK!"<<endl; printSet(s1);} else cout<<"Insert Failed!"<<endl; cout<<"pair<set<int>::iterator::iterator, bool> p;\np = s1.insert(60);\nif (p.second):"<<endl; pair<set<int>::iterator::iterator, bool> p; p = s1.insert(60); if (p.second) {cout<<"Insert OK!"<<endl; printSet(s1);} else cout<<"Insert Failed!"<<endl; //元素删除 //1,size_type erase(value) 移除set容器内元素值为value的所有元素,返回移除的元素个数 //2,void erase(&pos) 移除pos位置上的元素,无返回值 //3,void erase(&first, &last) 移除迭代区间[&first, &last)内的元素,无返回值 //4,void clear(), 移除set容器内所有元素 cout<<"\ns1.erase(70) = "<<endl; s1.erase(70); printSet(s1); cout<<"s1.erase(60) = "<<endl; s1.erase(60); printSet(s1); cout<<"set<int>::iterator iter = s1.begin();\ns1.erase(iter) = "<<endl; set<int>::iterator iter = s1.begin(); s1.erase(iter); printSet(s1); //元素查找 //count(value)返回set对象内元素值为value的元素个数 //iterator find(value)返回value所在位置,找不到value将返回end() //lower_bound(value),upper_bound(value), equal_range(value) 略 cout<<"\ns1.count(10) = "<<s1.count(10)<<", s1.count(80) = "<<s1.count(80)<<endl; cout<<"s1.find(10) : "; if (s1.find(10) != s1.end()) cout<<"OK!"<<endl; else cout<<"not found!"<<endl; cout<<"s1.find(80) : "; if (s1.find(80) != s1.end()) cout<<"OK!"<<endl; else cout<<"not found!"<<endl; //其它常用函数 cout<<"\ns1.empty()="<<s1.empty()<<", s1.size()="<<s1.size()<<endl; set<int> s9; s9.insert(100); cout<<"s1.swap(s9) :"<<endl; s1.swap(s9); cout<<"s1: "<<endl; printSet(s1); cout<<"s9: "<<endl; printSet(s9); //lower_bound,upper_bound,equal_range(略) }
///////////////i测试结果/////////////////////////
s1.insert() :
0, 10, 20, 30, 40,
s1.insert(20).second =
Insert Failed!
s1.insert(50).second =
Insert OK!
0, 10, 20, 30, 40, 50,
pair<set<int>::iterator::iterator, bool> p;
p = s1.insert(60);
if (p.second):
Insert OK!
0, 10, 20, 30, 40, 50, 60,
s1.erase(70) =
0, 10, 20, 30, 40, 50, 60,
s1.erase(60) =
0, 10, 20, 30, 40, 50,
set<int>::iterator iter = s1.begin();
s1.erase(iter) =
10, 20, 30, 40, 50,
s1.count(10) = 1, s1.count(80) = 0
s1.find(10) : OK!
s1.find(80) : not found!
s1.empty()=0, s1.size()=5
s1.swap(s9) :
s1:
100,
s9:
10, 20, 30, 40, 50,
相关推荐
gdb 打印功能扩展 ...# std::priority_queue<T> -- via ppqueue command # std::bitset<n> -- via pbitset command # std::string -- via pstring command # std::widestring -- via pwstring command
priority_queue_learn.cpp queue_learn.cpp set_learn.cpp stack_learn.cpp static_var_in_class.cpp std_except.cpp std_io.cpp stl_alg_learn.cpp string_learn.cpp test_init.cpp type_change.cpp vector_learn....
c++ std stl各容器的应用场合及性能 map hash_map unordered_map multimap list forward_list vector set hash_set multiset unsorted_set queue deque priority_queue
第20章 priority_queue优先队列容器 275 20.1 priority_queue技术原理 275 20.2 priority_queue应用基础 278 20.3 本章小结 281 第四篇 C++ STL算法技术 第21章 非变易算法 284 21.1 逐个容器元素for_...
顺序容器:vector,list,deque 顺序容器适配器:stack,queue 关联容器:set,map,multiset,multimap 无序关联容器:unordered_set,unordered_map,unordered_multiset,unordered_multimap 容器均支持列表初始...
STLite-2021 CS1951任务,... A班要求完成sjtu::priority_queue , sjtu::deque和sjtu::map ,B班要求完成sjtu::vector , sjtu::deque和sjtu::map 。本作业中的四个容器在接口和复杂度要求上与STL基本一致,除了:与S
pqu.h = std::priority_queue que.h = std::queue set.h = std::set stk.h = std::stack str.h = std::string ust.h = std::unordered_set vec.h = std::vector 使用 使用内置或typedef类型T配置CTL容器。 # ...
3.7 sgi stl的私房菜:__type_traits 103 第4章 序列式容器(sequence containers) 113 4.1 容器概观与分类 113 4.1.1 序列式容器(sequence containers) 114 4.2 vector 115 4.2.1 vector 概述 115 4.2.2 ...
动机CTL旨在通过在ISO C11中实现以下STL容器来提高C11开发人员的生产率:deq.h = std :: deque lst.h = std :: list pqu.h = std :: priority_queue que.h = std :: queue set.h = std :: set stk.h = std :: stack ...
3.7 SGI STL的私房菜:__type_traits 103 第4章 序列式容器(sequence containers) 113 4.1 容器概观与分类 113 4.1.1 序列式容器(sequence containers) 114 4.2 vector 115 4.2.1 vector 概述 115 4.2.2 ...
priority_queue set unordered_set multiset unordered_multiset map multimap unordered_map unordered_multimap algorithm 其它 实现自定义排序规则 Python 攻略 基本数据类型 生成器 文件操作 并发 三方库 jieba ...
1、STL标准容器类简介 标准容器类 说明 顺序性容器 vector 相当与数组,从后面快速的插入与删除,直接访问任何元素 deque 双队列,从前面或后面快速的插入与删除,... priority_queue 最高优先级元素总是第一个出列
第20章 priority_queue优先队列容器 275 20.1 priority_queue技术原理 275 20.2 priority_queue应用基础 278 20.3 本章小结 281 第四篇 C++ STL算法技术 第21章 非变易算法 284 21.1 逐个容器元素for_...
九、deque (Double Ended Queue) 双端队列 22 成员函数: 22 实例程序: 23 十、string 字符串 24 成员函数: 24 实例程序: 28 十一、常用算法调用 29 1. for_each 29 2. min_element / max_element 29 3. copy / ...
该篇分为十一部分,分别是:vector类的主要成员...stack类的主要成员、queue类的主要成员、priority_queue类的组要成员、set类的主要成员、multiset类的主要成员、map类的主要成员、multimap类的主要成员、STL算法函数
第20章 priority_queue优先队列容器 275 20.1 priority_queue技术原理 275 20.2 priority_queue应用基础 278 20.3 本章小结 281 第四篇 C++ STL算法技术 第21章 非变易算法 284 21.1 逐个容器元素for_...
丰富的范例程序 Sample of STL STL 范例(一) 容器部分 Vector-------------------------------------------1 Deque---------------------------------...Priority_queue------------------------------------------139
本教程共分为5个部分,第一部分是C语言提高部分,第二部分为C++基础部分,第三部分为C++进阶部分,第四部分为C、C++及数据结构基础部分,第五部分为C_C++与设计模式基础,内容非常详细. 第一部分 C语言提高部分目录...
10.2.7优先级队列priority_queue 110 10.2.8Set和multiset容器 111 10.2.9Map和multimap容器 118 10.2.10容器共性机制研究 123 10.2.11其他 124 10.3算法 125 10.3.1算法基础 125 10.3.2STL算法中函数对象和谓词 138...
10.3 Priority Queue 128 10.3.1 核心接口 128 10.3.2 运用实例 128 10.4 Bitset 129 10.4.1 Bitset运用实例 129 11 Strings 131 11.1 动机 131 11.1.1 示例:引出一个临时文件名 131 11.1.2 例二:引出一段文字并...