Why does std::map::lower_bound fail for maps of size 1?

Question

I may have stumbled upon a bug, but it might just be the way they implemented the standard library. Is the following a bug?

In gcc 4.8.2 and clang 3.4 both if I use std::map::lower_bound() on a map that has only one element, it returns end() even if the element in the map would be a lower bound. See the following example code.

If you want to test this, be sure to use the following compile option: -std=c++11

#include <cstdlib>
#include <iostream>
#include <map>

#define ts_t std::pair<uint64_t,uint64_t>

int main() {

    std::map<ts_t,uint32_t> test;

    uint32_t count = 0;

    test.insert(std::make_pair(
        std::make_pair(1403187740ull,698599ull),
        count++
    ));

    ts_t key = std::make_pair(1403187740ull,698600ull);

    auto lower = test.lower_bound(key);
    auto upper = test.upper_bound(key);

    if(lower==test.end()) std::cout<<"no lower bound\n";
    if(upper==test.end()) std::cout<<"no upper bound\n";
    if(test.begin()->first < key) std::cout<<"key is less than begin()\n";

    test.insert(std::make_pair(
        std::make_pair(1403187740ull,698601ull),
        count++
    ));

    lower = test.lower_bound(key);
    upper = test.upper_bound(key);

    if(lower==test.end()) std::cout<<"no lower bound\n";
    if(upper==test.end()) std::cout<<"no upper bound\n";
    if(test.begin()->first < key) std::cout<<"key is less than begin()\n";

    return EXIT_SUCCESS;
}

Here is the output I am getting:

no lower bound
no upper bound
key is less than begin()
key is less than begin()

I expect to see:

no upper bound
key is less than begin()
key is less than begin()

Update: after the answer, I wrote this updated code which does accomplishes what I was after. I am posting it here incase other people are trying to accomplish the same thing:

#include <cstdlib>
#include <iostream>
#include <map>

#define ts_t std::pair<uint64_t,uint64_t>

int main() {

    std::map<ts_t,uint32_t> test;

    uint32_t count = 0;

    test.insert(std::make_pair(
        std::make_pair(1403187740ull,698599ull),
        count++
    ));

    ts_t key = std::make_pair(1403187740ull,698600ull);

    std::map<ts_t,uint32_t>::iterator upper = test.upper_bound(key);
    std::map<ts_t,uint32_t>::iterator lower;
    if(upper==test.begin()){
        lower = test.end();
    } else {
        lower = upper;
        --lower;
    }

    if(lower==test.end()) std::cout<<"no lower key\n";
    if(upper==test.end()) std::cout<<"no upper bound\n";
    if(test.begin()->first < key) std::cout<<"key is less than begin()\n";

    test.insert(std::make_pair(
        std::make_pair(1403187740ull,698601ull),
        count++
    ));

    lower = test.lower_bound(key);
    upper = test.upper_bound(key);

    if(lower==test.end()) std::cout<<"no lower key\n";
    if(upper==test.end()) std::cout<<"no upper bound\n";
    if(test.begin()->first < key) std::cout<<"key is less than begin()\n";

    return EXIT_SUCCESS;
}

Answer 1

You're misunderstanding what lower_bound means. It does NOT mean the element below it; it means the first element that is not less, i.e. greater-or-equal.

The purpose of this function is so that the range lower_bound, upper_bound matches all of the elements that are equal to the search key.