Imitation of Java Generics

Generic programming is very common and has different names (and features) in various programming languages; C++ provides Turing-Complete Templates, Java offers Generics (along with Ada, Eiffel, C#, and Visual Basic .Net), and Parametric Polymorphism is present in ML, Scala, and Haskell.

While I am generally pretty happy with what C++ has to offer, adopting some of the features offered by other mechanisms can come in handy sometimes. To be more specific, in this post we will mimic Java’s support for defining a common super-type for generic elements (i.e. List).

The task at hand is the implementation of a priority queue, which is essentially a heap. Sure enough, the priority queue will have a parametric (template) type T, which will have to be Comparable. Something along the lines of:

template <typename T>
struct priority_queue {
    // ...
};

Keep in mind that we will have to do one of two things:

  • Either clearly state in the documentation that the implementation of our priority_queue heavily relies on type T having implemented operator<,
  • Or add another parametric (template) type F, to serve as a Comparator.

Both things may seem a little far from optimal. Have we gone with Java in the first place, all we would have had to do would have been something closely resembling the following:

class priority_queue<T extends Comparable>

As it turns out, the same effect (although with slightly different syntax) can actually be achieved even in C++, through utilization of two boost utilities: is_base_of and static_assert. A brief sketch is hereby presented:

struct Comparable {
    // required API..
};

template <typename T>
class priority_queue {
    // Ask compiler to enforce that T is a subtype of Comparable:
    BOOST_STATIC_ASSERT(boost::is_base_of<Comparable, T>::value);
};

A colleague of mine walked up to me some time ago and asked why isn’t such a mechanism included in C++’s core features. After putting some more thought into it, I have come to the conclusion that I would actually hate seeing such a built-in C++ feature – In my opinion, it will lead to an excessive number of not-general-enough base classes, which are only there to feed this mechanism. Moreover, it is very likely to lead to much more abuse of the multiple inheritance mechanism.

The C++0x standard draft presented a related feature named Concepts (and Concept-maps), which were recently dropped as well.

What do you think?

6 thoughts on “Imitation of Java Generics

  1. Your example would certainly result an unnecessary amount of base classes in C++. This is largely because in C++ there is no such thing as an interface or a mixin. In Java, this works because Comparable is an interface (implements not extends).

  2. I think you have not understood java generics, nor C++ concepts.

    Java generics relies on introspection, and through introspection loses all its face value.

    C++ concepts are an attempt to mimic part of haskell classes, and it´s been dropped mainly on the difficulty to agree how tio implement them, not on a basis on not seeing it as useful. In fact, it has only been delayed.

    As you see, Java generics are checked at compile-time and easily bypassavbble at run-time, while concepts do force checking at compile-time, but are not bypassable as they do not create any run-time artifact. Just like Haskell classes.

    I think it is an error to put all these different ideas under a misnomer as ‘generic programming’.

  3. As Zara said, you seem to be underestimating concepts. Concepts were supposed to be non-intrusive, you wouldn’t have to derive your class from Comparable it would be deduced automatically from the concept.

    auto concept Comparable<typename T> {
        bool operator<(const T&, const T&);
    };
    

    And you could also adapt types to meet the static interface.

    concept_map Comparable {
       bool operator<(const SomeType& lhs, const SomeType&rhs) { 
          return lhs.IsLessThan(rhs);
      }
    
  4. Your example is rewritten in C++ using static interface.
    Like it is done in std:: classes .

    template <typename T, typename Compare = std::less >
    class priority_queue;

    I don’t remember myself needing this type check so often.

    Since C++ doesn’t have a standard interfaces like Comparable, in most cases you rely on compile-time interface.

  5. And this is why C++ programmers laugh when Java programmers talk about object models and what could be stripped away without loss.

  6. Hi,
    I would like to add to your view of generics that apart from problems like clumsy interface (we require unnecessary inheritance) and some safety issues, they have obvious advantages over templates, at least when it comes to defining generic containers:
    1. No cryptic error messages.
    2. Much faster compilation – a generic can be compiled once, regardless of how many times you instantiate it and with how many types.
    3. Smaller executable – each template instantiation generates almost the same code time and again – this is not so for generics

    That said, I would also not like to see generics in C++. You can still implement something similar yourself using templates.

    Regards,
    &rzej

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>