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

但这至少在某些情况下似乎不是最理想的，例如，如果我选择了一个点，以至于我只是从子树中分离出来。（我承认我实际上并没有仔细考虑这里算法复杂性的实际细节，但是如果我们想象一个值类型复制成本非常高的情况，那么很明显，上面的一般情况下不可能是最优的.)

问题：有没有办法std::map以最佳方式执行此操作，或者我是否必须编写自己的二叉搜索树来访问内部结构来完成此操作？

Answer 1

如果我们谈论的是渐近复杂性，那么您可以使用通俗称为和 的O(log n)两个操作，对大多数自平衡树类型及时执行此操作。维基百科上有一篇关于此的详细文章。splitjoin

您无法使用 来获得这种复杂性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;
}