How to get a data structure having the features both circular buffer in the boost and unordered_map in the STL?

A series of data need to be added to my program. That data can be processed many times,so there is a counting number association with each data. If the counting number is greater that a fixed value, my program will do something.

I guess this data structure should have o(1) complexity, since I need to search the counting number. And I want to make the data structure bounded in case of the out of memory, since the number of data is unknown. It is fine that the new value overwrite the old value.

My question is if there has been an existed library that has such similar data structure? If the answer is no, my concern is what is the best way to achievement it? How to make it thread safe?

I know that there has been an circular buffer in the boost and unordered_map in STL. It seems like the data structure I want is the combination of them.