4

我有一个问题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

有什么解决办法吗？我读到了关于制作自己的比较类的文章，但我不知道该怎么做。或者也许有其他方法可以解决它？

4

4 回答 4

9

您必须提供自己的比较函子，在实例化地图时必须将其作为第三个模板参数传递。例如：

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

这个类的实例是可调用的（因此是“函子”），带有两个字符串参数，并且应该根据严格的弱排序逻辑返回真或假。

然后使用仿函数类型实例化地图：

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

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

于 2013-05-14T14:07:24.570 回答
3

就像其他人说的那样，您需要实现一个自定义比较器......

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进行您想要的比较。

于 2013-05-14T14:40:02.427 回答
2

您必须编写自己的比较器：

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;
于 2013-05-14T14:08:38.620 回答
-3

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

于 2013-05-14T14:07:33.053 回答