c++ - 地图中最接近的字符串/时间戳

Question

如果时间戳不在存储时间戳的地图中，我想在地图中找到最接近的匹配时间戳并使用最接近的值作为键。我有我正在尝试做的基本结构设置我只是不确定如何找到最近的时间戳

typedef std::map<std::string,int>  Map;
Map::iterator it;
Map my_map;

my_map["2010-01-26 17:02:12"]= 1;
my_map["2010-01-25 08:55:29"]= 2;
my_map["2010-01-24 08:55:29"]= 3;

string timestamp = "2010-01-24 08:55:30"; // would return 3
string timestamp1 = "2010-01-27 01:55:30"; // would return 1

  it = my_map.find(timestamp); 
     if(it == my_map.end()){
       //not sure how to approach this
   }    

更新

我试图避免将相当大的代码库从 转换std::string为uint64_t尽管它会提高性能，但这并不是什么大问题，

我无法在这里工作的std::map::lower_bound解决std::map::upper_bound方案是我在 IDE ONE 上的尝试，

http://ideone.com/MnRLIH

Answer 1

std::map::lower_bound您可能可以使用or获得您需要的东西std::map::upper_bound，其中任何一个都是O(log N)复杂度。

---

此外，强烈考虑将时间戳存储为 auint64_t而不是字符串。这将大大减少比较和处理的计算量。

Answer 2

我相信有upper_bound()和lower_bound()功能，你可以用它来找到上面和下面的邻居。