10

I have a multi set of int . C++

multiset<int>t;

I need to find the position of the first element which is greater than of equal to val. I used lower_bound for this

multiset<int>::iterator it= lower_bound(t[n].begin(), t[n].end(), val);

but can not find the the relative position from the beginning of the multi set . As The Cplusplus.com suggests using.. for vector.

// lower_bound/upper_bound example
#include <iostream>     // std::cout
#include <algorithm>    // std::lower_bound, std::upper_bound, std::sort
#include <vector>       // std::vector

int main () {
  int myints[] = {10,20,30,30,20,10,10,20};
  std::vector<int> v(myints,myints+8);           // 10 20 30 30 20 10 10 20

  std::sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30

  std::vector<int>::iterator low,up;
  low=std::lower_bound (v.begin(), v.end(), 20); //          ^
  up= std::upper_bound (v.begin(), v.end(), 20); //                   ^

  std::cout << "lower_bound at position " << (low- v.begin()) << '\n';
  std::cout << "upper_bound at position " << (up - v.begin()) << '\n';

  return 0;
}

Can I do it in multi set .. ? Another question is : Can I merge to multi set like vectors like shown bellow , v1,v2,v are vectors ?

merge(v1.begin(),v1.end(),v2.begin(),v1.end(),back_inserter(v))
1
  • You should ask your second question in... a second question.
    – D Drmmr
    Commented Jan 19, 2015 at 7:39

2 Answers 2

5

The generic way to get the distance between two iterators is to call std::distance.

auto it = std::lower_bound(t[n].begin(), t[n].end(), val);
const auto pos = std::distance(t[n].begin(), it);
1
  • 1
    Thanks D Drmmr ,it worked .. But complexity is linear... ? This may be give me TLE ... Again Do you know how to merge to multi set ? Commented Jan 18, 2015 at 12:56
3

For std::multiset, member types iterator and const_iterator are bidirectional iterator types. Bidirectional iterator does not support arithmetic operators + and - (for details check cppreference).

std::distance can be used to calculate the number of elements between two iterators.

std::distance uses operator- to calculate the number of elements if parameter is a random-access iterator. Otherwise, it uses the increase operator (operator++) repeatedly.

Here is a slightly changed code snippet from cppreference.

#include <iostream>
#include <set>

int main ()
{
  std::multiset<int> mymultiset;
  std::multiset<int>::iterator itlow, itup;

  for (int i = 1; i < 8; i++) mymultiset.insert(i * 10); // 10 20 30 40 50 60 70

  itlow = mymultiset.lower_bound(30);
  itup = mymultiset.upper_bound(40);

  std::cout << std::distance(mymultiset.begin(), itlow) << std::endl;
  std::cout << std::distance(mymultiset.begin(), itup) << std::endl;

  mymultiset.erase(itlow, itup); // 10 20 50 60 70

  std::cout << "mymultiset contains: ";
  for (std::multiset<int>::iterator it = mymultiset.begin(); it != mymultiset.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

Output

2
4
mymultiset contains:  10 20 50 60 70

You can merge the std::multiset with std::multiset::insert member function as following;

#include <iostream>
#include <set>

int main ()
{
  std::multiset<int> mset1;
  std::multiset<int> mset2;

  for (int i = 1; i < 8; i++) mset1.insert(i * 10); // 10 20 30 40 50 60 70
  for (int i = 1; i < 8; i++) mset2.insert(i * 10); // 10 20 30 40 50 60 70

  mset1.insert(mset2.begin(), mset2.end());

  std::cout << "mset1 contains: ";
  for (std::multiset<int>::iterator it = mset1.begin(); it != mset1.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

Output

mset1 contains:  10 10 20 20 30 30 40 40 50 50 60 60 70 70
2
  • 4
    Can we do it in constant time ? distance take linear time ! Commented Jan 18, 2015 at 14:28
  • @Matrix.code, constant time only for random-access iterators, it is not possible with std::multiset. I don't know the details but depending to your requirements, it could be possible to implement your own data structure.
    – Alper
    Commented Jan 18, 2015 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.