key-value data structure to search key in O(1) and get Max value in O(1)

Question

I need to implement a key-value data structure that search for a unique key in O(lgn) or O(1) AND get max value in O(1). I am thinking about

boost::bimap< unordered_set_of<key> ,multiset_of<value> >

Note that there is no duplicated key in my key-value data sets. However, two keys may have the same value. Therefore I used multiset to store values.

I need to insert/remove/update key-value pair frequently

How does it sounds ?

Answer 1

It depends on what you want to do. So it is clear that you want to use it for some get-the-maximum-values-in-an-iteration construction.

Question 1: Do you access the elements by their keys as well?

• If yes, I can think of two solutions for you:

  1. use boost::bimap - easy, tested solution with logarithmic runtimes.

  2. create a custom container that contains an std::map (or for even faster by key access std::unordered_map) and a heap implementation (e.g. std::priority_queue<std::map<key, value>::iterator> + custom comparator) as well, keeps them in sync, etc. This is the hard way, but maybe faster. Most operations on both will be O(logn) (insert, get&pop max, get by key, remove) but the constant sometimes do matter. Although is you use std::unordered_map the access by key operation will be O(1).

     You may want to write tests for the new container as well and optimize it for the operation you use the most.

• If no, you really just access using elements using the maximum value

  Question 2: do you insert/remove/update elements randomly or you first put in all elements in one round and then remove them one by one?

  • for random insert/remove/updates use std::priority_queue<std::pair<value, key>>

  • if you put in the elements first, and then remove them one-by-one, use and std::vector<std::pair<value, key>> and std::sort() it before the first remove operation. Do not actually remove the elements, just iterate on them.

Answer 2

You could build this using a std::map and a std::set.

1. One map to hold the actual values, i.e. std::map<key, value> m;. This is where your values are stored. Inserting elements into a map is O(log n).

2. A set of iterators pointing into the map; this set is sorted by the value of the respective 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;
       }
   };
   

   You can then get an iterator to the map entry with the largest value using *s.begin();.

This is rather easy to build, but you have to make sure to update both containers whenever you add/remove elements.