在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上使用迭代器是一種線性搜索。在地圖上搜索應該是對數的。

您的第二種方法也存在問題。你正在搜索兩次。

你爲什麼不只是使用

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（）不相同的元素）。