时间戳

首页 > 解决方案 > std::map 可以在迭代器处有效地拆分为两个 std::maps 吗？

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

问题描述

假设我有一个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以最佳方式执行此操作，或者我是否必须编写自己的二叉搜索树才能访问内部结构来完成此操作？

标签： c++binary-search-tree

解决方案

如果我们说的是渐近复杂性，O(log n)对于大多数自平衡树类型，您可以及时执行此操作，使用通俗地称为split和的两个操作join。有一篇关于此的广泛的Wikipedia 文章。

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

推荐阅读