Multimap无法排序

Question

我有一个多重映射，用于将一个字符串的汉明距离映射到相应的字符串上。

由于两个字符串的汉明距离可能相同，我希望它们按升序排序。但是当我打印它时，它并没有排序。 hamdistArray 声明为无符号类型。

typedef multimap<unsigned, string, less<unsigned> > Check;
            Check pairs; 

            pairs.insert(Check::value_type(hamdistArray[j], d.sortedWordDatabase[j]));

            for(Check::const_iterator iter = pairs.begin(); iter != pairs.end(); ++iter)
            {
                cout << iter->first << '\t' << iter->second<< endl;
            }

- Xann

---

“Check”是这种类型的一个愚蠢的名称。 - Lightness Races in Orbit

我不明白你发布的代码如何是一个测试用例，因为你只插入了一个值。 - Lightness Races in Orbit

@Tomalak Geret'kal 这段代码位于一个for循环内，因此使用了变量‘j’。选择Check是因为它可以根据字符串与数据库之间的汉明距离来进行纠正。 - Xann

请在您的测试用例中包含循环。“Check”是一个愚蠢的名称：该类型不纠正任何内容；它是一种类型，而不是过程。它是一种数据存储类型的名称，而不是改变数据的算法的名称。 - Lightness Races in Orbit

@Tomalak Geret'kal：感谢您的见解。也许我为这种类型选择的名称对您来说并没有意义。但我希望这不会妨碍您回答我的问题的能力。 :) - Xann

Answer 1

multimap中的元素按键（在本例中为无符号汉明距离）排序。具有相同键的元素不按值（在本例中为字符串）排序，通常按照它们插入的顺序保留。

- kbjorklu

---

谢谢您指出这一点。我应该如何将汉明距离与其对应的字符串一起排序呢？我应该手动完成吗？ - Xann

使用无符号整数和字符串的pair的set或multiset。 - kbjorklu

multimap文档似乎支持这个答案：http://www.cplusplus.com/reference/stl/multimap/insert/ - Ogre Psalm33

Answer 2

less模板函数不是必需的，因为它是默认值。尝试声明不带 as 的Check：

typedef multimap<unsigned, string> Check;

编辑：做到这一点的最佳方式是生成哈希键作为*key_type*，然后value-type可以是std :: pair<unsigned, string>

- Felipe Tonello

---

这会改变什么吗？ - pmr

尝试过了，但是没有改变任何东西。 - Xann

Answer 3

使用std::multimap是不可能实现的，因为在比较键时，无法确定它们代表哪个值。

- Oswald

Answer 4

multimap 只按其键（长度）排序，而不按值（字符串）排序。在这种情况下，我认为您最好的方法是使用 std::map<unsigned, std::set<std::string> >。您也可以使用 std::set<std::pair<unsigned, std::string> >，但搜索需要构造虚拟的 pair 进行搜索。

- Mark B