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之后和之前

回答

相关问题