How to search in a map/multimap starting from specific position

Question

I want to search in a map/multimap but not all of it. Instead I want to start in a specific position.

In the following example I want to find the two first numbers that sum b. And return their value.

multimap<int, int> a;
a.insert(make_pair(2, 0));
a.insert(make_pair(2, 1));
a.insert(make_pair(5, 2));
a.insert(make_pair(8, 3));

int b = 4;

for(auto it = a.begin(); it != a.end(); ++it) {
    auto it2 = a.find(b - it->first); //Is there an equivalent that starts from "it+1"?
    if(it2 != a.end()) {
        cout << it->second << ", " << it2->second << endl;
        break;
    }
}

output:

0, 0

desired output:

0, 1

Is it possible to achieve specific position search in a map?

Answer 1

How to search in a map starting from specific position

You could use std::find. But this is not ideal, since it has linear complexity compared to logarithmic complexity of a map lookup. The interface of std::map doesn't support such operation for lookups.

If you need such operation, then you need to use another data structure. It should be possible to implement by augmenting a (balanced) search tree with a parent node pointer. The downside is of course increased memory use and constant overhead on operations that modify the tree structure.

not from the beginning to the end.

Map look ups do not start from "the beginning" of the range. They start from the root of the tree.