stl 벡터의 인덱스 범위에 대한 알고리즘

다음과 같은 데이터 테이블이 있습니다. 여기서 keyID는 중복 될 수 있다는 점에 유의하십시오. 나는 정렬 된 벡터 구조의 데이터 아래에 수집했습니다.stl 벡터의 인덱스 범위에 대한 알고리즘

struct myData { 
    int keyID; 
    int value; 
} 

vector<myData> vecReadFromFile;

이제 사용자는 특정 -a Keyid 키 ID를 입력하고 나는이 종료하면 벡터에 그 값을 종료하면 그 값을 반환 할 수 있는지 확인해야합니다. 만약 내가 어떤 값 사이에 예를 들어 사용자가 120030을 입력하면 가치가 120028과 120039 사이에 떨어지는 사이에 확인이 가치가 ie, lowerIndex 및 upperIndex이 예제에서 '2'및 '3'(vector 0에서 시작하는 인덱스)

사용자가 120001보다 적은 keyID를 입력하면 값을 반환하지 않습니다. 마찬가지로 사용자가 마지막 키 값보다 큰 keyID를 입력 한 다음 다른 오류 코드를 반환합니다.

기본적으로 주어진 키 값의 인덱스 범위를 효과적으로 찾고 싶습니다. 나는 위의 예제에서 버그가 무엇인지 언급 한 코드가 추가 된 것 같습니다.

STL 제공 algortihms를 사용하도록 논리를 변경할 수 있습니다. 제발 제안 해주세요.

어떻게이 알고리즘을 C++에서 효과적으로 구현할 수 있습니까? 샘플 코드를 함수로 요청하십시오. 여기서는 필자의 프로젝트에서 여러 번 함수를 호출 할 것이므로 효율적이어야한다.

keyID Value 

120002 10 
120025 20 
120028 25 
120039 30 
120042 - 
120048 40 
120052 50 
120112 60 
120117 70 
12
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; 
}

감사를 가지고

출처

2012-08-31 venkysmarty

이 혼란을하려고하고 당신은 아무것도 시도했습니다 것처럼 보이지 않습니다에 적용 할 수 있습니다 참조하십시오. – Aesthete

1) 열쇠 중복을 허용하는 STL 컨테이너 다중 세트를 선택하는 것이 더 바람직합니다. 2) lower_bound() 및 upper_bound() 메소드를 참조하십시오. –