Key value to find the key in O (1) and get the maximum value in O (1)
I need to implement a key value data structure that looks for a unique key in O (lgn) or O (1) and gets a max value in O (<1). I think about
boost::bimap< unordered_set_of<key> ,multiset_of<value> >
Please note that there is no duplicate key in my key datasets. However, two keys can have the same meaning. So I used a multiset to store the values.
I need to frequently insert / delete / update key-value pairs
How does this sound?
source to share
It depends on what you want to do. So it is clear that you want to use it to build get-the-maximum-values-in-and-iteration.
Question 1: Are the items accessed using their keys ?
-
If so , I can think of two solutions for you:
-
use
boost::bimap
is a simple, proven solution with logarithmic runtime. -
create a custom container containing
std::map
(or even faster access to keysstd::unordered_map
) as well as a heap implementation (likestd::priority_queue<std::map<key, value>::iterator>
+ own comparator), sync them, etc. This is the hard way, but perhaps faster. Most operations on both will be O (logn) (insert, get & pop max, get by key, remove), but constant sometimes matters. Although you are usingstd::unordered_map
, the key access operation will be O (1).You might also want to write tests for the new container and optimize it to work best.
-
-
If not , you are really just using max-value elements
Question 2: do you randomly insert / remove / update items or do you insert all items in one round first and then remove them one by one?
-
for random input / delete / update use
std::priority_queue<std::pair<value, key>>
-
if you insert elements first and then delete them one by one, use and
std::vector<std::pair<value, key>>
andstd::sort()
before the first delete operation. Don't actually remove the elements, just repeat them.
-
source to share
You can create this with std::map
and std::set
.
-
One card for storing actual values, i.e.
std::map<key, value> m;
... This is where your values ββare stored. Inserting items into a map is O (log n). -
A set of iterators pointing to a map; this set is sorted by the value of the corresponding map entry, i.e.
std::set<std::map<key, value>::iterator, CompareBySecondField> s;
with something like (untested):template <class It> struct CompareBySecondField : std::binary_function<It, It, bool> { bool operator() ( const T &lhs, const T &rhs ) const { return lhs->second > rhs->second; } };
Then you can get the iterator to write the card with the highest value using
*s.begin();
.
It's pretty easy to build, but you have to update both containers whenever you add / remove items.
source to share