0

私はqmapの<int , Myclass*>

キーの範囲は1～n_maxです。

マップに挿入するときは、利用可能な最も低い未使用のキーを知る必要があります。

たとえば、マップに含まれている場合

<1、オブジェクト1>

<3、obj3>

マップに次のアイテムを挿入するとき、キーを 2 に割り当てたいと思います

これを行う最も効率的な方法は何ですか

よろしく

4

2 に答える 2

1

検索を最適化するために、おそらくいくつかのことを行う必要があります。

最初に、count()map.end() の前のレコード (つまり --) などと照合します。それらが同じであれば、それがいっぱいであることがわかり、最後に追加できます。

そうでない場合 (最後の反復子の値が より大きい場合count())、穴を探す必要があることがわかります。全体を検索するときは、おそらくすべてを引き出してからuniqueKeys()、その中央から検索を開始して、中央のキーが前のキーと一致するかどうかを確認しますcount()/2。そうでない場合は、さらに 1 つ下に移動しcount()/4、そうでない場合は 1 つ上に移動しcount()/4ます。探しているものが見つかるまで繰り返します。

しかし、実際には、そもそもマップが適切なコンテナーであるかどうかはわかりません。配列またはリンクされたリストが必要なように聞こえますが、データによって異なります。ただし、マップを使用して上記の操作を行う必要がある場合は、おそらく適切なコンテナーを見つける必要があることをお勧めします。

于 2012-03-09T14:58:30.987 に答える
0

QMap はキーでソートされたアイテムを保持するため、c++ 標準ライブラリの々の Context_Find アルゴリズムを使用できます。

#include <QMap>
#include <algorithm>

bool missing (int i, int j) {
  return (i+1 < j);
}

int next_key(const QMap<int,int>& map) {
  if (!map.size()) 
    return 1; // or 0, if an acceptable key value

  QList<int>::iterator i = std::adjacent_find(map.keys().begin(), map.keys().end(), missing);

  if (i==map.keys().end()) // no missing values found
    --i; 

  return *i + 1;
}

複雑度は、(結果 - 最初) + 1 および (最後 - 最初) - 述語 (「欠落」関数) の 1 適用のうち、正確に小さい方です。ここで、結果は戻り値です。

于 2012-03-10T12:01:29.360 に答える