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

Question

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

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

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

Complexity N*log(size()+N)), where N is source.size()

对吗？

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

std::map::merge 的时间复杂度的真相是什么？

Answer 1

I would expect that std::map::merge takes advantage of the fact that the elements of both std::maps are already sorted, so there is no need to search the place of insertion for every single element [...]

您忽略了要合并的地图可能是不同类型的事实，即它可能使用不同的排序：

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

因此实际上必须考虑要合并的地图未排序以获得最坏情况的复杂性。

Answer 2

想象一下这个方法的可能实现：

for (auto const& iter : source)
{
   dest. insert( iter);
}

因此您遍历源映射（复杂度 N），并将每个元素插入复杂度为 log(dest.size()+N) 的目标映射中。
正如user463035818的另一个答案已经指出的那样，两个映射的顺序不一定相同，因此您必须分别插入每个元素。
最后，树排序算法的构建方式必须是从根节点向下遍历树，并在向下或再次返回时进行平衡。很难编写一个按顺序遍历树的算法，添加元素和平衡树。

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

Computational time complexity of std::map::merge

c++

stdmap

std

binary-search-tree

c++17