| Topic: |
DEVELOP > c-Plus-Plus |
| User: |
"Pascal" |
| Date: |
08 Nov 2007 04:02:48 AM |
| Object: |
map in stl |
I'm using a map for storing information.
With lower_bound i can find keys equal to or greater then the key i give as
a parameter. With upper_bound i can find keys greater then the key i give as
a parameter.
What i want is find keys less then or equal to the key i give. Is that
possible with a map? After googling for 1 hour, it seems that nobody ever
needed this functionality :-)
--
Pascal
.
|
|
| User: "Pete Becker" |
|
| Title: Re: map in stl |
08 Nov 2007 08:54:26 AM |
|
|
On 2007-11-08 05:02:48 -0500, "Pascal" <NoSpam@NoSpam.NoSpam> said:
I'm using a map for storing information.
With lower_bound i can find keys equal to or greater then the key i give as
a parameter. With upper_bound i can find keys greater then the key i give as
a parameter.
What i want is find keys less then or equal to the key i give. Is that
possible with a map? After googling for 1 hour, it seems that nobody ever
needed this functionality :-)
Remember, iterators work in pairs: [first, last) is a sequence of
elements. When you call upper_bound you get an iterator 'res' that
points at the first element in [first, last) whose key is greater than
the key you passed. So the sequence [res, last) is the sequence of
elements with keys that are greater than the key. Now think of 'res' as
the end instead of the subsequence instead of the beginning: the
sequence [first, res) is all the elements with keys that are less than
or equal to the given key.
Similarly, if you call lower_bound, its result gives you a subsequence
[first, res) whose elements all have keys that are less than the given
key.
--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)
.
|
|
|
|
| User: "" |
|
| Title: Re: map in stl |
08 Nov 2007 04:51:55 AM |
|
|
On Nov 8, 11:02 am, "Pascal" <NoS...@NoSpam.NoSpam> wrote:
I'm using a map for storing information.
With lower_bound i can find keys equal to or greater then the key i give as
a parameter. With upper_bound i can find keys greater then the key i give as
a parameter.
What i want is find keys less then or equal to the key i give. Is that
possible with a map? After googling for 1 hour, it seems that nobody ever
needed this functionality :-)
--
Pascal
Do no know how useful would be, but how about a function like so:
// M must be sorted.
template<typename M>
typename M::const_iterator less_than_or_equal( const M& m, const
typename M::key_type& k )
{
M::const_iterator i = m.find( k );
return ( i == m.end() ? i : m.begin() );
}
Regards.
.
|
|
|
|
| User: "" |
|
| Title: Re: map in stl |
08 Nov 2007 05:09:09 AM |
|
|
On Nov 8, 11:02 am, "Pascal" <NoS...@NoSpam.NoSpam> wrote:
I'm using a map for storing information.
With lower_bound i can find keys equal to or greater then the key i give as
a parameter. With upper_bound i can find keys greater then the key i give as
a parameter.
What i want is find keys less then or equal to the key i give. Is that
possible with a map? After googling for 1 hour, it seems that nobody ever
needed this functionality :-)
--
Pascal
Or more likely:
template<typename M>
typename M::const_iterator less_than_or_equal( const M& m, const
typename M::key_type& k )
{
M::const_iterator i1 = m.find( k );
if( i1 != m.end() )
return i1;
M::const_iterator i2 = m.lower_bound( k );
return ( i2 == m.end() ? i2 : ( i2 == m.begin() ? m.end() : --i2 ) );
}
Regards.
.
|
|
|
|
| User: "Michael DOUBEZ" |
|
| Title: Re: map in stl |
08 Nov 2007 05:57:34 AM |
|
|
Pascal a écrit :
I'm using a map for storing information.
With lower_bound i can find keys equal to or greater then the key i give as
a parameter. With upper_bound i can find keys greater then the key i give as
a parameter.
What i want is find keys less then or equal to the key i give. Is that
possible with a map?
You mean like using std::lower_bound() with reverse iterators of map and
std::greater() as the strict weak ordering operator ?
std::lower_bound(m.rbegin(),m.rend(),val,std::greater())
After googling for 1 hour, it seems that nobody ever
needed this functionality :-)
Here it is.
Michael
.
|
|
|
|
| User: "Mark P" |
|
| Title: Re: map in stl |
08 Nov 2007 12:21:42 PM |
|
|
Pascal wrote:
I'm using a map for storing information.
With lower_bound i can find keys equal to or greater then the key i give as
a parameter. With upper_bound i can find keys greater then the key i give as
a parameter.
What i want is find keys less then or equal to the key i give. Is that
possible with a map? After googling for 1 hour, it seems that nobody ever
needed this functionality :-)
Almost always these sorts of queries can be solved by using UB, LB, or
at times, the first increment or decrement of those. Here it's actually
very simple: you want the range [m.begin(), m.upper_bound(k)).
You should convince yourself that this does the right thing even if all
keys are greater than k or all keys are less than or equal to k. And
keep in mind the convention that ranges are specified as [start, one
past the end).
-Mark
.
|
|
|
| User: "" |
|
| Title: Re: map in stl |
15 Nov 2007 03:19:39 PM |
|
|
To do what you want, loop from map.begin() to end() and break when
iterator->first > searchKey.
See http://theschmitzer.blogspot.com for alternative search strategies
using predicates.
Jeff
.
|
|
|
| User: "Mark P" |
|
| Title: Re: map in stl |
15 Nov 2007 05:46:13 PM |
|
|
wrote:
To do what you want, loop from map.begin() to end() and break when
iterator->first > searchKey.
See http://theschmitzer.blogspot.com for alternative search strategies
using predicates.
Jeff
Besides omitting context and replying to the wrong post, this is also
pretty bad advice. The *_bound functions are O(log n)-- reading through
the entire map is O(n). It's perfectly reasonable that one may way to
find the range in question without actually examining every element in
that range.
Regarding your blog post about partial match searching in a map, I
believe there are better ways to do this than burdening every object of
type Key with a mode flag. One possibility is to use a dynamic functor
as your comparison-- the functor maintains a pointer to some other
object whose state dictates the behavior of the functor. This allows
for a flexible comparison function without touching the Key objects.
Mark
.
|
|
|
|
|
|
|
Related Articles |
|
|
