c++ - std::map 可以在迭代器中有效地拆分为两个 std::map 吗？

Question

假设我有一个 std::map<int, std::string> myMap包含数据

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

还有一个 std::map<int, std::string>::iterator it指向元素

5. Fuchsia

我想做类似的事情(编造)

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

这将导致 myMap包含

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

和 myHead包含

1. Red
2. Blue
3. Green

我可以通过做类似的事情来实现这一点

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

但这至少在某些情况下似乎不是最理想的，例如如果我选择一个点，以至于我只是从子树上 split 出来。 (我承认我实际上并没有仔细考虑这里算法复杂性的实际细节，但是如果我们想象一个值类型复制成本非常高的情况，那么很明显，上面的一般情况下不可能是最优的.)
问题:有什么办法可以得到 std::map以最佳方式执行此操作，还是我必须编写自己的二叉搜索树来访问内部结构来完成此操作？

Answer 1

如果我们说的是渐近复杂性，您可以在 O(log n) 中执行此操作大多数自平衡树类型的时间，使用通俗地称为 split 的两个操作和 join .有一个广泛的Wikipedia article在这一点上。
使用 std::map 无法获得这种复杂性，您需要推出自己的或第三方的自平衡树实现。如果您需要经常执行此操作，这是非常值得的。使用标准库可以获得的最佳结果是 O(n) ，这可能会慢许多数量级。
您可以在 O(n) 中完成在 C++11 中为:

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