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

第一种方法存在三大问题:

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

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

你为什么不直接使用

return sliceMap_.lower_bound(ts);

这应该可以通过一次对数搜索完全满足您的需求。