CODEWITHSUNDEEP
c++
venkysmarty
venkysmarty

Reputation: 11431

Algorithm for index range of values in stl vector

I have a table of data as shown below. Note here is that keyID can be duplicates. I have collected below data in vector structure, which is sorted.

struct myData {
   int keyID;
   int value;
}

vector<myData> vecReadFromFile;

Now user enters a particular keyID, and I have to check if that value exits in vector, if exits I have to return that value. If not I have to check between which values it fall for example if user enters 120030, value falls between 120028 and 120039 here I should get index of these values i.e., lowerIndex and upperIndex in this example '2' and '3' (as vector index starts at 0)

If user enters less keyID i.e., 120001 then return no value. Similarly user enters keyID greater than last key value then return an different error code.

Basically I want to find index range of given key value effectively. I have added code which is present seems not working for above example I mentioned what is bug?

I can change logic to use STL provided algortihms. Please suggest.

How we can achive this algorithm effectively in C++? Request with sample code as function. Note here I will call function many times in my project so it has to effective.

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

I have some code here

 //==========================================================================
// 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;
}

Thanks for your time and help

Upvotes: 1

Views: 756

Answers (3)

spin_eight
spin_eight

Reputation: 4025

1)I think if you are going to lookup some values by their keys better to choose STL container multiset, which allows key duplicates.

2) see methods lower_bound() and upper_bound() they might be applicable to that you are trying to do

Upvotes: 1

Rost
Rost

Reputation: 9089

std::lower_bound() from STL, <algorithm> header: http://en.cppreference.com/w/cpp/algorithm/lower_bound

Upvotes: 5

James McNellis
James McNellis

Reputation: 355079

There is the std::equal_range algorithm.

Upvotes: 5

Related Questions