1

以下に示すようなデータの表があります。ここで、keyID は重複する可能性があることに注意してください。以下のデータをベクター構造で収集しました。これはソートされています。

struct myData {
   int keyID;
   int value;
}

vector<myData> vecReadFromFile;

ユーザーが特定のキー ID を入力すると、その値がベクター内に存在するかどうかを確認する必要があります。存在する場合は、その値を返す必要があります。そうでない場合は、たとえばユーザーが 120030 を入力した場合、値が 120028 と 120039 の間に収まる値の間を確認する必要があります。これらの値のインデックスを取得する必要があります。つまり、この例では '2' と '3' (ベクトルとしてインデックスは 0 から始まります)

ユーザーがより少ないキー ID、つまり 120001 を入力すると、値は返されません。同様に、ユーザーが最後のキー値より大きいキー ID を入力すると、別のエラー コードが返されます。

基本的に、特定のキー値のインデックス範囲を効果的に見つけたいと考えています。上記の例で動作していないように見えるコードを追加しました。バグとは何ですか?

ロジックを変更して、STL が提供するアルゴリズムを使用できます。提案してください。

このアルゴリズムを C++ で効果的に実現するにはどうすればよいでしょうか? サンプルコードを関数としてリクエストします。ここで、プロジェクトで関数を何度も呼び出すので、効果的でなければならないことに注意してください。

keyID   Value   

120002  10  
120025  20  
120028  25  
120039  30  
120042  -   
120048  40  
120052  50  
120112  60  
120117  70  
120123  70  
120126  80  
120130  90

ここにいくつかのコードがあります

 //==========================================================================
// FindBounds
bool FindBounds(const KEY& cTarget, UINT& uLower, UINT& uUpper)
{
  uLower = -1;
  uUpper = -1;

  // start with full range of data.
  uLower = 0;
  uUpper = m_uCount-1; // Here I have m_uCount as vector.size()

 // narrow the bounds as much as possible.
 while (uUpper - uLower > 1 && cTarget != m_pKeys[uLower])
 {  
    // split the range in half and discard the half that the key does not belong to. 
    UINT uBound = uUpper - (uUpper-uLower)/2;
    // keep the lower range.
    if (KeyInRange(uLower, uBound, cTarget))
    {
       uUpper = uBound;
    }
    // keep the upper range.
    else
    {
      uLower = uBound;
    }
 }

}

bool KeyInRange(UINT uLower, UINT uUpper, const KEY& cTarget)
{
    // check if target is within range.
    if (m_pKeys[uLower] <= cTarget)
    {
    if (m_pKeys[uUpper] > cTarget || (m_pKeys[uLower] == cTarget && m_pKeys[uLower] == m_pKeys[uUpper]))
    {
            return true;
    }
     }
    // target is not within range.
    return false;
}

お時間をいただきありがとうございます。

4

3 に答える 3

5

std::equal_rangeアルゴリズムがあります。

于 2012-08-31T12:55:26.053 に答える
5

std::lower_bound()STL から、<algorithm>ヘッダー: http://en.cppreference.com/w/cpp/algorithm/lower_bound

于 2012-08-31T12:58:49.300 に答える
1

1）キーでいくつかの値を検索する場合は、キーの重複を許可する STL コンテナーmultisetを選択する方がよいと思います。

2）メソッドlower_bound()を参照してくださいupper_bound()。それらは、実行しようとしていることに適用できる可能性があります

于 2012-08-31T12:59:57.393 に答える