CODEWITHSUNDEEP
c++setcontainersstd
user8469759
user8469759

Reputation: 2732

How Can I get a range of values in a map for given lower bound and upper bound in an std::set?

Say I have the following code

#include <iostream>
#include <set>

int main ()
{
  std::set<int> myset;
  int inf, sup;

  inf = 25; sup = 60;
  for (int i=1; i<10; i++) myset.insert(i*10); // 10 20 30 40 50 60 70 80 90

  return 0;
}

I was trying to figure out if the standard library provides any methods, or combination of methods that would allow me to get two iterators it_l, it_u such that the range [inf,sup] is covered. I've tried to use lower_bound, upper_bound but I've misunderstood how they works. The idea would be avoiding to write loops (because I know I could write my own function for this task, but maybe there's some alternative I'm not aware of).

Update : Some examples of expected output would be (in my example)

inf =25; sup = 60 I expect {30,40,50,60}

if instead

inf=30; sup = 60 I expect {30,40,50,60}

if

inf=25; sup = 65 I expect {30,40,50,60}

Apparently there's a misunderstanding, or maybe it's me I'm not correctly expressing what I want to do.

When I say inf and sup please intend them as extreme values of a real interval. Once you made such assumption what I want is to retrieve is the intersection between the interval [inf,sup] and the discrete set specified by an set objects. Is there some contradiction between what I just said and my examples?

Let A={10 20 30 40 50 60 70 80 90},B1=[25,60],B2=[30,60] and B3=[25,65]

For each i=1,2,3 The intersection between A and Bi gives exactly what I've said in my examples.

Upvotes: 5

Views: 2528

Answers (4)

mindriot
mindriot

Reputation: 5668

This works fine for me:

#include <iostream>
#include <set>

template <typename T>
std::pair<typename std::set<T>::const_iterator, typename std::set<T>::const_iterator>
infsup(const std::set<T>& set, const T& inf, const T& sup)
{
  return std::make_pair(set.lower_bound(inf), set.upper_bound(sup));
}

int main ()
{
  std::set<int> myset;
  int inf, sup;

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

  for (auto its = infsup(myset, 30, 60); its.first != its.second; ++its.first)
  {
    std::cout << " " << *its.first; // 30 40 50 60
  }
  std::cout << std::endl;

  for (auto its = infsup(myset, 25, 65); its.first != its.second; ++its.first)
  {
    std::cout << " " << *its.first; // 30 40 50 60
  }
  std::cout << std::endl;

  return 0;
}

Using lower_bound for inf means that the start iterator will point to the first element that is not less than inf, and so fulfills the condition you want for the lower end of the range.

Using upper_bound for sup means that the end iterator will point to _ first element that is greater than sup_. Note that the end iterator, in C++, always points just past the end of your range, so therefore sup will be included.

Edit to reflect the discussion in the comments (thanks to @Useless for pointing it out): Note that this works fine for empty result ranges, e.g.

  • when both inf and sup are less than the smallest element in the set
  • when both are greater than the greatest element
  • when there are no elements within [inf, sup] (in your example, say inf=25, sup=29)

But if you pick inf > sup so that the returned iterators refer to different elements, then its.first > its.second, which would make the for loops (as I wrote them above) fail. So it is up to you to ensure that inf <= sup (just like for any other for loop you might be writing).

Upvotes: 4

Angew is no longer proud of SO
Angew is no longer proud of SO

Reputation: 171127

It seems you just want this:

auto it_l = myset.lower_bound(inf);
auto it_u = myset.lower_bound(sup + 1);

This way, you'll get the half-open interval [it_l, it_u) such that all elements i in it come from myset and are inf <= i <= sup (i.e. precisely what you want). Half-open iterator intervals are what the entire standard library works with, so you should be fine.

Upvotes: 1

n. m. could be an AI
n. m. could be an AI

Reputation: 119877

C++ works with half-open ranges. That is, [inf, sup), never [inf, sup]. The half-open-range idiom is well supported by the standard library: just use std::set::lower_bound and std::set::upper_bound. (Not std::upper bound etc). The closed-range one is not, you are on your own if you insist on using it. I would recommend adopting the standard ways and switching to half-open ranges everywhere.

Upvotes: 0

ROX
ROX

Reputation: 1266

Its not clear why you say upper and lower bound don't do what you want.

lower_bound will return an iterator pointing to the first element you are trying to find (the first element that is not less than the argument)

upper_bound gives you the first element greater than the argument (so 70 in your example) but that's how stl iterators work, end points to one-beyond-the-last-element.

These 2 iterators can be used to make a copy of the elements if you really want a copy - but you can also just use them to access the elements of the original collection - and that range would include 60 but not 70 in your example.

Upvotes: 0

Related Questions