使用对作为键的 C++ 映射

Question

我正在使用 map (这似乎是 previous question 之后的最佳实现，带有一对键，作为传入消息的“容器”，可以根据 sourceID 和优先级进行排序，即键:(sourceID，优先级)它指向一个 int 值。处理将在这张 map “上”发生。

我刚刚遇到了一个问题 - 我需要执行类似于此伪代码的操作来随后检索消息:

map<pair<int, int>, int> mymap;

if (!mymap[make_pair(nodeID,i)].empty()) //i refers to all the priority levels
    //processing occurs here to retrieve a value

但我似乎做起来并不容易。有没有一种方法可以在不运行迭代器的情况下简单地做到这一点，例如for (i = 0; i <priority ; i++) ？我知道如果我使用等效的 vector<vector<int>>我可以很容易地做到这一点，但 map 目前更适合我的程序。

编辑:

消息按(sourceID，优先级)分类到映射中，然后在按(destID，优先级)映射到另一个映射之前进行处理。我需要检查是否有消息可用于任何特定的 destID，无论优先级如何，因此我正在寻找一种简单的方法来检查它。

我知道如果我使用 vector<vector<int>> , 我将能够做类似 node[2].empty() 的事情，如果我想检查节点 2 是否没有可用消息。有 map 的等效项吗？

Answer 1

如果我没理解错的话，你会想要一种方便的方法来确定有多少条目(node_id,i) map 有，哪里node_id是固定的，i可以是任何东西。

如果这种理解是正确的，您可以利用 map 中的排序基于 std::less<std::pair<int,int>> 定义的排序这一事实。 ，默认情况下是字典顺序。换句话说，node-id 将用作主要排序标准，而 pair 中的第二个元素将用作次要排序标准。

因此您可以使用 lower_bound和 upper_bound映射函数以确定给定节点 ID 的条目范围，如下所示(C++11 代码，但可以转换为 C++03):

std::ptrdiff_t num_per_node(const mymap &map, const int node_id)
{
  using std::distance;
  static constexpr int min = std::numeric_limits<int>::min();
  static constexpr int max = std::numeric_limits<int>::max();

  auto lo = map.lower_bound({node_id,min});
  auto hi = map.upper_bound({node_id,max});
  return distance(lo,hi);
}

上面定义的函数返回映射 map 中的条目数对于给定的节点 ID node_id .

所以你的伪代码变成:

if (num_per_node(mymap,nodeID) > 0)

该函数具有对数复杂度，这显然(渐近)优于遍历所有优先级值。

请注意，这仅适用于您的对的元素是 int ，因此很容易确定最小值和最大值。同样，它也只适用于字典顺序。如果您将自定义的比较器函数与您的 map 一起使用，此方法将不再有效，并且是否可以找到相应的方法取决于您的比较器的定义方式。

这是一个带有完整示例的 GIT-gist，演示了如何使用该函数:https://gist.github.com/jogojapan/5027365