Поиск индекса мультисети

Question

У меня есть мульти набор Int . C++

multiset<int>t;

Мне нужно найти положение первого элемента, который больше, чем равен val. Я использовал lower_bound для этого

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

но не могу найти относительную позицию с начала множества. Как Cplusplus.com предлагает использовать.. для вектора.

// 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;
}

Могу ли я сделать это в нескольких наборах..? Другой вопрос: могу ли я слить с множеством, как векторы, как показано ниже, v1,v2,v являются векторами?

merge(v1.begin(),v1.end(),v2.begin(),v1.end(),back_inserter(v))

Answer 1

Общий способ получить расстояние между двумя итераторами - вызвать std:: distance.

auto it = std::lower_bound(t[n].begin(), t[n].end(), val);
const auto pos = std::distance(t[n].begin(), it);

Answer 2

За std::multiset, типы членов iterator а также const_iterator являются двунаправленными типами итераторов. Двунаправленный итератор не поддерживает арифметические операторы + и - (подробнее см. Cppreference).

std::distance может использоваться для вычисления количества элементов между двумя итераторами.

std::distance использования operator- рассчитать количество элементов, если параметр является итератором с произвольным доступом. В противном случае он многократно использует оператор увеличения (operator++).

Вот слегка измененный фрагмент кода из 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;
}

Выход

2
4
mymultiset contains:  10 20 50 60 70

Вы можете объединить std::multiset с std::multiset::insert функция-член следующим образом;

#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;
}

Выход

mset1 contains:  10 10 20 20 30 30 40 40 50 50 60 60 70 70