What caontainer shall be used instead of std::map is there is noorders in keys?

[Peng Yu]

Hi,

Suppose I have a bunch of keys that map to some values. I can only
compare whether two keys are equal or not but there is no order
between different keys, that is, there is no ">" and "<" operator.

I think sgi's hash_map can be used for this case. But it is not in C++
standard. I'm wondering what other STL container I can use?

Thanks,
Peng

 

[Kai-Uwe Bux]

Hi,

Suppose I have a bunch of keys that map to some values. I can only
compare whether two keys are equal or not but there is no order
between different keys, that is, there is no ">" and "<" operator.

I think sgi's hash_map can be used for this case. But it is not in C++
standard. I'm wondering what other STL container I can use?

The next iteration of the standard will contain unordered_map<>. It may
serve your needs, but you will have to supply a hash-function (the standard
will provide hash-functions for some standard types). If your
implementation is slightly ahead of things, it may already contain
tr1::unordered_map<>.

Otherwise,

std::some_sequence< pair< key_type, mapped_type > >

comes to mind.


Best

Kai-Uwe Bux

 

[Erik Wikström]

Hi,

Suppose I have a bunch of keys that map to some values. I can only
compare whether two keys are equal or not but there is no order
between different keys, that is, there is no ">" and "<" operator.

Unless you can use unordered_map or similar, as Kai-Uwe Bux advised, you
can always impose an artificial ordering on the keys. There are a lot of
things that has no logical order in real life (colours for one). But as
soon as you model them in a computer they become a pattern of bits,
which can always be interpreted as a number.

If you do not want your key-class to have a public < operator there is
an (kind of ugly) trick you can use. Declare the operator private and
make std::less<key-class> a friend. This works because std::map uses
std::less to compare two elements, unless you tell it to use something else.

 

[Peng Yu]

Unless you can use unordered_map or similar, as Kai-Uwe Bux advised, you
can always impose an artificial ordering on the keys. There are a lot of
things that has no logical order in real life (colours for one). But as
soon as you model them in a computer they become a pattern of bits,
which can always be interpreted as a number.

If you do not want your key-class to have a public < operator there is
an (kind of ugly) trick you can use. Declare the operator private and
make std::less<key-class> a friend. This works because std::map uses
std::less to compare two elements, unless you tell it to use something else.

http://www.boost.org/doc/libs/1_36_0/doc/html/unordered.html
There is 'unordered' in boost.

If I don't use 'unordered', I could define an artificial order by
defining std::less<T>. The good thing of this approach is that I don't
have specify the comparator for std::map. However, this could break
other code. For example, I first have two double's compared, later I
change double to std::complex<double>, which shall not be compared.
But since I defined std::less<T> for std::complex<T>, the compiler
would accept the code, which is wrong.

If I could make an function object that gives artificial order, but
then I have to specify it whenever I use std::map, which is too
tedious.

Since both the above approaches have shortcoming, it is then better to
use 'unordered' if I can, right?


Thanks,
Peng

 

[James Kanze]

Unless you can use unordered_map or similar, as Kai-Uwe Bux
advised, you can always impose an artificial ordering on the
keys. There are a lot of things that has no logical order in
real life (colours for one). But as soon as you model them in
a computer they become a pattern of bits, which can always be
interpreted as a number.

If you do not want your key-class to have a public < operator
there is an (kind of ugly) trick you can use. Declare the
operator private and make std::less<key-class> a friend. This
works because std::map uses std::less to compare two elements,
unless you tell it to use something else.

Why bother with an operator< at all? Just defined an ordering
function (isBefore), then specialize std::less to use it.
(You're allowed to specialize standard types and functions over
user defined types, as long as the specialization fulfills the
requirements of the function or type.) Or just provide some
ordering functional object, and require the user to specify it
when instantiating the map or the set.

 

[James Kanze]

http://www.boost.org/doc/libs/1_36_0/doc/html/unordered.html
There is 'unordered' in boost.

If I don't use 'unordered', I could define an artificial order
by defining std::less<T>. The good thing of this approach is
that I don't have specify the comparator for std::map.
However, this could break other code. For example, I first
have two double's compared, later I change double to
std::complex<double>, which shall not be compared. But since
I defined std::less<T> for std::complex<T>, the compiler would
accept the code, which is wrong.

Not if the user code used < for the comparison. The whole point
of specializing std::less (rather than defining operator<) is
that user code won't use it; it will only be used for ordering
in containers.

If I could make an function object that gives artificial
order, but then I have to specify it whenever I use std::map,
which is too tedious.
Really?

Since both the above approaches have shortcoming, it is then
better to use 'unordered' if I can, right?

Using unordered means that you have to define a hash function,
defining a good hash function is a lot more complex than
defining ordering (usually), and if you provide a bad one, it
almost certainly won't show up in your tests, but your actual
application will run significantly slower. (Actually, it is
possible to more or less test the quality of a hash function;
hash a large number of random instances of your object, modulo
something (say 100), and count each of the results. Then do
some very simple statistical analysis on the counts. I actually
do this when reasonable, but most people I've seen don't, and
it's not necessarily simple to generate "random" values for many
classes.)