为了节省空间，有时我们会使用动态数组vector。
定义vector动态数组：vector<类型名>变量名
1. vector<int>que //定义que为一个int类型的动态数组 2. vector<char> a //定义 a 为一个char 类型的动态数组 3. vector<data> c //其中data为自定义的数据类型，可以为结构体
vector常用函数
a[i] 返回动态数组中的第i个元素
a.empty() 若动态数组为空，则返回true,否则返回false
a.size() 返回动态数组中元素的个数
a.resize() 修改动态数组大小
a.push_back() 向动态数组尾部插入一个元素
a.pop_back() 删除动态数组尾部的一个元素
a.begin() 返回指向vector头部的迭代器（指针）
a.end() 返回指向vector尾部元素的后一个元素的迭代器（指针）
利用vector动态数组实现的排序代码：
1. #include<stdio.h> 2. #include<vector> 3. #include<queue> 4. #include<algorithm> 5. #include<iostream> 6. using namespace std; 7. int main() 8. { 9. vector<int>a; 10. int n; 11. scanf("%d",&n); 12. for(int i=1;i<=n;i++){ 13. int tmp; 14. scanf("%d",&tmp); 15. a.push_back(tmp); 16. } 17. sort(a.begin(),a.end()); 18. for(int i=0;i<a.size();i++) printf("%d ",a[i]); 19. printf("\n"); 20. return 0; 21. }
在实际应用中，我们可以使用map容器来作为一个有序的映射表，可以将其看做是一个下标可以是任何类型的数组。对map单次操作的时间复杂度为O(lgn)。
定义map： map<类型1,类型2>变量名;
map<string,int> ma; //定义ma为一个从string到int的一个映射
访问map中的元素
1. map<string,int> ma; //定义ma 2. ma[“abc”]=2; //将字符串”abc”映射到整数”2”上 3. cout<<ma[“abc”]<<endl; //屏幕上将输出整数2 4. //同时，map中的类型可以是自己定义的结构体，此时结构体中应该有重载小于符号。
map的常用函数
operator[] 访问map中的元素,该元素不存在,将创建一个新元素并将该元素映射到类型2的初始值上(对于int类型,初始值为0)
ma.begin() 返回map中第一个元素的迭代器（指针）
ma.end() 返回map中最后一个元素的后一个元素的迭代器（指针）
ma.size() 返回map中元素个数
ma.count(element) 若元素element存在于map中返回1，否则返回0
ma.clear() 初始化map
ma.lower_bound() 返回键值大于等于给定元素的第一个位置
注意：一旦map中的一个元素被访问，不论它之前是否已经被赋值，它都将被视为已经存在，例如：
1. if(ma[“abc”]) /*do something*/ ; 2. if(ma.count(“abc”))cout<<”yes”<<endl; 3. else cout<<”no”<<endl;//本段程序运行后屏幕上将输出”yes
1. #include<stdio.h> 2. #include<map> 3. #include<iostream> 4. using namespace std; 5. map<string,int>ma; 6. int main() 7. { 8. ma["apple"]=1; 9. ma["banana"]=2; 10. ma["lemon"]=3; 11. cout<<ma.size()<<endl;//输出map的大小3 12. cout<<ma["apple"]<<endl;//输出1 13. if(ma.count("pear"))cout<<"pear"<<endl; 14. else cout<<"no pear"<<endl;//输出"no pear" 15. cout<<ma.lower_bound("cow")->first<<endl;//输出"lemon" 16. cout<<ma.lower_bound("cow")->second<<endl;//输出ma["lemon"],即输出3 17. return 0; 18. }
