std::map - 如何更改键的排序？

Question

我在使用std::map时遇到了问题。我想将一些成对的列表映射到特定的索引下：

map<string, list<pair<string, int> > > List;

这是在Dijkstra算法中使用的。 主要问题在于map会按字母顺序排序string键，就像这样：

AAA, AA0, AA1, AAB, AC1 = AA0->AA1->AAA->AAB->AC1

但我想以不同的方式进行排序：

AAA, AA0, AA1, AAB, AC1 = AAA->AAB->AA0->AA1->AC1

有没有解决方案？我读过制作自己的比较类的方法，但我不知道如何做。或者也许有其他方法可以解决？

- bartekmp

Answer 1

在实例化映射时，必须提供自己的比较函数作为第三个模板参数进行传递。例如：

struct Comp
{
  bool operator()(const std::string& lhs, const std::string& rhs) const
  {
    // implement your comparison logic here
  }
};

这个类的实例是可调用的（因此称为“函数对象”），带有两个字符串参数，并且应该基于严格弱排序逻辑返回true或false。

然后，使用函数对象类型实例化map：

std::map<string, list<pair<string, int>>, Comp> List;

现在，地图将在内部使用您的比较逻辑来定义其元素的排序。

- juanchopanza

---

好的，我明白了，但是我该如何比较字符串的差异呢？我的意思是，我该如何在字符串中找到一个数字？ - bartekmp

@user2342783 这是一个完全不同的问题。您应该在一个新的问题中提出它。 - stefan

@user2342783 这是一个不同的问题。但是你可以迭代字符串的元素（每个元素都是一个 char），并执行一些操作，例如调用 std::isdigit。 - juanchopanza

Answer 2

正如其他人所说，您需要实现一个自定义的比较器...

struct custom_comparer
{
    bool operator()(const std::string& left, const std::string& right) const
    {
        return std::lexicographical_compare(
            left.cbegin(), left.cend(), 
            right.cbegin(), right.cend(),
            [](char l, char r) -> bool
            {
                 bool ldigit = isdigit(l) != 0,
                      rdigit = isdigit(r) != 0;

                 return (!ldigit && rdigit) || (ldigit == rdigit && l < r);
            });
    }
};

使用它...

std::map<string, list<pair<string, int>>, custom_comparer> List;

普通的string比较操作符使用lexicographical_compare进行比较。我上面的custom_comparer也使用它，但是插入了自定义的比较器。该自定义比较器使用isdigit来执行您想要的比较。

- David

Answer 3

您需要编写自己的比较器：

struct custom_string_comparer
{
    bool operator()(const std::string& s1, const std::string& s2)
    {
         return ...; // your comparison here
    }
};

map<string, list<pair<string, int>>, custom_string_comparer> List;

- Marius Bancila

Answer 4

是的。你需要提供第三个模板参数，请参见文档。

- Andrew Lazarus

---

虽然你的陈述是正确的，但仅凭它本身并没有太大帮助。请至少像其他人一样写下一个最简示例。此外，cplusplus.com并不是“文档”。 - stefan