VC STL - equal_range problem

Author

equal_range problem

Stephen Howe

2005-02-14, 9:11 pm

Hi

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

I can do

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

// populate vector

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

and now the iterators [range.first, range.second) contains all instances of
75.
So far, so good.

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

it1 = lower_bound(v.begin(), v.end(), 75);
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);

Thanks

Stephen Howe

Igor Tandetnik

2005-02-14, 9:11 pm

"Stephen Howe" <stephenPOINThoweATtns-globalPOINTcom> wrote in message
news:eHtojWyAFHA.2640@TK2MSFTNGP14.phx.gbl
> But now suppose I wish to find the range [75, 100). Now what?
> It seems I can only do this in 2 steps:
>
> it1 = lower_bound(v.begin(), v.end(), 75);
> it2 = upper_bound(v.begin(), v.end(), 100);
>
> I can't do this using equal_range(), or can I?

You could use an overload of equal_range that takes a predicate, and
construct a comparator that treats all values between 75 and 100 as
equal. It's probably less work to just make two calls as you show.
--
With best wishes,
Igor Tandetnik

With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going to
land, and it could be dangerous sitting under them as they fly
overhead. -- RFC 1925

Stephen Howe

2005-02-14, 9:11 pm

"Igor Tandetnik" <itandetnik@mvps.org> wrote in message
news:ev60$fyAFHA.3504@TK2MSFTNGP12.phx.gbl...
> "Stephen Howe" <stephenPOINThoweATtns-globalPOINTcom> wrote in message
> news:eHtojWyAFHA.2640@TK2MSFTNGP14.phx.gbl
>
> You could use an overload of equal_range that takes a predicate, and
> construct a comparator that treats all values between 75 and 100 as equal.
> It's probably less work to just make two calls as you show.

I can slightly improve it by doing

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

Stephen Howe

Jerry Coffin

2005-02-14, 9:11 pm

In article <eHtojWyAFHA.2640@TK2MSFTNGP14.phx.gbl>, "Stephen Howe"
<stephenPOINThoweATtns-globalPOINTcom> says...

[ ... ]

> But now suppose I wish to find the range [75, 100). Now what?
> It seems I can only do this in 2 steps:
>
> it1 = lower_bound(v.begin(), v.end(), 75);
> 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);

It can be done with the other form of equal_range (the one that takes
a predicate) though the methodology isn't at all obvious:

template<class T>
class in_range {
T tolerance;
public:
in_range(T const &t) : tolerance(t) {}

bool operator()(T const &X, T const &Y) {
return (X<(Y-tolerance)) ||
(X>(Y+tolerance));
}
};

range = std::equal_range(v.begin(), v.end(), 87, in_range<int>(12));

Instead of supplying the lower and upper bounds, we have to supply
the middle of the desired range, and specify the tolerance on either
side of that as an argument when constructing our comparator.
Personally, I think I'd use lower_bound and upper_bound, or perhaps
create my own in_range algorithm to do the job.

--
Later,
Jerry.

The universe is a figment of its own imagination.

Igor Tandetnik

2005-02-14, 9:11 pm

"Stephen Howe" <stephenPOINThoweATtns-globalPOINTcom> wrote in message
news:eHtojWyAFHA.2640@TK2MSFTNGP14.phx.gbl
> But now suppose I wish to find the range [75, 100). Now what?
> It seems I can only do this in 2 steps:
>
> it1 = lower_bound(v.begin(), v.end(), 75);
> it2 = upper_bound(v.begin(), v.end(), 100);

Note that this code gives you the range [75, 100] inclusive. The last
call to upper_bound will return an iterator to 101 or higher - the first
value that is strictly greater than 100. If you indeed want [75, 100),
use lower_bound in both calls.
--
With best wishes,
Igor Tandetnik

With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going to
land, and it could be dangerous sitting under them as they fly
overhead. -- RFC 1925

Stephen Howe

2005-02-14, 9:11 pm

> Note that this code gives you the range [75, 100] inclusive. The last
> call to upper_bound will return an iterator to 101 or higher - the first
> value that is strictly greater than 100. If you indeed want [75, 100),
> use lower_bound in both calls.

Yes you right. My notation is wrong. I meant 1 beyond the last 100 in the
vector. So upper_bound() is correct. I suppose what I really want is

[75, 100+1)

Thanks

Stephen Howe

Igor Tandetnik

2005-02-14, 9:11 pm

"Jerry Coffin" <jcoffin@taeus.us> wrote in message
news:MPG.1c60a87ce92a5b929897d9@msnews.microsoft.com
> In article <eHtojWyAFHA.2640@TK2MSFTNGP14.phx.gbl>, "Stephen Howe"
> <stephenPOINThoweATtns-globalPOINTcom> says...
> It can be done with the other form of equal_range (the one that takes
> a predicate) though the methodology isn't at all obvious:
>
> template<class T>
> class in_range {
> T tolerance;
> public:
> in_range(T const &t) : tolerance(t) {}
>
> bool operator()(T const &X, T const &Y) {
> return (X<(Y-tolerance)) ||
> (X>(Y+tolerance));
> }
> };
>
> range = std::equal_range(v.begin(), v.end(), 87, in_range<int>(12));

Your predicate does not induce a strict weak ordering on the values, and
thus cannot be passed to equal_range. Specifically, it is intransitive:

in_range<int>(1)(1, 4) == true && in_range<int>(1)(4, 2) == true // but
in_range<int>(1)(1, 2) == false

The relation equiv(t)(x, y) == (!in_range(t)(x, y) && !in_range(t)(y,
x)) is also intransitive. It can be rewritten equivalently as abs(x - y)
<= t. Then

equiv(1)(1, 2) == true && equiv(1)(2, 3) == true //but
equiv(1)(1, 3) == false

The correct comparator would be like this:

template <typename T>
struct RangeComp : public std::binary_function<T, T, bool>
{
RangeComp(const T& low, const T& high) :
low_(low), high_(high)
{}
bool operator()(const T& x, const T& y) const
{
// treat all values in range as equivalent
if (!(x < low_) && x < high_ &&
!(y < low_) && y < high_)
{
return false;
}
return (x < y);
}
private:
T low_;
T high_;
};

range = std::equal_range(v.begin(), v.end(), 75, RangeComp<int>(75,
100));

Any value that falls within range can be used as the third parameter,
since they are all considered equal by the comparator.
--
With best wishes,
Igor Tandetnik

With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going to
land, and it could be dangerous sitting under them as they fly
overhead. -- RFC 1925

Stephen Howe

2005-02-14, 9:11 pm

> It can be done with the other form of equal_range (the one that takes
> a predicate) though the methodology isn't at all obvious:
>
> template<class T>
> class in_range {
> T tolerance;
> public:
> in_range(T const &t) : tolerance(t) {}
>
> bool operator()(T const &X, T const &Y) {
> return (X<(Y-tolerance)) ||
> (X>(Y+tolerance));
> }
> };

Thanks Jerry, it is an interesting idea, but apart from the problems Igor
noted, it will only work if difference between values is odd, it won't work
if even.

Stephen

Sponsored Links