时间戳

首页 > 解决方案 > std::map::merge 的计算时间复杂度

c++ - std::map::merge 的计算时间复杂度

问题描述

C++17 引入了一个将一个合并到另一个的std::map::merge函数。std::map

由于std::map是有序关联容器，更明确地说是自平衡二叉搜索树（最常实现为红黑树或 AVL 树），我希望std::map::merge利用两个std::maps 的元素已经排序的事实，所以不需要搜索每个元素的插入位置，即时间复杂度应该是线性摊销的O(N)。

有趣的是， cppreference 表示的计算时间复杂度std::map::merge是对数的O(N*log(N))：

复杂度N*log(size()+N))，其中 N 是 source.size()

那是对的吗？

在这种情况下std::map::merge似乎等同于std::map::insert(iterator begin, iterator end)，std::map::merge完全是多余的。

的时间复杂度的真实情况是std::map::merge什么？

标签： c++binary-search-treestdc++17stdmap

解决方案

我希望 std::map::merge 利用两个 std::maps 的元素已经排序的事实，因此无需搜索每个元素的插入位置 [...]

您错过了要合并的地图可能属于不同类型的事实，即它可能使用不同的排序：

template <class C2>
void merge(std::map<Key, T, C2, Allocator>& source); 
                            ^--- this is not necessarily the same as for the map you 
                                 are merging into

所以实际上要合并的地图必须被认为没有排序以获得最坏情况的复杂性。

推荐阅读