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 namespace std;
8 typedef long long ll;
9 const int maxn=5e4+10;
10 const int N=1e4+10;
11 int main()
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 namespace std;
37 const int maxn=1005;
38 const int N=1e4+10;
39 int main()
40 {
41 int n;
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 int temp;
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\n");
62 else
63 {
64 it = lower_bound(v.begin(),v.end(),v1[v1.size()-1]);
65 v.erase(it);
66 printf("%d\n",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\n");
75 continue;
76 }
77 if(v.size() % 2 == 0)
78 printf("%d\n",v[v.size()/2-1]);
79 else
80 printf("%d\n",v[v.size()/2]);
81 }
82 }
83 return 0;
84 }