1

这段代码是这里代码的一个小修改：给定一个字符串数组，返回所有的字谜字符串组
我花了最近1小时阅读了map，set等文章的参考，但仍然无法理解。

   #include <map>
    #include <iostream>
    #include <set>
    #include <algorithm>
    using namespace std;
 int main(){
    int n; cin >>n;
    string word;
    map<string, set<string> > anagrams;
    for (int i=0;i<n;i++){
        cin >> word;
        string sortedWord(word);
        sort(sortedWord.begin(), sortedWord.end());
        anagrams[sortedWord].insert(word);
    }
    for (auto& pair : anagrams){
        for (auto& word: pair.second){
            cout << word << " ";
        }
        //cout << "\n";
    }
}

据我了解，集合更像是一个有序向量。所以当我们来到这行代码时

anagrams[sortedWord].insert(word);

它使用我们的 sortedWord 作为键并将该对插入到字谜中。现在，当我继续插入对时，字谜会根据 sortedWord 自动排序。例如，如果我按这个顺序插入 cat, god , anagrams 将包含：

act act
act cat
dgo god

现在，当我使用基于范围的循环时，它会打印这对的第二项。我的理解正确吗？我有两个问题。当我们使用 sortedWord 作为键时，它为什么不替换之前的值呢？例如，act cat 应该替换 act act。这是因为地图或集合的实施吗？第二个问题，当我尝试为以下输入打印 pair.first 时，我得到一些随机输出：

Input:
5
cat act dog tac god
Output(for pair.second):
act cat tac dog god
Output(for pair.first):
a c t d g o

如果有人能给我进一步使用 set，我将不胜感激。

4

3 回答 3

3

对于std::map<std::string, std::set<std::string> >，当你这样做时：

anagrams[sortedWord].insert(word);

它将返回对std::set<std::string>存储在的引用，sortedWord或者它将（本质上）创建一个新的set并将其存储在该键处。由于您没有分配aset给它，所以set不会替换。但是在这种情况下，每次您具有相同的值时，它都会使用on 方法sortedWord添加到现有集合中。insertstd::set

就pair.first输出而言，它不是随机的。在地图中，您迭代键和值（键是first，值是second）。所以在这种情况下，pair.first是来自 的字符串sortedWords。所以第一次迭代是act，第二次迭代是dgo。由于您随后遍历了这些字符串对象，因此您将获得各个字符。

就结构而言，您的地图可以可视化为： 

(key) -> (value - set)  
act   -> act cat tac  
dgo   -> dog god
于 2013-10-08T12:42:46.557 回答
3

anagrams[sortedWord].insert(word);

它使用我们的 sortedWord 作为键并将该对插入到字谜中。

不完全正确。anagrams是每个键映射到的容器set。这意味着，您可以在 中拥有很多值anagrams[key]，但它们永远不会重复。

考虑 input: cat act dog god none cat，字谜将更像这样：

anagrams-+-act-+-act
         |     +-cat
         |
         +-dgo-+-dog
         |     +-god
         |
         +-enno-+-none

请注意，不会有cat, 两者的重复dog，并且god输入将存储在无意义的dgo键下。

当您遍历 pair 的第一个值时，您会得到键，但是由于 key is not set，但string您会得到单个字符而不是单词。

在我的示例中，您会得到类似于a c t d g o e n n o键中的字符的东西。

于 2013-10-08T12:45:54.660 回答
1

首先，为什么map<string, set<string> >不替换东西中的键？代码这样做：

string sortedWord(word);
sort(sortedWord.begin(), sortedWord.end());
anagrams[sortedWord].insert(word);

因此，对于任何单词，它首先被排序，例如

act -> act
cat -> act

并将排序后的版本用作键，以找到适当的值，即std::set字符串中的一个。未排序的版本word被插入到集合中。这不会取代之前的内容。
其次，如果您在字符串上使用基于范围的 for 循环，您将得到每个字母。

于 2013-10-08T12:45:38.457 回答