Can a std::map be efficiently split into two std::maps at an iterator?

Question

Let's say I have a std::map<int, std::string> myMap containing the data

1. Red
2. Blue
3. Green
5. Fuchsia
6. Mauve
9. Gamboge
10. Vermillion

and also an std::map<int, std::string>::iterator it pointing at the element

5. Fuchsia

I would like to do something like (making this up)

std::map<int, std::string> myHead = eject(myMap, myMap.begin(), it);

which would result in myMap containing

5. Fuchsia
6. Mauve
9. Gamboge
10. Vermillion

and myHead containing

1. Red
2. Blue
3. Green

I could accomplish this by doing something like

std::map<int, std::string> myHead;
myHead.insert(myMap.begin(), it);
myMap.erase(myMap.begin(), it);

but this seems suboptimal in at least some cases, e.g. if I pick a point such that I'm just splitting off a subtree. (I'll admit that I haven't actually thought through the actual details of the algorithmic complexity here, but if we imagine a case where the value type is extraordinarily expensive to copy then it's clear that the above can't be optimal in general.)

Question: is there a way that I can get std::map to perform this operation in an optimal manner, or do I have to write my own binary search tree where I have access to the internals to accomplish this?

Answer 1

If we're speaking asymptotic complexity, you can do this in O(log n) time for most self-balancing tree types, using two operations colloquially known as split and join. There's an extensive Wikipedia article on this.

You can not get this complexity using std::map, you'll need to roll your own or a third-party self-balancing tree implementation. If you need to do this operation often, this is well worth it. The best you can get using the standard library is O(n), which can be many orders of magnitude slower.

You can do it in O(n) in C++11 as:

template<class K, class T, class C, class A>
std::map<K, T, C, A> eject(
    std::map<K, T, C, A>& my_map,
    std::map<K, T, C, A>::iterator begin,
    std::map<K, T, C, A>::iterator end,
) {
    std::map<K, T, C, A> result;
    while (begin != end) {
        auto next = std::next(begin);
        // C++11
        result.insert(result.end(), std::move(*begin));
        my_map.erase(begin);
        // C++17 (avoids move and destruct)
        // result.insert(result.end(), my_map.extract(begin));
        begin = next;
    }
    return result;
}