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

user_2462437 0
Viewed 731

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?

binary-search-tree c++
3 Answers

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;
}
user_5656350

There is extract, but it operates on nodes not node ranges.

And you can efficiently combine maps.

But there is no efficient (faster than O(n)) range based extract.

user_17746670

You can use move iterators, as follows

int main(){
    auto my_map = std::map<int, std::string>{
        {1, "Read"s},
        {2, "Blue"s},
        {3, "Green"s},
        {5, "Fuchsia"s},
        {6, "Mauve"s},
        { 9, "Gamboge"s },
        {10, "Vermillion"s}
    };
    auto it = my_map.begin();
    std::advance(it, 3);
    auto head_map = std::map{
        std::make_move_iterator(my_map.begin()),
        std::make_move_iterator(it)
    };
    auto tail_map = std::map{
        std::make_move_iterator(it),
        std::make_move_iterator(my_map.end())
    };
    std::cout << "The Head\n";
    for (auto [key, value]: head_map){
        std::cout << key << ":" << value << " ";
    }
    std::cout << "\n\nThe Tail\n";
    for (auto [key, value]: tail_map){
        std::cout << key << ":" << value << " ";
    }
}

Demo

user_96382720
Related