std::map 迭代器和插入的行为

Question

作为一个简单的开始

Map<key,val> map1=//filled up in some way;
Map<key,val> map2;
map2.insert(map1.begin(),map1.end());

我们知道 map::insert 是 O(log(n))，没有提供提示。这是否意味着上面的运行s 在 O(nlog(n)) 中，或者它是否使用了 map1 已经排序并简单地插入到正确位置（递增当前迭代器）的事实？因为 map1 已经排序，所以我们应该能够在线性时间内完成此操作。怎么样

std::copy(map1.begin(),map1.end(),map2.end());

它是每次都在 O(log(n)) 中插入，还是在 O(1) 中复制到通过递增迭代器标记的受尊重的位置？

也许是一个更能说明问题的例子

template<class InIter, class OutIter, class ResIter>
ResIter foo(InIter first, OutIter last, ResIter res){
   while(first!=last){
      res=*first;
      ++first;
      ++res;
   }
return res;
}

当我们处理映射迭代器时，这个运行是 O(n) 还是 O(nlog(n))？插入是 O(log(n))，还是 O(1)，因为我们指定了位置，即 *res=*first?

为清楚起见编辑：

有

*res=*first

表现得像

map2.insert(res,*first)

意思是，插入到 map2 中，使用指向正确位置的迭代器 res 作为提示，使其成为 O(1)，还是执行常规的 O(log(n)) 插入？

Answer 1

快速阅读标准后，对void insert(InputIterator first, InputIterator last);的复杂性没有要求。因此，允许惰性实现具有 O(n log(n)) 复杂性，即使由于以下原因 map1 为空，它也可能是线性的。

因为如果输入范围已排序，标准确实要求构造函数的线性复杂度，所以这需要为 O(n):

Map<key,val> map1=//filled up in some way;
Map<key,val> map2(map1.begin(),map1.end()); // complexity in O(n)

对于你问题的第二部分，因为你想给出元素插入位置的提示，正确的方法是：

template<class InIter, class OutIter, class ResIter>
ResIter foo(InIter first, OutIter last, ResIter res){
   while(first!=last){
      emplace_hint(res, *first);
      ++first;
      ++res;
   }
return res;
}

不幸的是，标准对 emplace 或 emplace_hint.

的复杂性没有要求

std::map 迭代器和插入的行为

Behavior of std::map iterators and insertions

c++

iterator

stdmap

time-complexity