3

I have a multiset, implemented as follows:

#include <bits/stdc++.h>
using namespace std;

multiset <int> M;

int numunder(int k){
    /*this function must return the number of elements smaller than or equal to k
    in M (taking multiplicity into account).
    */
}

At first I thought I could just return M.upper_bound(k)-M.begin()+1. Unfortunately it seems we cannot subtract pointers like that. We ended up having to implement an AVLNodes structure. Is there a way to get this to work taking advantage of the c++ std?

3 Answers3

5

Sticking closely to your proposed M.upper_bound(k)-M.begin()+1 solution (which clearly does not compile, because the multimap iterator is a bidirectional iterator that does not implement operator-), you could use std::distance to get the distance between two multimap iterators to have a correct solution.

Note that this solution will have O(n) complexity, because if the iterator is not a random access iterator, std::distance will just increment the iterator passed in as first parameter, until it finds the iterator passed in as second argument.

I also don't really think that this problem can be solved in better than O(n) complexity with std::multiset.

Csq
  • 5,775
  • 6
  • 26
  • 39
  • Oh wow, that is really nice! Thank you very much. Do you know the complexity? –  Apr 15 '16 at 21:17
  • The complexity is O(n), I will add it to the answer. – Csq Apr 15 '16 at 21:18
  • Oh, ok, thanks. We needed it to be log(n) for our contest, but it is good to know. With the AVLNode we can get it to be logarithmic. :) If you think it is possible to solve this without having to implement a lot of data structures I would really appreciate it, I'm accepting either way. –  Apr 15 '16 at 21:23
  • Yes, if add the number of children attribute to the nodes in the AVL tree that could be logarithmic. – Csq Apr 15 '16 at 21:28
  • 1
    For the broader question you can also look at: https://stackoverflow.com/questions/17428841/get-number-of-elements-greater-than-a-number – Csq Apr 15 '16 at 21:28
1

This can be solved using some policy based data structures avaliable in gcc . You can use the red black tree with information statistics, here is a discussion

0

Gcc implements multisets as red-black trees. In a binary tree there is no non-trivial way to get the "sorted index" of a node without storing extra info in the node, such as the number of children.

Also know that iterating through the iterators returned by find, upper_bound, etc. will walk the tree, because the iterators are not random access. See https://en.cppreference.com/w/cpp/container/multiset

If you want to only use built-in data structures you could maintain a separate vector that you can perform binary search on. This is more organizational work but if you are only inserting or erasing then it is pretty simple. Anything more complicated probably warrants its own data structure.

qwr
  • 9,525
  • 5
  • 58
  • 102
  • Hello there, thanks for the answer. It turns out we can use the following policy based structure to solve it, and it is the method used in programming contests: https://codeforces.com/blog/entry/11080 . Thank you very much though ! –  Mar 13 '20 at 17:52
  • 1
    I have seen that blog post and to be honest I don't do contest problems hard enough to require those (yet). – qwr Mar 14 '20 at 01:50