Hi

// Previously posted by myself on microsoft.public.vc.stl as a variant

Say I have vector<int>, it is sorted, there maybe duplicates and
I wish to find the range [begin, end) of int 75.

I can do

vector<int>    v;
pair<vector<int>::iterator, vector<int>::iterator> range;
vector<int>::iterator it1, it2;

// populate vector here

range = equal_range(v.begin(), v.end(), 75);

and now the iterator range [range.first, range.second) is a STL range to any
instances of 75.
So far, so good.

But now suppose I wish to find the range [51, 100). Now what?
It seems I can only do this in 2 steps:

it1 = lower_bound(v.begin(), v.end(), 51);
it2 = upper_bound(v.begin(), v.end(), 100);

I can't do this using equal_range(), or can I?

It is a shame there is not

range = equal_range(v.begin(), v.end(), object1, object2);
range = equal_range(v.begin(), v.end(), object1, object2, predicate());

as part of the library where as a precondition, either
object1 < object2
or
!predicate(object2, object1)
is true.

Thanks

Stephen Howe




      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

Stephen Howe wrote:
>Say I have vector<int>, it is sorted, there maybe duplicates and
>I wish to find the range [begin, end) of int 75.
>
>I can do
....
>
>range = equal_range(v.begin(), v.end(), 75);
>
>and now the iterator range [range.first, range.second) is a STL range to any
>instances of 75.
>So far, so good.
>
>But now suppose I wish to find the range [51, 100). Now what?

You can define a predicate that compares to a range instead of a
specific value.

class range_pred {
	typedef std::pair<int, int> data;
public:
	bool operator()(data d, int val) const
	{
		return val < d.first || val > d.second;
	}
	
	bool operator()(int val, data d) const
	{
		return (*this)(d, val);
	}
};

// and use it this way
range = equal_range(v.begin(), v.end(), 
					std::make_pair(51, 100), range_pred());

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

Stephen Howe wrote:
> <snip>
>
> But now suppose I wish to find the range [51, 100). Now what?
> It seems I can only do this in 2 steps:
> 
> it1 = lower_bound(v.begin(), v.end(), 51);
> it2 = upper_bound(v.begin(), v.end(), 100);
> 
> I can't do this using equal_range(), or can I?
> 

You can do it be writing your own predicate, basically write it so that 
it treats all numbers in the range [51,100) as equal.

something like (note: I haven't tried compiling this.. sorry!)
template<int lower, int upper>
struct range_predicate {
bool operator()(int i,int j) {
if(lower<=i && i<upper && lower<=j && j<upper) return false;
return i<j;
}
};

then do
range = equal_range(v.begin, v.end(), range_predicate<50,100>());

Although I will admit this isn't as nice as it could be...

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

Stephen Howe wrote:
> Hi
....
> range = equal_range(v.begin(), v.end(), 75);
>
> and now the iterator range [range.first, range.second) is a STL range
to any
> instances of 75. So far, so good.
>
> But now suppose I wish to find the range [51, 100). Now what?
> It seems I can only do this in 2 steps:
>
> it1 = lower_bound(v.begin(), v.end(), 51);
> it2 = upper_bound(v.begin(), v.end(), 100);
>
> I can't do this using equal_range(), or can I?

No, and it seems rather obvious to me. 51 is not equal to 100, and
*it1 is not equal to *it2.

BTW, try
it1 = lower_bound(v.begin(), v.end(), 51);
it2 = upper_bound(it1, v.end(), 100);

No need to search for the value 100 in the range [v.begin(), it1]
HTH,
Michiel Salters


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

"Stephen Howe" <sjhoweATdialDOTpipexDOTcom@eu.uu.net> wrote in message 
news:41f7170a$0$311$cc9e4d1f@news.dial.pipex.com...

> It is a shame there is not
>
> range = equal_range(v.begin(), v.end(), object1, object2);
> range = equal_range(v.begin(), v.end(), object1, object2, predicate());
>
> as part of the library where as a precondition, either
> object1 < object2
> or
> !predicate(object2, object1)
> is true.

Why?  Is that really such a common operation?  Is it so difficult to write

    it1 = lower_bound(v.begin(), v.end(), object1);
    it2 = upper_bound(it1, v.end(), object2);

?

If there were a form of equal_range that took two objects, would you also 
want one that took three?


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

> If there were a form of equal_range that took two objects, would you also
> want one that took three?

No. It is the fact that 2 objects searched for would be the limits of an stl
range. What would it mean with 3 objects?
But I guess this is non-standard as no other algorithm takes a pair of
objects.

The other reason for asking is the the complexity requirements for such an
equal_range() might be lower than lower_bound() combined with upper_bound().
I have not sat and analysed this yet.

Stephen Howe



      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On 26 Jan 2005 04:52:21 -0500, "Stephen Howe"
<sjhoweATdialDOTpipexDOTcom@eu.uu.net> wrote:

> Say I have vector<int>, it is sorted, there maybe duplicates and

> But now suppose I wish to find the range [51, 100). Now what?
> It seems I can only do this in 2 steps:

> it1 = lower_bound(v.begin(), v.end(), 51);
> it2 = upper_bound(v.begin(), v.end(), 100);

This gives you [51, 100].  If you really want [51, 100) you need
lower_bound for the second also.

> I can't do this using equal_range(), or can I?

Yes you can.  It needs a predicate and careful use.  I assume a
range of the form [,).

template <class T>
struct Comp {
     T b, e;
     Comp (T b, T e) : b(b), e(e) {
         assert(b <= e);
         }
     bool operator() (T lhs, T rhs) {
         return lhs == b ? ! (rhs < e) : lhs < b;
         }
     };

std::equal_range(v.begin(), v.end(), 51, Comp<int>(51, 100));

Why not just write the algorithm you want?

template <class I, class T>
std::pair<I, I> equal_range(I first, I past, T b, T e) {
     I f(std::lower_bound(first, past, b));
     return std::pair<I, I>(f, std::lower_bound(f, past, e));
     }

It does seem to be less complicated.

If you really think the combined search of std::equal_range
will be significantly better, you could just code it with
the Comp.

template <class I, class T>
std::pair<I, I> equal_range(I first, I past, T b, T e) {
     return std::equal_range(first, past, b, Comp<T>(b, e));
     }

John

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

> BTW, try
> it1 = lower_bound(v.begin(), v.end(), 51);
> it2 = upper_bound(it1, v.end(), 100);

Yes. That occured to me after I posted.
It reduces the compares.

Thanks

Stephen Howe




      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

"Andrew Koenig" <ark@acm.org> writes:

> "Stephen Howe" <sjhoweATdialDOTpipexDOTcom@eu.uu.net> wrote in message
> news:41f7170a$0$311$cc9e4d1f@news.dial.pipex.com...
>
>> It is a shame there is not
>>
>> range = equal_range(v.begin(), v.end(), object1, object2);
>> range = equal_range(v.begin(), v.end(), object1, object2, predicate());
>>
>> as part of the library where as a precondition, either
>> object1 < object2
>> or
>> !predicate(object2, object1)
>> is true.
>
> Why?  Is that really such a common operation?  Is it so difficult to write
>
>     it1 = lower_bound(v.begin(), v.end(), object1);
>     it2 = upper_bound(it1, v.end(), object2);
>
> ?
>
> If there were a form of equal_range that took two objects, would you also
> want one that took three?

I'm not sure what that would mean, but the semantics of the two-object
case are achievable now that we've made heterogeneous comparison
operators legal with equal_range et. al.

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On 26 Jan 2005 13:59:15 -0500, Motti Lanzkron <mlanzkron@yahoo.co.uk>
wrote:

> Stephen Howe wrote:

> >But now suppose I wish to find the range [51, 100). Now what?

> You can define a predicate that compares to a range instead of a
> specific value.

> class range_pred {
>       typedef std::pair<int, int> data;
> public:
>       bool operator()(data d, int val) const
>       {
>               return val < d.first || val > d.second;
>       }
>
>       bool operator()(int val, data d) const
>       {
>               return (*this)(d, val);
>       }
> };

> // and use it this way
> range = equal_range(v.begin(), v.end(),
>                                       std::make_pair(51, 100), range_pred());

Not bad, but try compiling it with a fussy compiler like comeau.
Hint:

    std::vector<unsigned> v;
    std::equal_range(v.begin(), v.end(), 42);

fails.

John

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

Motti Lanzkron wrote:
> Stephen Howe wrote:
>
>>Say I have vector<int>, it is sorted, there maybe duplicates and
>>I wish to find the range [begin, end) of int 75.
>>
>>I can do
>
> ....
>
>>range = equal_range(v.begin(), v.end(), 75);
>>
>>and now the iterator range [range.first, range.second) is a STL range to any
>>instances of 75.
>>So far, so good.
>>
>>But now suppose I wish to find the range [51, 100). Now what?
>
>
> You can define a predicate that compares to a range instead of a
> specific value.
>
> class range_pred {
>       typedef std::pair<int, int> data;
> public:
>       bool operator()(data d, int val) const
>       {
>               return val < d.first || val > d.second;
>       }
>
>       bool operator()(int val, data d) const
>       {
>               return (*this)(d, val);
>       }
> };
>
> // and use it this way
> range = equal_range(v.begin(), v.end(),
>                     std::make_pair(51, 100), range_pred());

Shouldn't that be:

class range_pred {
        typedef std::pair<int, int> data;
public:
        bool operator()(data d, int val) const
        {
                return val > d.second;
        }

        bool operator()(int val, data d) const
        {
                return val < d.first;
        }
};

After all, the predicate is testing less-than, not containment.

While I consider this to be the best solution, I do not see how it is
portable.  equal_range requires the container to be considered sorted
with the predicate specified, and this predicate can not be applied to
the container!

   -- MJF

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

I would consider std::subrange(It1,It2,lower,upper) much less esoteric
than, say, random_shuffle, even though I agree that it is not so
terrible to have to do it in two statements.

Cheers,
Nicola Musatti


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

John Potter wrote:
>
>Not bad, but try compiling it with a fussy compiler like comeau.
>Hint:
>
>    std::vector<unsigned> v;
>    std::equal_range(v.begin(), v.end(), 42);
>
>fails.

I'm looking at the standard now and I see: 

template<class ForwardIterator, class T>
pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator, ForwardIterator, const T&);

Where does it require that T be the same type as *ForwardIterator ?

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

>> it1 = lower_bound(v.begin(), v.end(), 51);
>> it2 = upper_bound(v.begin(), v.end(), 100);
>
> This gives you [51, 100].  If you really want [51, 100) you need
> lower_bound for the second also.

Thanks John. The code is right, my maths notation is wrong. I should have
[51, 100+1). But I guess on thinking that the 2nd object should be 
non-inclusive limit so that it matches the general form of ranges in the 
library.

Stephen Howe 



      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

John Potter <jpotter@lhup.edu> writes:

> Not bad, but try compiling it with a fussy compiler like comeau.
> Hint:
>
>     std::vector<unsigned> v;
>     std::equal_range(v.begin(), v.end(), 42);
>
> fails.

But Comeau is now officially "too fussy."
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#270

--
Dave Abrahams
Boost Consulting
www.boost-consulting.com

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On 27 Jan 2005 16:30:46 -0500, David Abrahams
<dave@boost-consulting.com> wrote:

> John Potter <jpotter@lhup.edu> writes:

> > Not bad, but try compiling it with a fussy compiler like comeau.
> > Hint:
> >
> >     std::vector<unsigned> v;
> >     std::equal_range(v.begin(), v.end(), 42);

> > fails.

> But Comeau is now officially "too fussy."
> http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#270

Status WP.  Comeau will be "too fussy" when and if the WP becomes
a standard with those words still intact.  I wish I could file a
bug report on Comeau today.

John

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On 27 Jan 2005 15:56:05 -0500, Motti Lanzkron <mlanzkron@yahoo.co.uk>
wrote:

> John Potter wrote:

> >Not bad, but try compiling it with a fussy compiler like comeau.
> >Hint:

> >    std::vector<unsigned> v;
> >    std::equal_range(v.begin(), v.end(), 42);

> >fails.

> I'm looking at the standard now and I see: 

> template<class ForwardIterator, class T>
> pair<ForwardIterator, ForwardIterator>
> equal_range(ForwardIterator, ForwardIterator, const T&);

> Where does it require that T be the same type as *ForwardIterator ?

It seems to be indicated in 25.3.3/1.  Some think that the following
is a valid implementation.

template <class T>
struct __less {
   bool operator() (T const& lhs, T const& rhs) {
      return lhs < rhs;
      }
   };
template <class FI, class T>
pair<FI, FI> equal_range (FI f, FI p, T const& v) {
   return equal_range(f, p, v, __less<T>());
   }

Some also think that had things been better understood, it would
have been

template <class FI>
pair<FI, FI> equal_range(FI, FI, typename
      iterator_traits<FI>::value_type const&);

That, of course is all history.  The only important question today
is whether you want your code to compile today on fussy compilers.

John

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

Stephen Howe wrote:

>>> it1 = lower_bound(v.begin(), v.end(), 51);
>>> it2 = upper_bound(v.begin(), v.end(), 100);
>>
>> This gives you [51, 100].  If you really want [51, 100) you
>> need lower_bound for the second also.
> 
> Thanks John. The code is right, my maths notation is wrong. I
> should have [51, 100+1). But I guess on thinking that the 2nd
> object should be non-inclusive limit so that it matches the
> general form of ranges in the library.

Past-the-end iterators are supposed always to exist, but what is past 
the end of int's range?

-- 
Quidquid latine dictum sit, altum viditur.

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On 28 Jan 2005 23:55:25 -0500, Martin Eisenberg
<martin.eisenberg@udo.edu> wrote:

> Stephen Howe wrote:

> >>> it1 = lower_bound(v.begin(), v.end(), 51);
> >>> it2 = upper_bound(v.begin(), v.end(), 100);

> >> This gives you [51, 100].  If you really want [51, 100) you
> >> need lower_bound for the second also.

> > Thanks John. The code is right, my maths notation is wrong. I
> > should have [51, 100+1). But I guess on thinking that the 2nd
> > object should be non-inclusive limit so that it matches the
> > general form of ranges in the library.

> Past-the-end iterators are supposed always to exist, but what is past 
> the end of int's range?

The choice is either to pick one or use [,] preventing an empty range.
A very old problem for full range of anything.  do-while for complete
range of any integral type prevents zero executions.  You can't have
both.

John

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

John Potter wrote:

> On 28 Jan 2005 23:55:25 -0500, Martin Eisenberg
> <martin.eisenberg@udo.edu> wrote:

>> Past-the-end iterators are supposed always to exist, but what
>> is past the end of int's range?
> 
> The choice is either to pick one or use [,] preventing an empty
> range. A very old problem for full range of anything.  do-while
> for complete range of any integral type prevents zero
> executions.  You can't have both.

What about the mathematical convention that sum_{i=m}^n a_i = 0
for m > n? The programming analog would break down for a type with 
just one value, oh well. (I acknowledge that there is another 
convention making the sum zero only for m = n + 1.)

-- 
Quidquid latine dictum sit, altum viditur.

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]