从EOJ上的DNA排序题开始，这个题目有两个测试点总是超时，万分感谢有学长?指出问题，原来的两层遍历时间复杂度有问题，所以顺势学习map;
感觉有两个难点，一是迭代器，二是按照value排序；
一、迭代器
迭代器一直感觉很高端的样子，从行为上看暂时可以理解为指针？如果不用迭代器连访问都很困难，而且高端一点的容器涉及到的STL函数比如find返回值都是迭代器
二、按照value排序
map会按照key排序，在CSDN上没找到其他方法能按照value排序的，所以折中一下，把map中的pair对放在vector里，然后自己写一个cmp，就可以用sort啦
AC代码记录一下
#include <bits/stdc++.h> using namespace std; int t,cnt; string tmp; typedef pair<string,int>dnapair; map<string,int>dna; vector<dnapair>v; map<string,int>::iterator iter; vector<dnapair>::iterator iter2; bool cmp(dnapair a,dnapair b) { if(a.second!=b.second)return a.second<b.second; return a.first<b.first; } int main() { cin>>t; while(t--) { cin>>tmp; iter=dna.find(tmp); if(iter!=dna.end())dna[tmp]++; else dna.insert(pair<string,int>(tmp,1)); } for(iter=dna.begin();iter!=dna.end();iter++) { v.push_back(dnapair(iter->first,iter->second)); } sort(v.begin(),v.end(),cmp); for(iter2=v.begin();iter2!=v.end();iter2++) cout<<iter2->first<<endl; return 0; }
写到这里突然想起之前的一个题
这个题是python上机测试的，我突然想起来和这个有点关联，用C++写一写（格式化输入就搞死我了，单就这个题目还是py好用）；
提高下难度，按照出现次数降序排序，出现次数相同按照数字本身升序排序；
#include <bits/stdc++.h> using namespace std; int t,tmp,sum; char c; map<int,int>cnt; typedef pair<int,int>intpair; vector <intpair>v; map<int,int>::iterator iter; vector<intpair>::iterator iter2; bool cmp(intpair a,intpair b) { if(a.second!=b.second)return a.second>b.second; return a.first<b.first; } int main() { cin>>tmp; cnt.insert(pair<int,int>(tmp,1)); c=getchar(); while(c==‘,‘) { cin>>tmp; if(cnt.find(tmp)!=cnt.end())cnt[tmp]++; else cnt.insert(pair<int,int>(tmp,1)); c=getchar(); } for(iter=cnt.begin();iter!=cnt.end();iter++) v.push_back(intpair(iter->first,iter->second)); sort(v.begin(),v.end(),cmp); for(iter2=v.begin();iter2!=v.end();iter2++) cout<<iter2->first<<‘ ‘<<iter2->second<<endl; return 0; }
暂时就这样，万望不吝赐教~
原文：https://www.cnblogs.com/MissCold/p/11415660.html