map in stl

[Pascal]

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

 

[diligent.snail]

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

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.

 

[diligent.snail]

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

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.

 

[Michael DOUBEZ]

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

 

[Pete Becker]

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.

 

[Mark P]

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

 

[jeffrey.j.schmitz]

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

 

[Mark P]

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