首页 > 代码库 > 初涉算法——STL初步
初涉算法——STL初步
一、头文件<algorithm>
①sort函数
- sort使用数组元素默认的大小比较运算符进行排序，只有在需要按照特殊依据进行排序时才需要传入额外的比较函数；
- sort可以给任意对象排序（不一定是内置类型，由此可见sort是模板函数），前提是类型需要定义“小于”运算符，或者在排序时传入一个“小于”函数；
- 排序对象若存在普通数组中，则用sort(a, a+n)的方式调用；
- 排序对象若存在vector中，则用sort(v.begin(), v.end())。
1 #include<algorithm> 2 const int maxn = 10000; 3 int main() 4 { 5 int n, a[maxn]; 6 for(int i=0;i<n;i++){ 7 scanf("%d",&a[i]); 8 } 9 sort(a,a+n); 10 }
②lower_bound函数
- 查找大于或者等于x的第一个位置
- 可以在用sort函数排好序后再使用lower_bound
1 #include<algorithm> 2 const int maxn = 10000; 3 int main() 4 { 5 int n, a[maxn]; 6 for(int i=0;i<n;i++) 7 scanf("%d",&a[i]); 8 sort(a,a+n); 9 scanf("%d",&x); 10 int p = lower_bound(a, a+n, x) - a; //在已排序数组a中寻找x 11 if(a[p]==x) 12 printf("%d found at %d\n", x, p+1); 13 }
二、头文件<vector>
①特点：它把一些常用操作“封装”在了vector类型内部（例如：函数size()可以读取其大小）。
②区别于数组：无需另外用一个变量（maxn）指定元素个数。
③优点：可以直接赋值，还可以作为函数的参数或者返回值。
vector是一个模板类：
1 int main() 2 { 3 vector<int> a; //声明一个不定长int型数组a 4 a.push_back(1); //在尾部添加元素1 5 a.pop_back(); //在尾部删除元素 6 cout<<a.size(); //输出a的大小 7 a.resize(4); //修改a的大小为4 8 a.clear(); //清空a，此时a的大小为0 9 bool isEmpty = a.empty(); //a为空，则isEmpty被赋值为true 10 }
三、头文件<set>
定义：set是数学上的集合——每个元素最多只能出现一次。
特点：和sort一样，自定义类型也可以构造set，但必须定义“小于”运算符。
性质：set中元素已从小到大排好序。
题目：输入一个文本，找出所有不同的单词（连续的字母序列），按字典序从小到大输出，单词不区分大小写。
1 #include<iostream> 2 #include<string> 3 #include<set> 4 #include<sstream> 5 using namespace std; 6 7 set<string> dict; //声明string集合 8 string s, buf; 9 10 int main() 11 { 12 while(cin >> s) { //注意：string已经定义了"小于"运算符，可直接使用set保存单词集合 13 for(int i = 0; i < s.length(); i++) //利用了set的性质，一个for循环即可从小到大遍历所有元素 14 if(isalpha(s[i])) //判定s[i]是否为字母 15 s[i] = tolower(s[i]); //全都转为小写 16 else 17 s[i] = ‘ ‘; 18 stringstream ss(s); 19 while(ss >> buf) 20 dict.insert(buf); 21 } 22 for(set<string>::iterator it = dict.begin(); it != dict.end(); ++it)//利用了set的性质，一个for循环即可从小到大遍历所有元素 23 cout << *it << "\n"; //迭代器it的用法之一 24 return 0; 25 }
四、头文件<map>
定义：map就是从键（key）到值（value）的映射。
特点：重载了[]运算符，map像是数组的“高级版”。
举例：用map<string,int> month_name来表示“月份名字到月份编号”的映射，然后用month_name["July"]=7这样的方式来赋值。
题目：输入一些单词，找出所有满足如下条件的单词：该单词不能通过字母重排而得到输入文本中的另外一个单词。字母不区分大小写。
1 #include<iostream> 2 #include<string> 3 #include<cctype> 4 #include<vector> 5 #include<map> 6 #include<algorithm> 7 using namespace std; 8 9 map<string,int> cnt; 10 vector<string> words; 11 12 13 string repr(string s) //将单词s进行标准化 14 { 15 string ans = s; 16 for(int i = 0; i < ans.length(); i++) 17 ans[i] = tolower(ans[i]); 18 sort(ans.begin(), ans.end()); 19 return ans; 20 } 21 22 int main() { 23 int n = 0; 24 string s; 25 while(cin >> s) { 26 if(s[0] == ‘#‘) break; 27 words.push_back(s); 28 string r = repr(s); 29 if(!cnt.count(r)) //set和map都支持insert、find、count和remove操作，并且可以按照从小到大的顺序循环遍历其中的元素 30 cnt[r] = 0; 31 cnt[r]++; 32 } 33 vector<string> ans; 34 for(int i = 0; i < words.size(); i++) 35 if(cnt[repr(words[i])] == 1) 36 ans.push_back(words[i]); 37 sort(ans.begin(), ans.end()); 38 for(int i = 0; i < ans.size(); i++) 39 cout << ans[i] << "\n"; 40 return 0; 41 }
小结：set和map都支持insert、find、count和remove操作，并且可以按照从小到大的顺序循环遍历其中的元素。此外，map还提供了“[]”运算符，使得map可以像数组一样使用。
五、头文件<stack>
- 定义：stack<int> s
- 入栈：push()
- 出栈：pop()
- 取栈顶元素：top()
题目：Uva12096
1 #include<iostream> 2 #include<string> 3 #include<set> 4 #include<map> 5 #include<stack> 6 #include<vector> 7 #include<algorithm> 8 using namespace std; 9 10 #define ALL(x) x.begin(),x.end() 11 #define INS(x) inserter(x,x.begin()) 12 13 typedef set<int> Set; 14 map<Set,int> IDcache; //把集合映射成ID 15 vector<Set> Setcache; //根据ID取集合 16 17 //查找给定集合x的ID。如果找不到，分配一个新ID 18 int ID (Set x) { 19 if (IDcache.count(x)) return IDcache[x]; 20 Setcache.push_back(x); //添加新集合 21 return IDcache[x] = Setcache.size() - 1; 22 } 23 24 int main () { 25 int T; 26 cin >> T; 27 while(T--) { 28 stack<int> s; //题目中的栈 29 int n; 30 cin >> n; 31 for(int i = 0; i < n; i++) { 32 string op; 33 cin >> op; 34 if (op[0] == ‘P‘) s.push(ID(Set())); 35 else if (op[0] == ‘D‘) s.push(s.top()); 36 else { 37 Set x1 = Setcache[s.top()]; s.pop(); 38 Set x2 = Setcache[s.top()]; s.pop(); 39 Set x; 40 if (op[0] == ‘U‘) set_union (ALL(x1), ALL(x2), INS(x)); 41 if (op[0] == ‘I‘) set_intersection (ALL(x1), ALL(x2), INS(x)); 42 if (op[0] == ‘A‘) { x = x2; x.insert(ID(x1)); } 43 s.push(ID(x)); 44 } 45 cout << Setcache[s.top()].size() << endl; 46 } 47 cout << "***" << endl; 48 } 49 return 0; 50 }
六、头文件<queue>
- 定义：queue<int> s
- 入队：push()
- 出队：pop()
- 取队首元素：front()
【优先队列】
区别于队列：先出队列的元素是队列中优先级最高的元素。
声明：priority_queue<int> pq //pq是一个“越小的整数优先级越低的优先队列”
取队首元素：top()
注：自定义类型也可以组成优先队列，但必须为每个元素定义一个优先级。
初涉算法——STL初步
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。