初涉算法——STL初步

一、头文件<algorithm>

①sort函数

sort使用数组元素默认的大小比较运算符进行排序，只有在需要按照特殊依据进行排序时才需要传入额外的比较函数；
sort可以给任意对象排序（不一定是内置类型，由此可见sort是模板函数），前提是类型需要定义“小于”运算符，或者在排序时传入一个“小于”函数；
排序对象若存在普通数组中，则用sort(a, a+n)的方式调用；
排序对象若存在vector中，则用sort(v.begin(), v.end())。

 #include<algorithm>

 const int maxn = ;

 int main()

 {

     int n, a[maxn];

     for(int i=;i<n;i++){

         scanf("%d",&a[i]);

     }

     sort(a,a+n);

 }

②lower_bound函数

查找大于或者等于x的第一个位置
可以在用sort函数排好序后再使用lower_bound

 #include<algorithm>

 const int maxn = ;

 int main()

 {

     int n, a[maxn];

     for(int i=;i<n;i++)

         scanf("%d",&a[i]);

     sort(a,a+n);

     scanf("%d",&x);

     int p = lower_bound(a, a+n, x) - a;  //在已排序数组a中寻找x

     if(a[p]==x)

         printf("%d found at %d\n", x, p+);

 }

二、头文件<vector>

①特点：它把一些常用操作“封装”在了vector类型内部（例如：函数size()可以读取其大小）。

②区别于数组：无需另外用一个变量（maxn）指定元素个数。

③优点：可以直接赋值，还可以作为函数的参数或者返回值。

vector是一个模板类：

 int main()

 {

     vector<int> a;                //声明一个不定长int型数组a

     a.push_back();               //在尾部添加元素1

     a.pop_back();                 //在尾部删除元素

     cout<<a.size();               //输出a的大小

     a.resize();                  //修改a的大小为4

     a.clear();                    //清空a，此时a的大小为0

     bool isEmpty = a.empty();     //a为空，则isEmpty被赋值为true

 }

三、头文件<set>

定义：set是数学上的集合——每个元素最多只能出现一次。

特点：和sort一样，自定义类型也可以构造set，但必须定义“小于”运算符。

性质：set中元素已从小到大排好序。

题目：输入一个文本，找出所有不同的单词（连续的字母序列），按字典序从小到大输出，单词不区分大小写。

 #include<iostream>

 #include<string>

 #include<set>

 #include<sstream>

 using namespace std;

 set<string> dict;                　　　　　　//声明string集合

 string s, buf;

 int main()

 {

   while(cin >> s) {                        //注意：string已经定义了"小于"运算符，可直接使用set保存单词集合

     for(int i = ; i < s.length(); i++)    //利用了set的性质，一个for循环即可从小到大遍历所有元素

       if(isalpha(s[i]))                 　　//判定s[i]是否为字母

           s[i] = tolower(s[i]);             //全都转为小写

       else

           s[i] = ' ';

     stringstream ss(s);

     while(ss >> buf)

         dict.insert(buf);

   }

   for(set<string>::iterator it = dict.begin(); it != dict.end(); ++it)//利用了set的性质，一个for循环即可从小到大遍历所有元素

     cout << *it << "\n";            //迭代器it的用法之一

   return ;

 }

四、头文件<map>

定义：map就是从键（key）到值（value）的映射。

特点：重载了[]运算符，map像是数组的“高级版”。

举例：用map<string,int> month_name来表示“月份名字到月份编号”的映射，然后用month_name["July"]=7这样的方式来赋值。

题目：输入一些单词，找出所有满足如下条件的单词：该单词不能通过字母重排而得到输入文本中的另外一个单词。字母不区分大小写。

 #include<iostream>

 #include<string>

 #include<cctype>

 #include<vector>

 #include<map>

 #include<algorithm>

 using namespace std;

 map<string,int> cnt;

 vector<string> words;

 string repr(string s)                //将单词s进行标准化

 {

   string ans = s;

   for(int i = ; i < ans.length(); i++)

     ans[i] = tolower(ans[i]);

   sort(ans.begin(), ans.end());

   return ans;

 }

 int main() {

   int n = ;

   string s;

   while(cin >> s) {

     if(s[] == '#') break;

     words.push_back(s);

     string r = repr(s);

     if(!cnt.count(r))     //set和map都支持insert、find、count和remove操作，并且可以按照从小到大的顺序循环遍历其中的元素

         cnt[r] = ;

     cnt[r]++;

   }

   vector<string> ans;

   for(int i = ; i < words.size(); i++)

     if(cnt[repr(words[i])] == )

         ans.push_back(words[i]);

   sort(ans.begin(), ans.end());

   for(int i = ; i < ans.size(); i++)

     cout << ans[i] << "\n";

   return ;

 }

小结：set和map都支持insert、find、count和remove操作，并且可以按照从小到大的顺序循环遍历其中的元素。此外，map还提供了“[]”运算符，使得map可以像数组一样使用。

五、头文件<stack>

定义：stack<int> s
入栈：push()
出栈：pop()
取栈顶元素：top()

题目：Uva12096

 #include<iostream>

 #include<string>

 #include<set>

 #include<map>

 #include<stack>

 #include<vector>

 #include<algorithm>

 using namespace std;

 #define ALL(x) x.begin(),x.end()

 #define INS(x) inserter(x,x.begin())

 typedef set<int> Set;

 map<Set,int> IDcache; //把集合映射成ID

 vector<Set> Setcache; //根据ID取集合 

 //查找给定集合x的ID。如果找不到，分配一个新ID

 int ID (Set x) {

   if (IDcache.count(x)) return IDcache[x];

   Setcache.push_back(x);     //添加新集合

   return IDcache[x] = Setcache.size() - ;

 }

 int main () {

   int T;

   cin >> T;

   while(T--) {

     stack<int> s; //题目中的栈

     int n;

     cin >> n;

     for(int i = ; i < n; i++) {

       string op;

       cin >> op;

       if (op[] == 'P') s.push(ID(Set()));

       else if (op[] == 'D') s.push(s.top());

       else {

         Set x1 = Setcache[s.top()]; s.pop();

         Set x2 = Setcache[s.top()]; s.pop();

         Set x;

         if (op[] == 'U') set_union (ALL(x1), ALL(x2), INS(x));

         if (op[] == 'I') set_intersection (ALL(x1), ALL(x2), INS(x));

         if (op[] == 'A') { x = x2; x.insert(ID(x1)); }

         s.push(ID(x));

       }

       cout << Setcache[s.top()].size() << endl;

     }

     cout << "***" << endl;

   }

   return ;

 }

六、头文件<queue>

定义：queue<int> s
入队：push()
出队：pop()
取队首元素：front()

【优先队列】

区别于队列：先出队列的元素是队列中优先级最高的元素。

声明：priority_queue<int> pq //pq是一个“越小的整数优先级越低的优先队列”

取队首元素：top()

注：自定义类型也可以组成优先队列，但必须为每个元素定义一个优先级。

巴特西

初涉算法——STL初步

最新文章

热门文章