摘要：
vector容器的简单应用，我们可以用vector维护一个有序数组，每次对要插入的数用upper_bound或者lower_bound来为这个数找一个应该插入到vector的位置。=r.end();it++)19cout˂˂(*it)˂˂endl;20}21/*22结果：2312422532627*/ViewCode更多vector操作见：https://blog.csdn.net/qq_31858735/article/details/82623110本题代码：1/*2vector容器的简单应用，我们可以用vector维护一个有序数组，每次对要插入的数用upper_bound或者lower_bound来3为这个数找一个应该插入到vector的位置。1718upper_bound:从数组的begin位置到end-1位置二分查找第一个小于num的数字，19找到返回该数字的地址，不存在则返回end。
vector容器的简单应用，我们可以用vector维护一个有序数组，每次对要插入的数用upper_bound或者lower_bound来
为这个数找一个应该插入到vector的位置。另外再找一个数组来维护插入数的顺序，来面对pop操作
在从小到大的排序数组中，
lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，
找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，
找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
在从大到小的排序数组中，重载lower_bound()和upper_bound()
lower_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字，
找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
upper_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字，
找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
void push_back(const T& x):向量尾部增加一个元素X
iterator insert(iterator it,const T& x):向量中迭代器指向元素前增加一个元素x
iterator insert(iterator it,int n,const T& x):向量中迭代器指向元素前增加n个相同的元素x
iterator insert(iterator it,const_iterator first,const_iterator last):向量中迭代器指向元素前插入另一个相同类型向量的[first,last)间的数据
构造函数
vector():创建一个空vector
vector(int nSize):创建一个vector,元素个数为nSize
vector(int nSize,const t& t):创建一个vector，元素个数为nSize,且值均为t
1 //int型vector,包含3个元素且每个元素都是9 2 vector<int> vecIntB(3,9);
vector(const vector&):复制构造函数
vector(begin,end):复制[begin,end)区间内另一个数组的元素到vector中
vector容器的查找
find(r.begin(),r.end(),要查找的值)，注意这个find相当于一个“类函数”，即不需要vector.find()
返回值可赋值给迭代器（比如it），it-=r.begin()会得到一个下标，这个下标就是要查找的值在vector中的位置（从0开始）
如果没有找到会返回r.end()（r.end()位置的值是一个随机数）。所以可以与r.end()比较来判断这个值存不存在
vector元素的删除
iterator erase(iterator it):删除向量中迭代器指向元素
遍历vector
1 #include<iostream> 2 #include<queue> 3 #include<vector> 4 #include<string.h> 5 #include<stdio.h> 6 #include<algorithm> 7 using namespacestd; 8 typedef long longll; 9 const int maxn=5e4+10; 10 const int N=1e4+10; 11 intmain() 12 { 13 vector<int>r; 14 vector<int>::iterator it; 15 r.push_back(1); 16 r.push_back(2); 17 r.push_back(3); 18 for(it=r.begin();it!=r.end();it++) 19 cout<<(*it)<<endl; 20 } 21 /* 22 结果： 23 1 24 2 25 3 26 27 */
更多vector操作见：https://blog.csdn.net/qq_31858735/article/details/82623110
本题代码：
1 /* 2 vector容器的简单应用，我们可以用vector维护一个有序数组，每次对要插入的数用upper_bound或者lower_bound来 3 为这个数找一个应该插入到vector的位置。另外再找一个数组来维护插入数的顺序，来面对pop操作 4 5 6 在从小到大的排序数组中， 7 lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字， 8 找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。 9 10 upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字， 11 找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。 12 13 14 在从大到小的排序数组中，重载lower_bound()和upper_bound() 15 lower_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字， 16 找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。 17 18 upper_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字， 19 找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。 20 21 22 23 void push_back(const T& x):向量尾部增加一个元素X 24 iterator insert(iterator it,const T& x):向量中迭代器指向元素前增加一个元素x 25 iterator insert(iterator it,int n,const T& x):向量中迭代器指向元素前增加n个相同的元素x 26 iterator insert(iterator it,const_iterator first,const_iterator last):向量中迭代器指向元素前插入另一个相同类型向量的[first,last)间的数据 27 更多vector操作见：https://blog.csdn.net/qq_31858735/article/details/82623110 28 */ 29 #include<stdio.h> 30 #include<string.h> 31 #include<iostream> 32 #include<algorithm> 33 #include<map> 34 #include<queue> 35 #include<vector> 36 using namespacestd; 37 const int maxn=1005; 38 const int N=1e4+10; 39 intmain() 40 { 41 intn; 42 vector<int>v1,v; 43 scanf("%d",&n); 44 vector<int>::iterator it; 45 while(n--) 46 { 47 char ch[15]; 48 scanf("%s",ch); 49 string s =ch; 50 if(s == "Push") 51 { 52 inttemp; 53 scanf("%d",&temp); 54 v1.push_back(temp); 55 it = lower_bound(v.begin(),v.end(),temp); //获取大于等于temp这个值位置 56 v.insert(it,temp); //vector插入到it的前面 57 } 58 else if(s == "Pop") 59 { 60 if(v1.size() == 0) 61 printf("Invalid "); 62 else 63 { 64 it = lower_bound(v.begin(),v.end(),v1[v1.size()-1]); 65 v.erase(it); 66 printf("%d ",v1[v1.size()-1]); 67 v1.pop_back(); 68 } 69 } 70 else if(s == "PeekMedian") 71 { 72 if(v1.size() == 0) 73 { 74 printf("Invalid "); 75 continue; 76 } 77 if(v.size() % 2 == 0) 78 printf("%d ",v[v.size()/2-1]); 79 else 80 printf("%d ",v[v.size()/2]); 81 } 82 } 83 return 0; 84 }