templates versus ADTs

[Taras_96]

It seems that templates and ADTs accomplish very similar things.

Using a template approach:

template <class Incrementable> void foo (Incrementable i)
{
i.increment();
}

and if you write in your code:

Counter myCounter;
foo(myCounter); // automatic template deduction deduction done

then the compiler would essentially 'create' some code that looks like
this:

void foo(Counter myCounter)
{
myCounter.increment();
}

obviously for this to compile you need to have an increment function
in the Counter class.

Compare this to an ADT approach:

void foo (IncrementableInterface i) //Incrementable interface is an
ADT with an increment pure virtual method
{
i.increment();
}

Any classes that extend the IncrementableInterface class can be passed
in as a parameter - the compiler checks this.

To me it seems that the ADT method is cleaner. Both require certain
methods to be implemented in order for compilation to proceed, but the
main advantage of the ADT method is that it is self documenting - by
specifying the virtual methods, the expected interface is specified
explicitly. Compare this with the templated approach, where the only
way of conveying the requirements to a user is via documentation
(which most probably will not be done ).

Obviously if functions/classes parametise the basic C++ types
(float,char,etc), then templates must be used, as a basic type can not
extend an ADT (I think that Java gets around this by declaring Integer
and Char etc.. objects, which extend the base Object class, and thus
are genuine Objects in their own rights). So apart from these cases,
when would a templated approach be used over an ADT approach?

I don't see why the <iterator> templates were decided upon in the
first place (I'm sure there's a good reason). For example, instead of
specifying that the first parameter to the transform function must
satisfy the InputIterator concept, why didn't they just make the first
parameter an ADT with an interface as required by an InputIterator?

The only reason I can see is that if this was the case, then pointers
could not be passed in as iterators.

If all iterators were classes, would this remove the need for an
interator_traits template class? As far as I can see, the only reason
why this class exists is so that you can assign traits to iterator
types that may not be classes (for example, a pointer). Wouldn't
removing the requirement for helper classes would make the library
cleaner and easier to use?

 

[Victor Bazarov]

It seems that templates and ADTs accomplish very similar things.

Using a template approach:

template <class Incrementable> void foo (Incrementable i)
{
i.increment();
}

and if you write in your code:

Counter myCounter;
foo(myCounter); // automatic template deduction deduction done

then the compiler would essentially 'create' some code that looks like
this:

void foo(Counter myCounter)
{
myCounter.increment();
}

obviously for this to compile you need to have an increment function
in the Counter class.

Compare this to an ADT approach:

void foo (IncrementableInterface i) //Incrementable interface is an
ADT with an increment pure virtual method

In order to use run-time polymorphism, you have to pass by reference:

void foo (IncrementableInterface & i)

{
i.increment();
}

Any classes that extend the IncrementableInterface class can be passed
in as a parameter - the compiler checks this.

.... if you declare the argument a reference.

To me it seems that the ADT method is cleaner. Both require certain
methods to be implemented in order for compilation to proceed, but the
main advantage of the ADT method is that it is self documenting - by
specifying the virtual methods, the expected interface is specified
explicitly. Compare this with the templated approach, where the only
way of conveying the requirements to a user is via documentation
(which most probably will not be done ).

At this point, yes. There is a new element of the language, "concept"
being actively discussed. I recommend you read up on those; use the
Standard Committee site to find the relevant documents.

Obviously if functions/classes parametise the basic C++ types
(float,char,etc), then templates must be used, as a basic type can not
extend an ADT (I think that Java gets around this by declaring Integer
and Char etc.. objects, which extend the base Object class, and thus
are genuine Objects in their own rights). So apart from these cases,
when would a templated approach be used over an ADT approach?

Read up about "duck typing". That approach is much more liberal than
inheritance.

I don't see why the <iterator> templates were decided upon in the
first place (I'm sure there's a good reason). For example, instead of
specifying that the first parameter to the transform function must
satisfy the InputIterator concept, why didn't they just make the first
parameter an ADT with an interface as required by an InputIterator?

The only reason I can see is that if this was the case, then pointers
could not be passed in as iterators.

Is that not enough for you? Then read about duck typing.

If all iterators were classes, would this remove the need for an
interator_traits template class? As far as I can see, the only reason
why this class exists is so that you can assign traits to iterator
types that may not be classes (for example, a pointer). Wouldn't
removing the requirement for helper classes would make the library
cleaner and easier to use?

Presence of 'iterator_traits' is not a requirement, it's a convenience.

V

 

[James Kanze]

It seems that templates and ADTs accomplish very similar things.

It seems that templates are the usual way of implementing ADTs
in C++.