std :: map range erase complexity [英] std::map range erase complexity

问题描述

cppreference.com 表示范围擦除的复杂性 std :: map 是：

log（c.size（））+ std： ：distance（first，last）

，而通过迭代器删除单个元素是经过摊销的常数。因此，如果我在一个循环中删除元素：

  for（auto it = first; it！= last; it = map.erase （it））; $ d $  std :: distance（first，last）     / code>，并且 cplusplus.com 同意这一点。标准说什么？这是只是在cppreference.com上打字？
解决方案
  log（c.size（））+ std :: distance（first，last） 
 
 
 
当（第一个，最后一个）是整个范围时，这是更大的因子，到 std :: distance（first，last），这是线性的，因此这与您的想法一致。
 
 
 
  it = map.erase（it）是摊销常数。它是不变的，加上（很少）一个微小的位用于遍历和平衡。当你添加所有这些有趣的小位togeather，他们总和到 C * log（c.size（））对于一些C> 1。
 
 
 
在这两种情况下，你想使用的是 map.clear（），它是 O / code>有一个非常小的常数。它比一次擦除更快，因为它可以跳过平衡。
 
cppreference.com says that complexity of range erase of std::map is:

  
log(c.size()) + std::distance(first, last)
while erase for single element by iterator is amortized constant. So if I erase elements in a loop:
for( auto it = first; it != last; it = map.erase( it ) );
that should be linear on std::distance(first, last), and cplusplus.com agrees with that. What does standard say? Is this just typo on cppreference.com?
解决方案
log(c.size()) + std::distance(first, last)

When (first,last) is the entire range, that is the bigger factor, so this simplifies to std::distance(first, last), which is linear, so this is consistent with your thoughts.

it = map.erase( it ) is amortized constant. It's constant, plus (rarely) a tiny bit for traversal and balancing.  And when you add all those ocasional tiny bits togeather, they sum to C*log(c.size()) for some C>1.

In either case, what you want to use is map.clear(), which is O(n) with a very small constant. It's far faster than erasing one at a time, since it can skip the balancing.

                        
这篇关于std :: map range erase complexity的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！