-1

我试图使用自定义比较器按值排序地图，但我无法弄清楚为什么我一直收到“没有匹配的 compareByVal 调用”的错误

这是我在 main.cpp 中的内容：

#include <map>
#include <iostream>

struct compareByVal {
  bool operator[](const std::pair<int,int> & a, const std::pair<int,int> & b)
    return a.second < b.second;
}

int main() {
  std::map<int,int,compareByVal> hash;
  hash[1] = 5;
  hash[2] = 2;
  hash[3] = 10;

  std::cout << hash.begin()->first << std::endl;
}
4

5 回答 5

1

第一个简单的问题是

struct compareByVal {
  bool operator[](const std::pair<int,int> & a, const std::pair<int,int> & b)
    return a.second < b.second;
}

应该

struct compareByVal {
  bool operator()(const std::pair<int,int> & a, const std::pair<int,int> & b) const {
    return a.second < b.second;
  }
};

第二，严重的问题是比较的签名是错误的。它应该是

struct compareByVal {
  bool operator()(const int leftKey, const int rightKey) const;
}

您无法访问比较函数中的值。没有（简单的）方法可以按值对地图进行排序。

于 2020-02-06T15:22:54.643 回答
1

简单地说，你不能。不确定您使用的是哪个编译器，但 clang 和 gcc 都提供了有用的消息。有上下文。

铛： static_assert(__is_invocable<_Compare&, const _Key&, const _Key&>{},

海湾合作委员会： if (__i == end() || key_comp()(__k, (*__i).first))

您可以看到 clang 和 gcc 都在调用 compare 方法时只使用了key而不是 value。这就是地图的工作原理。

如果要按值排序，则必须创建自己的自定义映射，或者更实际地，使用值作为键。创建自己的地图来实现这一点比您想象的要困难，因为它必须在修改任何值后进行排序。

于 2020-02-06T15:25:24.897 回答
1

如果您想std::map按其值对 a 进行排序，那么您使用了错误的容器。std::map按定义按键排序。

您可以包装键和值：

struct foo {
    int key;
    int value;
};

然后使用 a std::set<foo>，它使用仅比较 的比较器foo::value。

于 2020-02-06T16:08:31.673 回答
0

这可能是 XY 问题。

如果您需要同时按键和值排序，那么单个std::map可能不是最有效的选择。

在数据库理论中，所有数据都将放在一个表中。将创建一个索引表来描述访问或排序方法。需要以一种以上方法排序的数据将具有多个索引表。

在 C++ 中，核心表是std::vector. 索引将是std::map<key1, vector_index>, std::map<key2, vector_index>，其中vector_index是核心表中项目的索引。

例子： 

struct Record
{
  int age;
  std::string name;
};

// Core table
std::vector<Record> database;

// Index by age
std::map<int, unsigned int> age_index_table;

// Index by name
std::map<std::string, unsigned int> name_index_table;

// Fetching by age:
unsigned int database_index = age_index_table[42];
Record r = database[database_index];

// Fetching by name:
unsigned int database_index = name_index_table["Harry Potter"];
Record r = database[database_index];

您可以通过在 Internet 上搜索“数据库索引表 c++”来了解更多信息。

如果它看起来像一个数据库，闻起来像一个数据库......

于 2020-02-06T16:14:20.020 回答
0

好吧，首先，您收到错误的原因：“没有对 compareByVal 的匹配调用”是因为 map 的比较器仅适用于键。所以比较器应该像：

struct compareByVal {
  template <typename T>
  bool operator()(const T& a, const T& b) const
    return a < b;
}

谈到你想要实现的目标，我看到了两种方法：

  1. 将地图的所有元素复制到 std::vector 并对其进行排序：
std::vector<std::pair<int,int> > v(hash.begin(), hash.end());
std::sort(v.begin(), v.end(), [](const auto& a, const auto& b) { return a.second < b.second; });
  1. 将地图的所有元素复制到另一个地图，其中键作为值，值作为键。如果地图的值不是唯一的，则可以使用 std::multimap 代替。
于 2020-02-06T15:35:58.937 回答