1

我正在使用一个地图（这似乎是上一个问题之后最好的实现，带有一对键，作为传入消息的“容器”，可以根据 sourceID 和优先级进行排序，即 key: (sourceID, priority) 指向一个int 值。处理将在此地图上进行。

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

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>>，我将能够轻松地做到这一点，但目前地图更适合我的程序。

编辑：

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

我知道如果我使用 a ，如果我想检查节点 2 是否没有可用消息vector<vector<int>>，我将能够执行类似的操作。node[2].empty()地图有等价物吗？

4

3 回答 3

3

(node_id,i)如果我理解正确，您会想要一种方便的方法来确定地图有多少条目，在哪里node_id是固定的并且i可以是任何东西。

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

因此，您可以使用 map 的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上面定义的函数返回给定 node-id映射中的条目数node_id。

所以你的伪代码变成：

if (num_per_node(mymap,nodeID) > 0)

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

请注意，这仅有效，因为您的对的元素是int，因此很容易建立最小值和最大值。同样，它也仅因字典顺序而起作用。如果您在地图上使用自定义的比较器功能，则此方法将不再起作用，并且是否可以找到对应的方法取决于您的比较器是如何定义的。

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

于 2013-02-25T03:40:29.853 回答
1

只是为了建立@jogojapan 所做的工作，我已经对其进行了调整以不使用 C++11（因为我没有使用它），并将其留在这里以供参考。不确定它会做他所做的一切，但对我来说足够用

#include <iostream>
#include <utility>
#include <limits>
#include <map>

using namespace std;

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

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

  int main() {
    map<pair<int, int>, int> m;
    m.insert(make_pair(make_pair(1,3),1));
    m.insert(make_pair(make_pair(3,4),2));
    m.insert(make_pair(make_pair(3,5),3));
    m.insert(make_pair(make_pair(3,9),4)); 
    m.insert(make_pair(make_pair(4,2),5)); 
    m.insert(make_pair(make_pair(4,3),6)); 
    m.insert(make_pair(make_pair(5,1),7)); 
    m.insert(make_pair(make_pair(8,2),8));

    for (int node_id = 0 ; node_id < 10 ; ++node_id)
      std::cout << "node-id " << node_id << ": " << num_per_node(m,node_id) << '\n';

    return 0;
  }

正确返回

node-id 0: 0
node-id 1: 1
node-id 2: 0
node-id 3: 3
node-id 4: 2
node-id 5: 1
node-id 6: 0
node-id 7: 0
node-id 8: 1
node-id 9: 0
于 2013-02-25T07:51:30.283 回答
0

一种可能的解决方案是使用 2 个嵌套地图：

typedef std::map<int,int> priorities;
typedef std::map<int,priorities> messages;

查找给定 sourceId 是否有任何消息，并且当您需要查找具有给定 sopurceId 和优先级的消息时，任何优先级对于 2 次查找的价格都变得微不足道。

于 2013-02-25T04:02:47.937 回答