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(n) 快）基于范围的提取。

Answer 2

可以使用move iterators，如下

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

Answer 3

如果我们说的是渐近复杂性，对于大多数自平衡树类型，您可以在 O(log n) 时间内完成此操作，使用两个俗称 split 和 join 的操作。对此有广泛的 Wikipedia article。

您无法使用 std::map 获得这种复杂性，您需要自己或第三方实现自平衡树。如果您需要经常执行此操作，这是非常值得的。使用标准库可以获得的最好的是 O(n)，它可以慢很多个数量级。

您可以在 C++11 中的 O(n) 中执行此操作：

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

std::map 能否在迭代器中有效地拆分为两个 std::map？

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

c++

binary-search-tree