C++ タイムスタンプを保持しておくようなハッシュテーブルの実装

Question

実現したいこと

key が string 、 value が int のハッシュテーブルを作成したいのですが、
このタイムテーブルにそれぞれのkey値が最後に参照された(ヒットした)タイムスタンプも保持しておきたいです。
どのような実装が考えられますか？
現在は c++ の std::unordered_map を使おうと考えていますが、
あまりうまく行っていません。

動作環境

Linux (Ubuntu 19.04)
C++

補足

後々は、それぞれのタイムスタンプを監視して、古いものはキャッシュから取り除くような機能も実装したいです。

Comments

[t_obara]

同じキーでアクセス時のタイムスタンプを値として格納するテーブルを用意してチェックするか、既存のテーブルの値に既存の値とは別にタイムスタンプも格納するようにするかでしょうか。

[gogono_koucha]

「同じキーでアクセス時のタイムスタンプを値として格納するテーブルを用意してチェックするか」
やはりこれが標準な方法のようなので、このように実装してみます。

「既存のテーブルの値に既存の値とは別にタイムスタンプも格納するようにするか」について質問があるのですが、これは、unordered_mapで可能ですか？

Answer 1

普通にやるのなら、unorderdmap(string, value)とmap(timestamp, string) の2つのコンテナを使う、でしょうか
ちょっと設計としては使いづらく、自分でラッパーを書いていくことになりそうです。

ただ、今回の案件に最も向いている、boostにmulti_index_containor というものがあります。
https://boostjp.github.io/tips/multi_index.html

・stringは順番に並ばなくていいので、unordered として格納
・timestampは順番に並んでほしいので、ordered として格納
・orderedから削除した場合でもunordered側からも消え、整合性が保たれる

問題は、記述方法がかなりややこしく、
unordered_map で躓いているレベルでは厳しいかもしれません。
調べて、使えそうなら使ってみてください。

Comments

[gogono_koucha]

前者についての質問です。
unorderedmap(string, value)
で例えば string a などがヒットしたときに、
map(timestamp, string)
の string a で検索をかけて timestamp を参照するって感じになるのでしょうか。

multi_index_containor について教えていただきありがとうございます。
調べてみます。

[izmktr]

そうですね、杜撰な設計でした
valueの部分を(value, timestamp)のクラスにしないとまずいですね
結局、keyの部分が二重管理になるので、mapではなく比較演算子を指定したsetをつかうべきなんでしょうね
そのへんを考慮していくとmulti_index_containor の再発明になるので、これを使うのが順当かと思います