 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Stephen Howe
Guest
|
 Posted: Wed Jan 26, 2005 9:52 am Post subject: New form of equal_range() |
 |
|
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 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! ]
|
|
| Back to top |
|
 |
Motti Lanzkron
Guest
|
| Posted: Wed Jan 26, 2005 6:59 pm Post subject: Re: New form of equal_range() |
|
|
Stephen Howe wrote:
| Quote: | 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! ]
|
|
| Back to top |
|
|
Bob Brian
Guest
|
| Posted: Wed Jan 26, 2005 7:22 pm Post subject: Re: New form of equal_range() |
|
|
Stephen Howe wrote:
| Quote: | 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
return i
}
};
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! ]
|
|
| Back to top |
|
|
msalters
Guest
|
| Posted: Wed Jan 26, 2005 7:31 pm Post subject: Re: New form of equal_range() |
|
|
Stephen Howe wrote:
| Quote: | 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! ]
|
|
| Back to top |
|
|
Andrew Koenig
Guest
|
| Posted: Wed Jan 26, 2005 8:51 pm Post subject: Re: New form of equal_range() |
|
|
"Stephen Howe" <sjhoweATdialDOTpipexDOTcom (AT) eu (DOT) uu.net> wrote
| Quote: | 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! ]
|
|
| Back to top |
|
|
Stephen Howe
Guest
|
| Posted: Thu Jan 27, 2005 12:52 pm Post subject: Re: New form of equal_range() |
|
|
| Quote: | 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! ]
|
|
| Back to top |
|
|
John Potter
Guest
|
| Posted: Thu Jan 27, 2005 12:52 pm Post subject: Re: New form of equal_range() |
|
|
On 26 Jan 2005 04:52:21 -0500, "Stephen Howe"
<sjhoweATdialDOTpipexDOTcom (AT) eu (DOT) uu.net> wrote:
| Quote: | 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.
| Quote: | 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
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! ]
|
|
| Back to top |
|
|
Stephen Howe
Guest
|
| Posted: Thu Jan 27, 2005 12:54 pm Post subject: Re: New form of equal_range() |
|
|
| Quote: | 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! ]
|
|
| Back to top |
|
|
David Abrahams
Guest
|
| Posted: Thu Jan 27, 2005 12:55 pm Post subject: Re: New form of equal_range() |
|
|
"Andrew Koenig" <ark (AT) acm (DOT) org> writes:
| Quote: | "Stephen Howe" <sjhoweATdialDOTpipexDOTcom (AT) eu (DOT) uu.net> wrote in message
news:41f7170a$0$311$cc9e4d1f (AT) news (DOT) 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! ]
|
|
| Back to top |
|
|
John Potter
Guest
|
| Posted: Thu Jan 27, 2005 12:56 pm Post subject: Re: New form of equal_range() |
|
|
On 26 Jan 2005 13:59:15 -0500, Motti Lanzkron <mlanzkron (AT) yahoo (DOT) co.uk>
wrote:
| Quote: | 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! ]
|
|
| Back to top |
|
|
M Jared Finder
Guest
|
| Posted: Thu Jan 27, 2005 1:07 pm Post subject: Re: New form of equal_range() |
|
|
Motti Lanzkron wrote:
| Quote: | 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! ]
|
|
| Back to top |
|
|
Nicola.Musatti@ObjectWay.
Guest
|
| Posted: Thu Jan 27, 2005 8:48 pm Post subject: Re: New form of equal_range() |
|
|
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! ]
|
|
| Back to top |
|
|
Motti Lanzkron
Guest
|
| Posted: Thu Jan 27, 2005 8:56 pm Post subject: Re: New form of equal_range() |
|
|
John Potter wrote:
| Quote: |
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! ]
|
|
| Back to top |
|
|
Stephen Howe
Guest
|
| Posted: Thu Jan 27, 2005 8:58 pm Post subject: Re: New form of equal_range() |
|
|
| Quote: | 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! ]
|
|
| Back to top |
|
|
David Abrahams
Guest
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
