std::multimap getting two ranges

Question

I'm using a C++ std::multimap and I have to loop over two different keys. Is there an efficient way to do this other than creating two ranges and looping over those ranges seperately?

This is the way im doing it now:

std::pair<std::multimap<String, Object*>::iterator,std::multimap<String, Object*>::iterator> range;
std::pair<std::multimap<String, Object*>::iterator,std::multimap<String, Object*>::iterator> range2;

// get the range of String key
range = multimap.equal_range(key1);
range2 = multimap.equal_range(key2);

for (std::multimap<String, Object*>::iterator it = range.first; it != range.second; ++it)
{
    ...
}
for (std::multimap<String, Object*>::iterator it2 = range2.first; it2 != range2.second; ++it2)
{
    ...
}

This is my first time using multimap's so I'm not too familiar with them. I will be doing alot of work in those loops and I was wondering if there is another operation where you could get two ranges at the same time or something. — Kaiser Wilhelm, Sep 07 '11 at 15:26
Can you give an example of keys where the keys overlap, but do not equal each other? Maybe my brain is soggy, but it seems like a simple equality check on the keys would do it. It makes more sense to me if you had separate lower and upper bounds for each query. — Tom Kerr, Sep 07 '11 at 15:44
it's a great example when single `typedef` can eliminate bigger half of code and make code dramatically more readable: `typedef std::multimap::iterator Iter` — Andriy Tylychko, Sep 07 '11 at 16:10

score 3 · Accepted Answer · answered Sep 07 '11 at 15:27

3

The code you started with is the most straightforward.

If you'd really like to iterate over two ranges in the same loop, you can create a custom iterator that takes two iterator ranges, iterates over the first until it's done then switches to the second. This is probably more trouble than it's worth, as you'd need to implement all of the iterator members yourself.

Edit: I was overthinking this; it's easy just to modify the two loops into a single one.

for (std::multimap<String, Object*>::iterator it = range.first; it != range2.second; ++it)
{
    if (it == range.second)
    {
        it = range2.first;
        if (it == range2.second)
            break;
    }
    ...
}

answered Sep 07 '11 at 15:27

Mark Ransom

299,747
42
398
622

I thought of this as well. However, do these two keys have to be next to each other for this to work? For instance if I have 3 keys and I want to loop over the 1st and the 3rd wont it include the 2nd with them? Or do those if statements fix that? – Kaiser Wilhelm Sep 07 '11 at 15:34
1

@Kaiser, the `if` statements handle the transition from the first range to the second. They can even be out of order. The only thing they *can't* do is intersect; if `range2` includes `range.second` then you'll get an infinite loop. – Mark Ransom Sep 07 '11 at 15:44
Ahh I see. My range2 is static and range1 is always going to be different. They should never intersect correct? Since multimap sorts it upon insertion? – Kaiser Wilhelm Sep 07 '11 at 15:49
1

@Kaiser, as long as the keys are different and you use `equal_range` as you did in your question, the ranges will not intersect. I also checked to make sure your `range2` iterators wouldn't be invalidated by insertion: http://stackoverflow.com/questions/6438086/iterator-invalidation-rules – Mark Ransom Sep 07 '11 at 16:39

score 3 · Answer 2 · edited May 23 '17 at 11:47

3

Boost does this, of course. Using Boost.Range and its join function will get you what you want. See Boost Range Library: Traversing Two Ranges Sequentially for more details.

edited May 23 '17 at 11:47

Community

1
1

answered Sep 07 '11 at 15:29

deft_code

57,255
29
141
224

Thanks, Boost seems really powerful. Unfortunately, my company is old school and hates new things... I guess they'll have to settle for inefficiency – Kaiser Wilhelm Sep 07 '11 at 15:32
this time it's not about efficiency, it's about convenience – Andriy Tylychko Sep 07 '11 at 16:08

score 0 · Answer 3 · answered Sep 07 '11 at 19:38

If you have access to C++-11 (Visual Studio 10+, gcc-4.5+) and are allowed to use it auto is a real gem:

// get the range of String key
auto range = multimap.equal_range(key1);
auto range2 = multimap.equal_range(key2);

for (auto it = range.first; it != range.second; ++it)
{
    ...
}
for (auto it2 = range2.first; it2 != range2.second; ++it2)
{
    ...
}

Anyway, I would just test the keys and only do the second loop if key2 != key1. Checking iterators each time in a loop has some cost.

A std::set_difference of the first range from the second might streamline the code. Maybe std::set_union the two ranges and insert through back_inserter into a set so you only get one copy?

Some experiments may be in order. Don't forget to put your first guess in the mix. It might surprise you by being just fine in terms of speed. Unless the ranges are typically very long and/or the loop operation is expensive it may not be worth the headache of extra bookkeeping.

std::multimap getting two ranges

3 Answers3