C++的集合和映射

1.集合set 概念

set就是数学上的集合——每个元素最多只出现一次，和sort一样，自定义类型也可以构造set，但同样必须定义“小于”运算符。

例题（安迪的第一个字典）

问题描述

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

样例输入

Adventures in Disneyland

Two blondes were going to Disneyland when they came  to a fork in the road.The sign read: "Disneyland Left."

So they went home.

样例输出（为了节约篇幅只保留前五行）

a

adventures

blondes

came 

disneyland

 示例代码

#include<iostream> #include<sstream> #include<set> #include<string> using namespace std; set<string> dict;//string集合 int main() { string s, buf; while (cin >> s) { for (int i = 0; i < s.length(); i++) { if (isalpha(s[i])) {//如果是字母 s[i] = tolower(s[i]);//大写转为小写，小写不变 } else { s[i] = ' '; } } stringstream ss(s);//字符串流的输入输出 while (ss >> buf) {//一个字符串一个字符串的来 dict.insert(buf);//插入dict中并从小到大排序 } } for (set<string>::iterator it = dict.begin(); it != dict.end(); ++it) {//遍历输出 cout << *it << "\n"; } return 0; }

分析

iterator的意思是迭代器，是STL中的重要概念，类似于指针。和“vector类似于数组一样”，这里的“类似”指的是用法类似。 

2.映射map 概念

 map就是i从键（key）到值（value）的映射。因为重载了[]运算符，map像是数组的“高级版”。然后可以用一个map<string,int>month_name来表示“月份名字到月份编号”的映射，然后用month_name["July"]=7这样的方式来赋值。

例题（反片语）

问题描述

输入一些单词，找出所有满足如下条件的单词：该单词不能通过字母重排，得到输入文本中的另外一个单词。在判断是否满足条件时，字母不分大小写，但在输出时应保留输入中的大小写，按字典序进行排列（所有大写字母在所有小写字母的前面）。

样例输入

ladder came tape soon leader acme RIDE lone Dreis peat

ScALE orb eye Rides dealer NotE derail LaCes drIed 

noel dire Disk mace Rob dries

#

样例输出

Disk

NotE

derail

drIed

eye

ladder

soon

示例代码

#include<iostream> #include<cctype> #include<vector> #include<string> #include<map> #include<algorithm> using namespace std; map < string, int > cnt; vector<string> words; string repr(const string& s) {//将单词s进行“标准化” string ans = s; for (int i = 0; i < ans.length(); i++) {//将字母全部变为小写 ans[i] = tolower(ans[i]); } sort(ans.begin(), ans.end());//将字母进行大小写排序 return ans; } int main() { int n = 0; string s; while (cin >> s) { if (s[0] == '#') { break; } words.push_back(s); string r = repr(s); if (!cnt.count(r)) {//如果该种字母排序没出现过，该种排序出现的次数置为0 cnt[r] = 0; } cnt[r]++;//无论是否出现过，次数都要加1 } vector<string> ans; for (int i = 0; i < words.size(); i++) { if (cnt[repr(words[i])] == 1) {//如果该单词的排序只出现过一次 ans.push_back(words[i]); } } sort(ans.begin(), ans.end());//从小到大排序 for (int i = 0; i < ans.size(); i++) { cout << ans[i] << "\n"; } return 0; }