0

タイムスタンプがタイムスタンプと共に保存されたマップにない場合、マップで最も近い一致するタイムスタンプを見つけ、最も近い値をキーとして使用したいと思います。私がやろうとしていることの基本的な構造のセットアップがありますが、最も近いタイムスタンプを見つける方法がわかりません

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いますが、パフォーマンスは向上しますが、それほど大きな問題ではありません。

I can't get the std::map::lower_boundor std::map::upper_boundsolutions to work here は、IDE ONE での私の試みです。

http://ideone.com/MnRLIH

4

2 に答える 2

5

おそらく必要なものをstd::map::lower_boundまたはstd::map::upper_boundで取得できます。どちらもO(log N)の複雑さです。

また、タイムスタンプをuint64_t文字列ではなく、たとえば a として保存することを強く検討してください。これにより、比較および処理する計算量が大幅に削減されます。

于 2013-01-13T18:35:51.993 に答える
3

上と下の隣人を見つけるために使用できる機能があると思いますupper_bound()。lower_bound()

于 2013-01-13T18:35:35.553 に答える