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?

+3


source to share


2 answers


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 keys std::unordered_map

      ) as well as a heap implementation (like std::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 using std::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>>

      and std::sort()

      before the first delete operation. Don't actually remove the elements, just repeat them.

+2


source


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.

+1


source







All Articles