Review of two simple function templates

[Slaunger]

Hi forum,

First post here. I trying to learn myself C++ by writing small programs, which solves some of the problems at Project Euler (http://projecteuler.net). I have previously solved a lot of those problems in Python, so the algorithms is not my challenge, but learning the language.

To aid me, I also have a copy of Stroustrup's "C++ Programming Language" by my side.

For some of those problems, a useful utility function is the ability to calculate the greatest common divisor [gcd(a, b)] between two integral types a and b, which is the greatest number which divides both a and b.

Since I might call gcd with a number of different integral types 16 bit, 32 bit, 64 bit or even larger custom types, it seems like a template function would be the right way to do this, so i have implemented the following template function using Euclid's algorithm

/**
 * Returns the greatest common divisor using Euclid's algorithm
 */
template <class T>
T gcd(T a, T b){
        T tmp;
        while (b) {
            tmp = a % b;
            a = b;
            b = tmp;
        }
        return a;
}

The code works for the test cases I have with different integral types and the template parameter T is resolved automatically, such that I can just call gcd(a, b) from the implementation.

However, Two things annoys me with this code:

1. There is no check that T is an integral type. Is there any method for doing that? Or will that always be resolved at compile time anyway because, e.g., non-integral types will not support the modulus operation in the template code? I would just like to make it more explicit in the template function declaration that it is only intended for use with integral types.

2. The presence of the tmp variable. In Python I can write
a, b = b, a % b
and avoid tmp altogether. Is there a C++ trick to avoid the explicit tmp here, or at least encapsulate it (perhaps in some other template)?

My next quest has been to make a variant of gcd, which operates on all integral values in one of the standard container types, like list and vector. The gcd of a sequence of numbers, can be done as a fold initiated with 0, using the previous gcd as a binary function, which is being called repeatedly. In Python I would use the reduce function to do that. As I understand the C++ equivalent to this is std::accumulate found in <numeric>. So I have coded the following template function, which seems to do the job

/**
 * Returns the greatest common divisor for the sequence of 
 * integral values in a container
 */
template <class Container, class T>
T gcd(const Container& c){
        return std::accumulate(c.begin(), c.end(), 0, gcd<T>);
}

Albeit this seems to work, there are a few things which annoy me here as well.

3. The class T parameter seems redundant as it out to be resolvable from the Container type. As a consequence it seems like I have to be very specific in specifying the template parameters, i.e.,
gcd<std::list<int>, int>(myList)
from the implementation, which is tedios as it ought to be resolvable from the myList type alone, I would guess. Is there any way to change the way the template function is declared to improve on that?
4. I first tried writing simply gcd in the accumulate function, but this was not resolvable, so I had to change to gcd<T>. It seems to me that the compiler should be capable of figuring out the template type from the context, that accumulate is being called with iterators to the container type.
5. Is this a good C++ implementation in the first place? I considered another signature, where the iterators were given as the arguments to gcd instead of a reference to the container, but this seemed more tedious to call from the implementation.

Thanks,

Kim

[Disch]

1. There is no check that T is an integral type. Is there any method for doing that?

Not really. That's one of the shortcomings with templates.

iirc there were some proposed ideas to address this in the next standard (see: concepts), but I don't think they were approved.

2. The presence of the tmp variable.

That's something you should just get over.

There's nothing wrong with temp variables. Yes, it's often possible to do tricks to avoid them, but it hurts code clarity and makes your code more awkward.

3. The class T parameter seems redundant as it out to be resolvable from the Container type.

T is re-typedef'd in the std containers for just this reason. Instead of using 'T', you can use 'typename Container::value_type'. It's wordy, yes, but it allows you to remove the T from the template call:

template <class Container>
typename Container::value_type gcd(const Container& c){
    return std::accumulate(c.begin(), c.end(), 0, gcd<typename Container::value_type>);
}

(nevermind that this function will conflict with your other gcd template. You'll probably have to name it something else)

Or... what might be simpler... since Container's type can be determined by the function call, you could put it after T:

template <class T, class Container>
T gcd(const Container& c){
    return std::accumulate(c.begin(), c.end(), 0, gcd<T>);
}

Note the latter can be called like so:

std::list<int> mylist;
int foo = gcd<int>(mylist);  // no need to specify < std::list<int> > 

But the former (the typename Container::value_type version) would be easier to call because you wouldn't have to specify anything:

int foo = gcd(mylist); // OK with the former 

5. Is this a good C++ implementation in the first place?

Yes and no.

Yes: it's convenient if you were going to call this function with containers.

No: it makes more assumptions about the container than is probably necessary (ie: that is has a value_type typedef, and begin() and end() functions)

The iterators as arguments signature that you suggested is the more general approach. That way you don't need a container at all. However as you mentioned it's more typing to call it when you're working with a standard container.

So it's a trade-off. Flexibility for convenience. If you don't want to choose one over the other, do both. Make one that takes iterators and another that takes a container.

[Slaunger]

1. There is no check that T is an integral type. Is there any method for doing that?

>Not really. That's one of the shortcomings with templates.

OK, I can live with that. Just wanted to know if there was a way...

2. The presence of the tmp variable.

>That's something you should just get over.

OK :-) Certainly, worse things could happen in life.

3. The class T parameter seems redundant as it out to be resolvable from the Container type.

>T is re-typedef'd in the std containers for just this reason. Instead of using 'T', you can use 'typename Container::value_type'. It's wordy, yes, but it allows you to remove the T from the template call:

template <class Container>
typename Container::value_type gcd(const Container& c){
    return std::accumulate(c.begin(), c.end(), 0, gcd<typename Container::value_type>);
}

>(nevermind that this function will conflict with your other gcd template. You'll probably have to name it something else)

Very nice, and just the kind of solution I was looking for.

I have renamed this template function to gcd_container, also to indicate it is a quite specialized "syntactical sugar" template to avoid tedios typing in the implementation (my later question).

Could one retain the original name an implement it as a template specialization (do all STL container classes inherit from some common base class, which could be declared explicitly)?

And I take your comment on-board rearding perhaps providing both an iterator and container signature template function.

And, thanks for a very nice first reponse to a C++ newbie! It was very helpful! :-)

Kim

[jsmith]

Wait...

1. There is, though it's a bit involved. Warning: this is uncompiled:

namespace 
{
    template< typename T, bool b = boost::type_traits::is_integral<T>::type >
    struct gcd_helper;

    template< typename T,  boost::true_type >
    struct gcd_helper
    {
         T operator()( T a, T b ) const
             { /* code here */ }
    };
}

template< typename T >
T gcd( T a, T b )
{
    return gcd_helper<T>()( a, b );
}

You can easily replace boost::type_traits::is_integral and boost::true_type with your own custom implementation if you don't want to use the boost type_traits library.

3. I would make the function take iterators instead of a container. That's what the STL does, in part because it allows the algorithm to work naturally with pointers (arrays).

[Slaunger]

Wait...
1. There is, though it's a bit involved. Warning: this is uncompiled:

Interesting, but involved indeed. I suppose the extra helper struct will lead to some function call overhead?

But really interesting to see this more advanced template magic. Nice to know that it exists.

3. I would make the function take iterators instead of a container. That's what the STL does, in part because it allows the algorithm to work naturally with pointers (arrays).

Yes, after also reading more about the STL containers in Stroustrup's book, the iterator call signature seems to be the most canonical form, which is best aligned with the spirit of the STL.

[jsmith]

It won't yield any overhead because gcd_helper's constructor does nothing and will be elided by the compiler, and the call to operator() can trivially be inlined.

[Slaunger]

It won't yield any overhead because gcd_helper's constructor does nothing and will be elided by the compiler, and the call to operator() can trivially be inlined.

Very nice!