lower_bound和upper_bound之後和之前

我想在事件數據庫中搜索並檢查什麼是時間t之前的即時事件，以及什麼是時間t之後的直接事件。如果事件發生在t時間，我希望前後兩者相等。如果給定時間在所有數據庫事件之前或之後，那麼必須在前後都給出最極端的事件。下面是代碼：lower_bound和upper_bound之後和之前

// g++ -std=c++11 test2.cpp -Wfatal-errors 

#include <iostream> 
#include <string> 
#include <vector> 
#include <algorithm> 

struct Event 
{ 
    double event_time; 
    std::string info; 

}; 

bool operator< (const Event &e1,double rhs_time) 
{ 
    return e1.event_time<rhs_time; 
} 
bool operator< (double lhs_time,const Event &e2) 
{ 
    return lhs_time<e2.event_time; 
} 


int main() 
{ 
    std::vector<Event> events= 
    { 
     {0.0, "Player 1 built a village"}, 
     {2.0, "Player 2 relocated"}, 
     {2.5, "Player 2 attacked plyer 3"}, 
     {4.0, "Player 4 built walls"}, 
     {6.0, "Player 3 left the game"}, 
     {7.0, "Player 2 built a village"}, 
    }; 
    std::vector<Event>::iterator before,after; 
    double search_time=4.5; 
    before=std::lower_bound (events.begin(), events.end(), search_time); 
    after= std::upper_bound (events.begin(), events.end(), search_time); 
    std::cout<<"What happened before and after "<<search_time<<"?"<<std::endl; 
    std::cout 
      <<"before: @"<<(before->event_time) 
      <<", "<<(before->info)<<std::endl; 
    std::cout 
      <<"after: @"<<(after->event_time) 
      <<", "<<(after->info)<<std::endl; 

    return 0; 
}

，其結果是

What happened before and after 4.5? 
before: @6, Player 3 left the game 
after: @6, Player 3 left the game

雖然我期待：

What happened before and after 4.5? 
before: @4, Player 4 built walls 
after: @6, Player 3 left the game

矢量進行排序。

我該如何解決這個問題？

（wandbox）

來源

2017-09-13 ar2015

使用浮點數作爲索引時要小心，您可能會遇到浮點不準確的問題。你在這裏發佈的每個以.0或.5結尾的數字的例子都不會有這個問題，但是這很容易改變。 –

@MarkRansom，謝謝你提到這一點。我完全意識到這一點。這是一個MWE。在實踐中，我將使用數據結構而不是文本信息，並使用插值。因此，我並不擔心這一點。 – ar2015

lower_bound將返回大於或等於搜索項的第一個元素。在這種情況下，元素爲6.0。

upper_bound將返回更大的第一個元素，但是不是等於搜索項目。在這種情況下，也是元素6.0。

要獲取要搜索的數字之前的元素，您需要明確遞減從lower_bound返回的迭代器。爲了防止未定義的行爲，您首先需要確定它尚未在begin()。

認爲lower_bound和upper_bound返回的範圍該項目將被放置在排序的數組中。如果搜索項不在序列中出現，它們將始終返回相同的迭代器。

來源

2017-09-13 02:43:26

非常感謝。我修正了[code]（https://wandbox.org/permlink/yLyEEfDWjqLCAuXS）。這段代碼是否保證在一個有序數據庫上總是'after = before'或'after = before + 1'？ – ar2015

@ ar2015如果序列中沒有重複項，它會執行。否則，你會得到'after = before + n'，其中'n'是重複的次數。 –

lower_bound和upper_bound之後和之前

回答

相關問題