c++ - 在 C++ 中优化 if-else 分支的小循环

Question

是否可以在以下循环中删除分支。所有迭代器都来自容器类型std::map<type_name, T>

  record_iterator beginIter = lastLookup_;                                                                                                                                                                                                                                                                                                                             
  record_iterator endIter = lastLookup_;                                                                                                                                                                                                                                                                                                                               
  ++endIter;                                                                                                                                                                                                                                                                                                                                                           
  for(;endIter != end(); ++beginIter, ++endIter){                                                                                                                                                                                                                                                                                                                      
    time_type now = beginIter->first;                                                                                                                                                                                                                                                                                                                                  
    if(ts == now){                                                                                                                                                                                                                                                                                                                                                     
      lastLookup_ = beginIter;                                                                                                                                                                                                                                                                                                                                         
      return beginIter;                                                                                                                                                                                                                                                                                                                                                
    }else if(ts > now && ts <= endIter->first){                                                                                                                                                                                                                                                                                                                        
      lastLookup_ = beginIter;                                                                                                                                                                                                                                                                                                                                         
      return endIter;
    }
  }

该算法试图解决的问题是优化前向查找，该位置被假定为与上次查找的位置相同或（不太远）向前。理想情况下，我保留了上次查找位置的迭代器，并线性前进。但这似乎具有相同的性能，

  record_iterator it= sliceMap_.find(ts);                                                                                                                                                                                                                                                                                                                              
  if(it !=end()){                                                                                                                                                                                                                                                                                                                                                      
    return it;                                                                                                                                                                                                                                                                                                                                                         
  }else{                                                                                                                                                                                                                                                                                                                                                               
    return sliceMap_.upper_bound(ts);                                                                                                                                                                                                                                                                                                                                  
  }         

我觉得问题出在分支上，所以可以在这段代码中删除分支，这样我就可以分析速度的不同了吗？

Answer 1

第一种方法存在三个大问题：

• 循环内的比较太多。
• 在 a 上使用迭代器std::map涉及 using std::map<>::iterator::operator++()，这并不是很快。查看从第 62 行开始的实现：http: //gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-3.4/tree_8cc-source.html。
• 在 a 上使用迭代器std::map是一种线性搜索。在地图上搜索应该是对数的。

你的第二种方法也有问题。您正在搜索两次。

你为什么不直接使用

return sliceMap_.lower_bound(ts);

这应该完全符合您对一次对数搜索的要求。

Answer 2

正如一些人所说，第一种方法没有多大意义，因为您正在对有序容器进行线性搜索。我意识到该位置应该在lastLookup附近

关于第二种方法，我认为一个简单的优化将消除第二次查找。你正在做一个record_iterator it= sliceMap_.find(ts); 另一个返回 sliceMap_.upper_bound(ts);

编辑：
尝试这样做：

record_iterator it = sliceMap_.lower_bound(ts);                                                                                                                                                                                                                                                                                                                              
return it;                                                                                                                                                                                        

我们在那里所做的是，使用 lower_bound() 来查找其键不小于 ts 的第一个元素（其中包括一个等于 upper_bound() 不做的元素）。