hars123's blog

Needed help in multiset
By hars123, history, 6 years ago, In English

I am trying to find number of elements smaller than or equal to a particular value inside the multiset. I want a logn time approach. I have tried using distance(s.begin(),s.upper_bound(val)). But using distance method could take O(N) time in worst case.Can someone help me.

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

You can't use multiset for that. Alternative data structures are segment trees and policy based data structures. see this

→ Reply
»
6 years ago, # |
← Rev. 11   Vote: I like it 0 Vote: I do not like it

In C++, a.begin() can be subtracted from upper_bound(a.begin(),a.end(),x) to find the 0-based offset position of the first item in the sorted vector vector<T> a that is greater than x. Note that if this position is equal to a.size(), then the largest value in the vector (i.e. a.back()) is less than or equal to x. This method may be applied to solve the Game of Two Stacks problem.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But sadly, you can't do the same with sets(or Multiset).

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 5   Vote: I like it 0 Vote: I do not like it

      Yes, because the iterator subtraction binary operator - is undefined for both set and multiset data structures. Iterators of both containers are not random-access iterators. However, if this task is required for a larger number of queries, a simple way to apply the iterator-difference method is to copy the sorted set or multiset to a vector like that.

      multiset<int> a; vector<int> sorted_vector;

for(auto item:a)
    sorted_vector.push_back(item);

size_t pos = upper_bound(sorted_vector.begin(),sorted_vector.end(),x)-sorted_vector.begin();
      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        and what do you think is the complexity of copying n elements from set to vector ?

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 5   Vote: I like it 0 Vote: I do not like it

          The function call push_back may do memory reallocation, which can raise the complexity to . However, if the required vector size is allocated before the copying operation, then random-access should be constant-time and the complexity should remain as . Traversing a multi-set implemented using binary tree should be done in , check Tree Traverasls. Therefore, the complexity of the entire copying task should be . It would be helpful to run a small program to confirm or refute this hypothesis.

          UPDATE: The following experimental results confirm roughly the linear-time complexity of copying the multiset to sorted vector.

          Experiment

          → Reply
»
6 years ago, # |
← Rev. 16   Vote: I like it 0 Vote: I do not like it

The following is a suggested C++14 solution based on the AVL balanced binary tree presented in Geeksforgeeks. Note that keys in the balanced binary tree should have distinct values. A multiset is implemented by counting the number of times the same key is inserted.

https://ideone.com/Fdupoh

UPDATE: A performance comparison between AVL::multiset<int> and std::multiset<int> was performed using 2,000,000 randomly generated integer keys. A new function 

template<class OutputIterator> 
OutputIterator copy_all(OutputIterator result, bool distinct = false) const

was introduced to the container AVL::multiset<T>. Similar to the standard library function std::copy, the introduced function copies all the sorted keys from the AVL multiset to the container starting from the forward output iterator position result, and considering the case when the same key was inserted two or more times. If the input parameter distinct is passed as true, any key is copied only one time even if it was inserted two ore more times. The results of the performance comparison shown in the program output of the previous link demonstrate that the introduced function call b1.copy_all(a1.begin()) is 21 times faster than copying all the keys in the std::multiset<int> b2 object using the standard for(auto b:b2) loop. Furthermore, the results show that inserting the 2,000,000 randomly generated integer keys to b1 is about 3.21 times faster than inserting the same keys to b2.

→ Reply