CODEWITHSUNDEEP
c++stdmultimap
PolGraphic
PolGraphic

Reputation: 3364

How to get the iterator (or the value) for "previous" item for given key of std::multimap?

I would like to get the item that goes before given key, for my std::multimap.

For the item that goes after given key I could simply use std::multimap::upper_bound (it will return the element with key greater then given). But unfortunately, std::multimap::lower_bound returns the element with the "lower or equal" key.

The sample taken from http://www.cplusplus.com/reference/map/multimap/lower_bound/:

mymultimap.insert(std::make_pair('a',10));
mymultimap.insert(std::make_pair('b',121));
mymultimap.insert(std::make_pair('c',1001));
mymultimap.insert(std::make_pair('c',2002));
mymultimap.insert(std::make_pair('d',11011));
mymultimap.insert(std::make_pair('e',44));

itlow = mymultimap.lower_bound ('b');  // itlow points to b
itup = mymultimap.upper_bound ('d');   // itup points to e (not d)

How to get the iterator (or the value) for a when you give b as a parameter?

Upvotes: 2

Views: 2987

Answers (3)

Stewart Becker
Stewart Becker

Reputation: 308

We know the following that for any sequenced container (i.e. map, set, multimap and multiset):

  • lower_bound(key) returns the first entry >= key
  • upper_bound(key) returns the first entry > key

Each function also returns end() in the event there is no entry >= / > key.

So we have functionality based on the operators > and >=. We might reasonably ask, can we have functionality based on < and <= as well?

It is somewhat trivial to ask for the first entry < or <= key (this is either begin() or not in the container). However it is meaningful to ask for is the last such entry. Indeed, what you are asking for is the last entry < key.
For completeness we will consider the last entry <= key too.

Let's suppose we have such functions, what should they do if there is no such entry? We could do a lot worse than return end() too - it is a testable value and distinct from any successful case. It is also consistent with both lower_bound, upper_bound, as well as find and a whole host of standalone search functions in the <algorithm> header. The bottom line is that end() is routinely used to mean `no such entry' so this should be good enough for us as well.

As noted by Barry and Mark, calling lower_bound(key) and then decrementing will give us what we want, unless lower_bound(key) == begin(). In this case, the first (and thus [joint-]smallest) entry is >= key, so there are no entries < key - precisely the scenario where we just said we should return end().

For the case of looking for the last entry <= key we can do the same but with upper_bound, again returning end() to mean 'no such entry' when upper_bound(key) == begin().

Lets call these functions lower_bound_dec and upper_bound_dec respectively:

// Find the last entry < key, returning end() if all entries are >= key
// Container can be any that implements lower_bound, e.g. std::map, std::multimap, std::set or std::multiset
template<typename Container, typename Key>
typename Container::const_iterator lower_bound_dec(const Container &container, const Key &key) {
    auto it = container.lower_bound(key);
    if (it == std::begin(container))
        it = std::end(container);
    else
        --it;
    return it;
}

// Find the last entry <= key, returning end() if all entries are > key
// Container can be any that implements upper_bound, e.g. std::map, std::multimap, std::set or std::multiset
template<typename Container, typename Key>
typename Container::const_iterator upper_bound_dec(const Container &container, const Key &key) {
    auto it = container.upper_bound(key);
    if (it == std::begin(container))
        it = std::end(container);
    else
        --it;
    return it;
}

We might also define iterator based functions, that mirror std::lower_bound and std::upper_bound and can operate on any sorted range with bidirectional iterators:

// Find the last entry < key, returning end() if all entries are >= key
// last must be reachable from first, and all entries in sorted order between them
template<typename Iterator, typename Key>
Iterator lower_bound_dec(Iterator first, Iterator last, const Key &key) {
    auto it = container.lower_bound(first, last, key);
    if (it == first)
        it = last;
    else
        --it; // requires bidirectional iterators
    return it;
}

upper_bound(first, last, key) and the forms that take a comparator left as exercises to the reader / anyone who wants to earn rep by editing! :)

TL/DR: Use lower_bound and then decrement, with the caveat that "decrementing" begin() yields end() to mean 'no such entry.'

Upvotes: 1

Barry
Barry

Reputation: 303097

You can use lower_bound, but there are two edge cases you have to consider: it returns begin() and it returns end():

auto itfound = mymultimap.lower_bound('b');
if (itfound == mymultimap.begin()) {
    // 'b', or something past 'b', is the first item
    // or the map is empty
    // what to do here?
}
else if (itfound == mymultimap.end()) {
    // there does not exist an item >= 'b'
    // what to do here? possibly std::prev(end()) ?
}
else {
    // ok cool, we found something in the middle
    // just back up
    --itfound;

    // do stuff with itfound here
}

Upvotes: 5

Mark Ransom
Mark Ransom

Reputation: 308206

Go ahead and use lower_bound, then decrement the iterator you receive (after checking to make sure it isn't begin).

itfound = mymultimap.lower_bound('b');
if (itfound != mymultimap.begin())
{
    --itfound;
    // do something with itfound
}

You may need slightly different logic if the item isn't in the map, but that shouldn't be a hard modification.

Upvotes: 2

Related Questions