How do you define key_compare and value_compare

[Dennis]

I'm writing a restricted map<Str,Int> for an assignment, without using
the map template. One of the things I'm having trouble with is trying
to define the key_compare and value_compare for this class. How do you
define those?

Dennis

[Dennis]

Update: Okay, my assignment doesn't need it any more, but I'd still
like to learn about how to do this for future templates I might write.
Thanx.

Dennis

[Kai-Uwe Bux]

Dennis wrote:

I'm writing a restricted map<Str,Int> for an assignment, without using
the map template. One of the things I'm having trouble with is trying
to define the key_compare and value_compare for this class. How do you
define those?

I am not sure, I know what you mean. Within your template you should have
some typedefs:

template< typename KeyType, typename MappedType >
class map {

typedef KeyType const key_type;
typedef MappedType mapped_type;
typedef std::pair< key_type, mapped_type > value_type;

};

Then you will use std::less< key_type > and std::less< value_type > as the
default comparison functions.

If that is not what you meant, you will need to say more about the Str class
and the Int class.
Best

Kai-Uwe Bux

[Dennis]

What I really meant to say was it is like a map<string,int> rather than
any special class I wrote myself. The description of key_compare is a
"Function object that compares two keys for ordering". So does that
mean it's a class within the map<string,int> that key_comp() uses?

Dennis

[Kai-Uwe Bux]

Dennis wrote:

What I really meant to say was it is like a map<string,int> rather than
any special class I wrote myself. The description of key_compare is a
"Function object that compares two keys for ordering". So does that
mean it's a class within the map<string,int> that key_comp() uses?

Not quite. In order to illustrate the significance of key_comp, let me take
a little detour and recall the way a map is typically implemented. Usually,
std::map< key_type, mapped_type > uses a (balanced) tree whose nodes store
pairs

std::pair< key_type const, mapped_type >

In order to find efficiently a node for a given key, the tree is organized
as a search tree, i.e., for any given node V, the left subtree has keys
less than the key at V and the right subtree only hosts keys not smaller
than the key at V.

Now, in order to compare keys, the map container uses a comparison function.
This function defaults to std::less<key_type>. You can, however, specify a
comparison function of your own choice. In order to do so, you pass a
function object (in the simplest case, a free standing function) as a
parameter upon construction of the map object.

In your example, map<string,int>: the default std::less<string> will be
lexicographic comparison of strings. If you know that your strings will
typically have long common initial segments but differ in length, you may
want to replace that with a short_lex order comparison predicate for
efficiency.
Hope this helps

Kai-Uwe Bux

[Dennis]

I think that gets closer to my question. So the "short_lex" in your
explanation is like the new key_compare? If so, how would you write the
comparison predicate?

[Kai-Uwe Bux]

Dennis wrote:

I think that gets closer to my question. So the "short_lex" in your
explanation is like the new key_compare? If so, how would you write the
comparison predicate?

Please quote what you are referring to: (a) how am I supposed to remember
something that is in the past? and (b) how is anybode else supposed to make
sense of your question?

Anyway, the short_lex order for strings goes like so:

#include <string>
#include <algorithm>

bool short_lex_is_less ( std::string const & a,
std::string const & b ) {
if ( a.length() < b.length() ) {
return ( true );
}
if ( b.length() < a.length() ) {
return ( false );
}
// length did not decide:
return ( std::lexicographical_compare( a.begin(), a.end(),
b.begin(), b.end() ) );
}
But to use it with a map, you would need to do something like this:

typedef bool (*string_compare)( std::string const &, std::string const & );

#include <map>

int main ( void ) {
std::map< std::string, int, string_compare >
the_map ( short_lex_is_less );
}

Hope this helps

Kai-Uwe Bux