Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Multiset Index Finding

Tags:

c++

multiset

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))
like image 932
Matrix.code Avatar asked Jan 18 '15 11:01

Matrix.code


People also ask

How do you find the index of an element in a multiset?

The multiset::find() is a built-in function in C++ STL which returns an iterator pointing to the lower_bound of the element which is searched in the multiset container. If the element is not found, then the iterator points to the position past the last element in the set.

How do I search in multiset?

C++ multiset find() C++ multiset find() function is used to find an element with the given value val. If it finds the element, then it returns an iterator pointing to the element otherwise, it returns an iterator pointing to the end of the multiset i.e. multiset::end().


2 Answers

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);
like image 148
D Drmmr Avatar answered Oct 16 '22 11:10

D Drmmr


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
like image 31
Alper Avatar answered Oct 16 '22 11:10

Alper