Iterators and ints get confused in template parameter

[Juha Nieminen]

I'm writing an STL-style data container, and this problem is puzzling
me. The following code should demonstrate the problem:

//----------------------------------------------------------
#include <iostream>
#include <list>

template<typename T>
class MyClass
{
public:
void assign(size_t amount, const T& value)
{
std::cout << amount << " " << value << std::endl;
}

template<typename InputIterator>
void assign(InputIterator first, InputIterator last)
{
while(first != last)
{
std::cout << *first << std::endl;
++first;
}
}
};

int main()
{
std::list<int> l1, l2;
l1.assign(10, 5); // ok
l2.assign(l1.begin(), l1.end()); // ok

MyClass<int> mc;
mc.assign(l1.begin(), l1.end()); // ok
mc.assign(10, 5); // error, wrong function gets called
}
//----------------------------------------------------------

I'm using gcc 4.1.2.

I understand *why* the problem is happening. However, I don't
understand why it's not happening with std::list, and I have no idea how
to get around the problem (in the same way as std::list does).

I have looked at the std::list source code in the gcc C++ libraries,
and I don't see any fancy trick being used to differentiate between the
two assign() functions. Yet it just works with std::list, but it doesn't
work with my code.

Any pointers?

 

[puzzlecracker]

I'm writing an STL-style data container, and this problem is puzzling
me. The following code should demonstrate the problem:

//----------------------------------------------------------
#include <iostream>
#include <list>

template<typename T>
class MyClass
{
public:
void assign(size_t amount, const T& value)
{
std::cout << amount << " " << value << std::endl;
}

template<typename InputIterator>
void assign(InputIterator first, InputIterator last)
{
while(first != last)
{
std::cout << *first << std::endl;
++first;
}
}

};

int main()
{
std::list<int> l1, l2;
l1.assign(10, 5); // ok
l2.assign(l1.begin(), l1.end()); // ok

MyClass<int> mc;
mc.assign(l1.begin(), l1.end()); // ok
mc.assign(10, 5); // error, wrong function gets called}

//----------------------------------------------------------

I'm using gcc 4.1.2.

I understand *why* the problem is happening. However, I don't
understand why it's not happening with std::list, and I have no idea how
to get around the problem (in the same way as std::list does).

I have looked at the std::list source code in the gcc C++ libraries,
and I don't see any fancy trick being used to differentiate between the
two assign() functions. Yet it just works with std::list, but it doesn't
work with my code.

Any pointers?

Which function gets called?

You don't have a member function with this signature assign(int,
int ); While int is guaranteed to convert to size_t, there is no such
guarantees available for a object of class T. One solution is add
this member function to this class, another is add user-defined
conversion operator.

PuzzleCracker

 

[Juha Nieminen]

I have looked at the std::list source code in the gcc C++ libraries,
and I don't see any fancy trick being used to differentiate between the
two assign() functions.

Actually I was wrong. The assign() functions themselves don't use any
trick, but the internal functions they call seem to use some kind of
obscure template magic to differentiate between the two cases.

The code in question is filled with names starting with _ and __, for
example:

typedef typename std::__is_integer<_InputIterator>::__type _Integral;

This seems to be telling me that this is not standard library code,
but code specific to gcc (or whatever STL library it's using). Thus it
wouldn't probably be very portable to try to copy this implementation
verbatim.

Any suggestions how I could solve this problem with standard STL code
only, and preferably without having to reimplement enormous libraries?
(Also I wouldn't want to make specializations for assign() for each
possible integral type.)

 

[James Kanze]

Actually I was wrong. The assign() functions themselves don't
use any trick, but the internal functions they call seem to
use some kind of obscure template magic to differentiate
between the two cases.

The code in question is filled with names starting with _ and
__, for example:

typedef typename std::__is_integer<_InputIterator>::__type _Integral;

This seems to be telling me that this is not standard library code,

Why? It's part of the implementation, so it's bound to use
funny names. But it's part of the implementation of the
standard library.

but code specific to gcc (or whatever STL library it's using).
Thus it wouldn't probably be very portable to try to copy this
implementation verbatim.

Maybe, maybe not. It's possible that the g++ library uses some
special g++ extensions here, but somehow I doubt it. And it
certainly can be done in standard C++. (The standard requires
it be done somehow, of course.)

Any suggestions how I could solve this problem with standard
STL code only, and preferably without having to reimplement
enormous libraries? (Also I wouldn't want to make
specializations for assign() for each possible integral type.)

You only have to specialize some discriminator template for each
possible integral type. That descrimator type has a typedef,
you call a function using an argument based on that typedef, and
operator overloading does the rest. Something along the lines
(untested):

class True {} ;
class False {} ;

template< typename T >
struct IntegerDiscriminator
{
typedef False Type ;
} ;

template<>
struct IntegerDiscriminator< int >
{
typdef True Type ;
}

// ...

And then:

template< typename T >
class MyClass
{
public:
void assign( size_t count, T const& value ) ;
template< typename ForwardIterator >
void assign( ForwardIterator begin,
ForwardIterator end )
{
doAssign( begin, end, IntegerDiscriminator< T

::type() ) ;

}

private:
void doAssign( size_t count, T value, True )
{
assign( count, value ) ;
}
template< typename ForwardIterator >
void doAssign( ForwardIterator begin,
ForwardIterator end,
False )
{
while ( begin != end ) ...
}
} ;

Or something like that. For all the details, see the
Vandevoorde and Josuttis.

 

[Juha Nieminen]

Why?

Does the C++ standard really specify templates like std::__is_integer?

If not, then the code above is specific to the library in question and
thus not portable all in itself.

It's part of the implementation, so it's bound to use
funny names. But it's part of the implementation of the
standard library.

My point is: I want to replicate the functionality, but I can't just
copy it verbatim from gcc's library because it uses non-standard types
like the ones in the above example line.

Maybe, maybe not.

Unless the C++ standard specifies things like std::__is_integer, the
answer is no.

The only thing I could do is to copy the functionality of that type
(and whatever it might use) into my code, but I was wondering if there
isn't any easier way.

It's possible that the g++ library uses some
special g++ extensions here, but somehow I doubt it. And it
certainly can be done in standard C++. (The standard requires
it be done somehow, of course.)

I don't think you really understood what I meant.

template<>
struct IntegerDiscriminator< int >
{
typdef True Type ;
}

Doesn't that only take care of the case where the parameter is of type
'int'? What about unsigned int, long, unsigned long, short, unsigned
short, char, signed char, unsigned char, long long, unsigned long long...

Or something like that. For all the details, see the
Vandevoorde and Josuttis.

I didn't understand that.

 

[James Kanze]

Does the C++ standard really specify templates like std::__is_integer?

The C++ standard does not specify how any of the standard
containers are implemented. It does require the implementation
to discriminate between integral types and other types in the
two iterator template member functions.

If not, then the code above is specific to the library in
question and thus not portable all in itself.

Obviously, such code is specific to the library. That doesn't
mean that it uses compiler extensions, and isn't "portable"
(except that user code doesn't have the right to use names
beginning with __). It's quite possible to write something like
__is_integer in portable C++, and I'd be fairly surprised if the
implementation in the g++ library wasn't in portable C++ (again,
modulo the fact that the names aren't legal in user code).

My point is: I want to replicate the functionality, but I
can't just copy it verbatim from gcc's library because it uses
non-standard types like the ones in the above example line.

And my point is: I don't see your point. Why can't you copy
__is_integer, changing the names, and use it?

Unless the C++ standard specifies things like
std::__is_integer, the answer is no.

Why? I'm pretty sure that the answer is yes.

The only thing I could do is to copy the functionality of that
type (and whatever it might use) into my code, but I was
wondering if there isn't any easier way.

Well, rather than copying, the actual code isn't too difficult
to understand, so it might be worth implementing it yourself,
for pedagogical reasons. Otherwise, there are implementations
of it in Boost, and doubtlessly elsewhere as well; the Boost
implementation is part of TR1, if I'm not mistaken, and will be
part of the next standard. (But I don't follow the library
issues too closely, so I could be wrong here.)

I don't think you really understood what I meant.

The standard says that when one of the two iterator template
functions is instantiated, if the instantiation type is an
integral type (and thus, not an iterator), the instantiation
should behave as if the corresponding non-template function
taking a size_t as its first argument was called. That means
that every implementation must somehow make it work.

At the time this clause was adopted, it was done so because it
was clear to the authors that it could be done in standard C++,
without any compiler tricks.

Doesn't that only take care of the case where the parameter is
of type 'int'? What about unsigned int, long, unsigned long,
short, unsigned short, char, signed char, unsigned char, long
long, unsigned long long...

Obviously. I thought I'd put a ... after it, to indicate that
you needed to extend it.

But you only have to do it once. You can use
IntegerDiscriminator for all such functions.

I didn't understand that.

If you're doing anything but the simplest templates, you should
definitely read " C++ Templates - The Complete Guide", by David
Vandevoorde and Nicolai Josuttis (ISBN 0-201-73484-2). It is
the reference for everything concerning templates, and it has
a complete chapter concerning just such problems. It's one of
those musts, without which your technical library isn't
complete.

 

[Juha Nieminen]

Could perhaps <tr1/type_traits> be used for this purpose?

 

[Kai-Uwe Bux]

Could perhaps <tr1/type_traits> be used for this purpose?

Yes.


Best

Kai-Uwe Bux

 

[Juha Nieminen]

Yes.

This seems to work. Does anyone have any objections (besides it
using tr1)?

//---------------------------------------------------------------------------
#include <iostream>
#include <list>
#include <tr1/type_traits>

template<typename T>
class MyClass
{
template<typename ValueType>
void dispatchAssign(ValueType amount, ValueType value,
std::tr1::true_type)
{
std::cout << amount << " " << value << std::endl;
}

template<typename InputIterator>
void dispatchAssign(InputIterator first, InputIterator last,
std::tr1::false_type)
{
while(first != last)
{
std::cout << *first << std::endl;
++first;
}
}

public:
void assign(size_t amount, const T& value)
{
dispatchAssign(amount, value, std::tr1::true_type());
}

template<typename InputIterator>
void assign(InputIterator first, InputIterator last)
{
dispatchAssign(first, last,
std::tr1::is_integral<InputIterator>());
}
};

int main()
{
std::list<int> l1, l2;
l1.assign(10, 5);
l2.assign(l1.begin(), l1.end());

MyClass<int> mc;
mc.assign(l1.begin(), l1.end());
mc.assign(10, 5);
}
//---------------------------------------------------------------------------

 

[James Kanze]

Could perhaps <tr1/type_traits> be used for this purpose?

Certainly. I'm not sure, but I think the code in the g++
library is inspired from this (or from an earlier Boost
version). If it isn't simply a copy with the names changed.

 

[Bart van Ingen Schenau]

This seems to work. Does anyone have any objections (besides it
using tr1)?

Yes. It won't work with types that are not convertable from int.
Try it with this class:
class Bar {};
ostream& operator<<(ostream& os, const Bar&){ os << "Bar";}

//---------------------------------------------------------------------------
#include <iostream>
#include <list>
#include <tr1/type_traits>

template<typename T>
class MyClass
{
template<typename ValueType>
void dispatchAssign(ValueType amount, ValueType value,
std::tr1::true_type)

For it to work with other types than integers, this should be
void dispatchAssign(size_t amount, const T& value,
std::tr1::true_type)

<snip>

Bart v Ingen Schenau