在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

第一种方法有三个大问题:

• 循环内的比较太多了.
• 使用迭代器std::map涉及使用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);

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