1

ソースIDと優先度に従って並べ替えることができる着信メッセージの「コンテナ」として、ペアキーを使用したマップ（前の質問の後に最適な実装のように見えました）を使用しています。 intvalue。処理はこのマップ上で行われます。

問題が発生したばかりです。後でメッセージを取得するには、次の擬似コードのようなことを行う必要があります。

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で使用可能なメッセージがあることを確認する必要があるため、これを確認する簡単な方法を探しています。

を使用すると、ノード2に使用可能なメッセージがないことを確認したい場合に、のvector<vector<int>>ようなことができるようになります。node[2].empty()マップに相当するものはありますか？

4

3 に答える 3

3

私が物事を正しく理解しているなら、あなた(node_id,i)は地図がいくつのエントリを持っているか、どこnode_idが固定されているか、そしてi何でもよいかを決定する便利な方法が欲しいです。

この理解が正しければ、マップ内の順序は、で定義された順序に基づいているという事実を利用できますstd::less<std::pair<int,int>>。これは、デフォルトでは辞書式順序です。つまり、node-idがメインの並べ替え基準として使用され、ペアの2番目の要素が2番目の並べ替え基準として使用されます。

したがって、マップのlower_boundandupper_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

考えられる解決策の1つは、2つのネストされたマップを使用することです。

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

指定されたsourceIdのメッセージがあり、指定されたsopurceIdと優先度のメッセージを検索する必要がある場合、2回のルックアップの価格で優先度が簡単になるかどうかを確認します。

于 2013-02-25T04:02:47.937 に答える