"comparable" interface for generic/templated objects?

[vk]

short question:
If I have a class with 1 generic type (type T), what is the best way
to compare objects of type T?

bkgd:
We wrote this generic java priority queue which uses a min-heap
(stored in an ArrayList) for class. All of the objects in the min-heap
are of a single (unknown at compile time) type. This unknown type has
to implement java.lang.Comparable so in the priority queue, I can
decide which node to put where. The function to compare objects just
casts them to the Comparable interface and then calls the obj.compareTo
(obj) method.

I'm looking to improve my c++, so I decided to re-write it (in c++).
If there is a Comparable (or similar) interface that works with
primitives and objects, it would be good to know.

 

[Alf P. Steinbach]

* vk:

short question:
If I have a class with 1 generic type (type T), what is the best way
to compare objects of type T?

The convention in C++ is to use the "less than" operator a < b and the "equals"
operator "==" (even though the latter can be expressed as !(a<b) && !(b<a)).

I.e., while in Java the type exposes an interface, in C++ it exposes the "less
than" and "equals" operators.

The standard library <utility> header conveniently defines the other relational
operators in terms of the above, in namespace "std::rel_ops".


Cheers & hth.,

- Alf

 

[vk]

thanks!, that does help.

I guess Java makes you implement an interface to compare objects
because there is no operator overloading..

I'm surprised that the compiler will let you call op< et al. on
objects that might not have those methods overloaded, though.

 

[Ian Collins]

thanks!, that does help.

What does, Please quote enough context for you reply to make sense.

I guess Java makes you implement an interface to compare objects
because there is no operator overloading..

I'm surprised that the compiler will let you call op< et al. on
objects that might not have those methods overloaded, though.

It doesn't.

struct A { int i; };
struct B { int n; };

int main() {
A a;
B b;

if( a < b ) {}
}
"/tmp/z.cc", line 8: Error: The operation "A<B" is illegal.

 

[ld]

thanks!, that does help.

No it doesn't since you said that your type is unknown at compile
time. Overloading will not catch the right type and hence operator.

I guess Java makes you implement an interface to compare objects
because there is no operator overloading..

I'm surprised that the compiler will let you call op< et al. on
objects that might not have those methods overloaded, though.

It doesn't. Overloading works at compile time so the compilers will
not let you call an undefined (undeclared) function.

What you need is overriding, that is you define a common abstract
class Comparable (as in Java) and override the compareTo member
function in its derived types. Abstract class is the C++ concept which
amongst others, can simulate the behavior of Java interface.

Then the operators/functions mentioned will just be wrappers
(syntactic sugar) around your member function compareTo in order to
use some generic algorithms which rely on (i.e. static duck typing).
To be complete, you will also need to implement the visitor pattern
(i.e. double dispatch) to handle polymorphic types in both arguments
and re-inject some static information after each resolution. Otherwise
you can use the dynamic_cast operator (slower but simpler).

Another possibility is to use the variant types from the Boost
library.

a+, ld.

 

[Alf P. Steinbach]

* ld:

No it doesn't since you said that your type is unknown at compile
time. Overloading will not catch the right type and hence operator.

That's just meaningless, sorry.

If you try to create an example you will perhaps see why it's meaningless.

If you don't see it then just post your example in this group and you'll have it
examined and commented on by competent folks.


Cheers, & hth.,

- Alf

 

[Daniel Pitts]

short question:
If I have a class with 1 generic type (type T), what is the best way
to compare objects of type T?

bkgd:
We wrote this generic java priority queue which uses a min-heap
(stored in an ArrayList) for class. All of the objects in the min-heap
are of a single (unknown at compile time) type. This unknown type has
to implement java.lang.Comparable so in the priority queue, I can
decide which node to put where. The function to compare objects just
casts them to the Comparable interface and then calls the obj.compareTo
(obj) method.

I'm looking to improve my c++, so I decided to re-write it (in c++).
If there is a Comparable (or similar) interface that works with
primitives and objects, it would be good to know.

If you are using templates, then you'll have something that is sometimes
called Compile-Time polymorphism. There is no "interface", hierarchy,
just a "does it do what I need it to do."

The convention in C++ is to use less than comparison "a < b", which can
be created for classes. There is nothing to say you can't create a
polymorphic Comparable interface, but it that kind of thing is more
expensive in C++ than in Java.

 

[ld]

* ld:



That's just meaningless, sorry.

If you try to create an example you will perhaps see why it's meaningless..

If you don't see it then just post your example in this group and you'll have it
examined and commented on by competent folks.

I thought that after two decades of using C++, I started to know a bit
of it.
To avoid wasting the time of everybody, you competent folk could show
us a nice example where overloading solve the problem of comparing two
polymorphic types, as mentioned by the OP. After that, I will maybe
post a link to a course which I did some time ago on this topic (more
precisely it was on the influence of static typing vs polymorphism on
large scale software design).

a+, ld.

 

[Alf P. Steinbach]

* ld:

I thought that after two decades of using C++, I started to know a bit
of it.
To avoid wasting the time of everybody, you competent folk could show
us a nice example where overloading solve the problem of comparing two
polymorphic types, as mentioned by the OP.

C++ is not Java, and I think that was what the OP asked about, how to do things
in C++. Not how to translate the Java mechanically to equivalent C++. E.g., C++
has user defined operators and doesn't have a common Object base class.

std:riority_queue is an example of how to do things in C++.

Could you perhaps quote where the OP or anyone else (except yourself) mentioned,
for C++, "overloading", "polymorphic" and "comparing two ... types". Or could
you perhaps quote where such was mentioned for Java. I'm sorry but I can't
recall reading that earlier.


TIA.,

- Alf

 

[ld]

* ld:





C++ is not Java, and I think that was what the OP asked about, how to do things
in C++.

I agree, but taking into account the mentioned background.

Not how to translate the Java mechanically to equivalent C++. E.g., C++
has user defined operators and doesn't have a common Object base class.

user defined operators are (very useful) syntactic sugar but nothing
prevent to define the operator< as a wrapper to a member function, in
particular if the type is polymorphic. And you don't need a common
Object base class to simulate Java interfaces.

std:riority_queue is an example of how to do things in C++.

So what is the first template argument of your std:riority_queue
when the type is not known at compile time, as mentioned by the OP?

Could you perhaps quote where the OP or anyone else (except yourself) mentioned,
for C++, "overloading", "polymorphic" and "comparing two ... types". Or could
you perhaps quote where such was mentioned for Java. I'm sorry but I can't
recall reading that earlier.

Maybe I was too fast, so I give more details.

"Overloading", quoting your answer:

"I.e., while in Java the type exposes an interface, in C++ it exposes
the "less
than" and "equals" operators."

Your are comparing java interface requiring overriding (polymorphism)
to C++ user defined operators as the C++ solution/replacement without
mentioning C++ related terms like abstract class, virtual member
function, polymorphic type or dynamic_cast. Look's like comparing
oranges and apples.

"Polymorphic, compareTo", quoting the OP:

"All of the objects in the min-heap are of a single (unknown at
compile time) type. This unknown type has to implement
java.lang.Comparable so in the priority queue, I can decide which node
to put where. The function to compare objects just
casts them to the Comparable interface and then calls the
obj.compareTo
(obj) method.

If the type if not known at compile time, it means that it is
polymorphic, otherwise it would be known at compile time. The role of
java.lang.Comparable is to compare two polymorphic objects in Java, in
particular when the Comparable interface is retrieved by a cast which
usually means that the static type is lost. Since the OP mentioned it,
the least would be to give an equivalent solution, and since C++
allows to do so, no reason to change the name of the abstract class
(OP interface) or the virtual member function (OP method) to confuse
the OP. Wrapping the Comparable::compareTo virtual member function
into an overloaded operator< to be compliant with the STL algorithms
is just an adaption and can be done later, once the C++ approach is
well understood.

a+, ld.

 

[Alf P. Steinbach]

* ld:

If the type if not known at compile time, it means that it is
polymorphic, otherwise it would be known at compile time.

OP: "If I have a class with 1 generic type (type T), what is the best way
to compare objects of type T?"

Would be nice if you could just relate to what's written.



Cheers & hth.,

- Alf

 

[Kai-Uwe Bux]

* ld:

OP: "If I have a class with 1 generic type (type T), what is the best way
to compare objects of type T?"

Would be nice if you could just relate to what's written.

He did. Just to a different part of what was written:

OP: All of the objects in the min-heap are of a single (unknown at compile
time) type.

From context, there is no doubt that the OP wants to compare the objects in
the min-heap.

I think the confusion arises because you feel that for the underlying
problem (whatever that may be) it is an artifact of the Java solution that
the type is unknown at compile time and that an idiomatic C++ solution
would involve types that are known at compile time. I think, you are
probably right. Unfortunately, we cannot tell since the OP has not told us
what his problem is.


Best

Kai-Uwe Bux

 

[ld]

* ld:




OP: "If I have a class with 1 generic type (type T), what is the best way
to compare objects of type T?"

Would be nice if you could just relate to what's written.

I did but it seems that you prefer to discard 2/3 of his post (the
background) that the OP took the time to give us. In particular he has
explicitly mentioned that the type is NOT known at compile time and
its interface will be retrieve by a (dynamic) cast, despite of the
fact that Comparable is a parametrized interface in Java. Maybe you
should re-read his entire post and my answers and point me where I am
missing something or assuming something wrong as I did for your
answer.

I feel to have answered to the OP, assuming that he is a responsible
person who took the time to explain the context. So unless the OP
wants/give more information, I consider his question and my answer as
consistent and close the discussion.

a+, ld.

 

[Alf P. Steinbach]

* ld:

I did but it seems that you prefer to discard 2/3 of his post (the
background) that the OP took the time to give us. In particular he has
explicitly mentioned that the type is NOT known at compile time and
its interface will be retrieve by a (dynamic) cast, despite of the
fact that Comparable is a parametrized interface in Java. Maybe you
should re-read his entire post and my answers and point me where I am
missing something or assuming something wrong as I did for your
answer.

I did, but you refused to try to code up an example.

Seeing something does require not expending great effort in looking away.

The queue is parameterized with a type T. All of the objects "are of a single
type", which to accomodate what I think is your view we might say is a type U
derived from T, and that the queue internally stores T* pointers. Then either
there is only one possible derived class, or at some point X the code must
ensure that only U objects are stored in the queue, otherwise they won't all be
of a single type U. Under the assumption of more than one possible derived
class, then at point X the type U is therefore known or can be established, for
if it isn't known or can't be established then the U dynamic type property can't
be assured. Hence the assumption that type U is and must be unknown yields a
contradiction, and is utterly rubbish.

I feel to have answered to the OP, assuming that he is a responsible
person who took the time to explain the context. So unless the OP
wants/give more information, I consider his question and my answer as
consistent and close the discussion.

In the previous paragraph you ask me for clarification of what you might have
missed (great! ). But here, immediately following, you're stating that unless
the OP serves up such clarification you'll ignore it. Oh well.


Cheers & hth.,

- Alf

 

[James Kanze]

short question:
If I have a class with 1 generic type (type T), what is the
best way to compare objects of type T?

bkgd:
We wrote this generic java priority queue which uses a
min-heap (stored in an ArrayList) for class. All of the
objects in the min-heap are of a single (unknown at compile
time) type. This unknown type has to implement
java.lang.Comparable so in the priority queue, I can decide
which node to put where. The function to compare objects just
casts them to the Comparable interface and then calls the
obj.compareTo (obj) method.

I'm looking to improve my c++, so I decided to re-write it (in
c++). If there is a Comparable (or similar) interface that
works with primitives and objects, it would be good to know.

Since the other programmers seem to be more interested in
arguing with one another than with answering your question:

C++ supports two types of genericity. Most of the time, objects
in containers have value semantics, and are not (run-time)
polymorphic; if you possibly can, that's what you should do as
well. In this case, the "polymorphism" is resolved at compile
time, and uses duck typing---you don't have to derive from any
given interface, just provide the required functionality. (In
this case, by default, an operator<, or more precisely,
std::less, which by default uses operator<.)

If you need a container which contains several different types
(all deriving from a common base), you need a container of
pointers, since containers do not support polymorphic objects.
This introduces several additional complexities, like managing
the memory. And In this case, you'll have to specify the
comparison function anytime it is needed (since comparison of
pointers only takes into account the pointer value, and defines
an arbitrary ordering). If you need to do this, you can define
your own Comparable interface, and derive from it. You then
define the comparator type you use for the functions to call it.

 

[ld]

* ld:









I did, but you refused to try to code up an example.

Seeing something does require not expending great effort in looking away.

The queue is parameterized with a type T. All of the objects "are of a single
type", which to accomodate what I think is your view we might say is a type U
derived from T, and that the queue internally stores T* pointers.

It's not my view, you should read again the entire question of the OP.

In the previous paragraph you ask me for clarification of what you might have
missed (great! ). But here, immediately following, you're stating that unless
the OP serves up such clarification you'll ignore it. Oh well.

Because I have adapted my answer to the question, not the opposite by
discarding the context of the question. Hence, unless the context of
the question changes, or the OP wants some clarifications, the
discussion is closed.

a+, ld.

 

[Alf P. Steinbach]

* ld:

It's not my view, you should read again the entire question of the OP.

You snipped the part showing your assumption to be completely meaningless.

I.e. you're a troll.

Goodbye,

- Alf