Re: How to get the iterator for a value less than the key specified?

From:

"Greg Herlihy" <greghe@pacbell.net>

Newsgroups:

comp.lang.c++.moderated

Date:

8 Jun 2006 18:54:35 -0400

Message-ID:

<1149749505.895273.78480@h76g2000cwa.googlegroups.com>

Albert Jin wrote:

Neither of the two methods, lower_bound and upper_bound, for std::set
does return the iterator less than the key specified. Is there a
better way to approach this?

template <typename Set>
typename Set::const_reverse_iterator less_lower_bound(Set const & set,
typename Set::const_reference key) {
    Set::key_compare key_comp = set.key_comp();
    Set::const_reverse_iterator i = set.rbegin();
    for (; i != set.rend(); ++i) {
        if (!key_comp(key, *i)) {
            break;
        }
    }
    return i;
}

There is certainly a less complicated solution: obtain the lower bound
iterator for the key from the set, then compare it against the set's
begin() iterator. If they compare unequal then decrement the
lower_bound iterator to find the iterator in question. If instead the
two iterators compare equal, then it is certain that no value lower
than the specified key is present in the set.

Greg

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]