c++vectorupperbound

Retrieving index of vector using std::upper_bound, index out of bounds


I am attempting to retrieve a vector's index based on it's value using std::upper_bound. For some reason though, the following code sets tmpKey equal to 2 vs my expected value of 1. Does anything stick out as being horribly wrong?

int main()
{
    float time = 30.0000000;
    std::vector<float> positionKeyTimes = { 0.000000000, 30.0000000 };

    auto it = std::upper_bound(positionKeyTimes.begin(), positionKeyTimes.end(), time);
    auto tmpKey = (size_t)(it - positionKeyTimes.begin());

    std::cout << tmpKey << "\n";

    std::cin.get();
}

Solution

  • std::upper_bound

    Returns an iterator pointing to the first element in the range [first, last) that is greater than value, or last if no such element is found.

    There's no element greater than 30 in your vector, so the end iterator is returned.

    To get your expected value you could use std::lower_bound instead, which

    Returns an iterator pointing to the first element in the range [first, last) that is not less than (i.e. greater or equal to) value, or last if no such element is found.

    Remembering that

    The range [first, last) must be partitioned with respect to the expression element < value or comp(element, value), i.e., all elements for which the expression is true must precede all elements for which the expression is false. A fully-sorted range meets this criterion.