Selecting an overloaded (potentially templated) constructor.

[Matthias]

Dear newsgroup.

This is my first post here, I hope I'm doing it right.

I wrote a circular iterator class which works as I intended but there
is a little quirk left which maybe you can help me to get rid of:

I want the constructor of my class to accept an iterator range and an
optional current iterator which defaults to the start iterator.
Additionally, it should accept an STL-style container (which will be
used from .begin() to .end()) and an optional current iterator which
defaults to the .begin()-iterator.

The problem is, when I use an array of non-const data to feed my class
(having a pointer to const data as a template argument), the compiler
(GCC) seems to pick the wrong constructor.

I reduced the problem to the following (hopefully minimal) example:

template <typename T>
struct my_class
{
my_class(const T& begin, const T& end, const T& current = T()) :
_begin(begin), _end(end), _current(current != T() ? current :
begin)
{}
template <typename Container> explicit
my_class(Container& container, const T& current = T()) :
_begin(container.begin()), _end(container.end()),
_current(current != T() ? current : _begin)
{}
private:
const T _begin;
const T _end;
T _current;
};

int main()
{
float array[3] = { 1.5, 2.5, 3.5 };
my_class<float*> first(array, array + 3);
// this doesn't work:
my_class<const float*> second(array, array + 3);
// this, however, does:
my_class<const float*> third(&array[0], array + 3);
// even this works:
my_class<const float*> fourth(array + 0, array + 3);
// and with non-const data it also works:
my_class<float*> fifth(array, array + 3);
}

The error message (in the line where "second" is initialized) is:
error: request for member 'begin' in 'container', which is of non-
class type 'float [3]'

The question is, I guess, how can I tell the compiler, that "array" is
not a container but just a pointer to the first array element.

I'm sure I could avoid this special case in my code, but somehow I got
curious ...

Thanks in advance for your help,
Matthias

 

[Jim Langston]

Dear newsgroup.

This is my first post here, I hope I'm doing it right.

I wrote a circular iterator class which works as I intended but there
is a little quirk left which maybe you can help me to get rid of:

I want the constructor of my class to accept an iterator range and an
optional current iterator which defaults to the start iterator.
Additionally, it should accept an STL-style container (which will be
used from .begin() to .end()) and an optional current iterator which
defaults to the .begin()-iterator.

The problem is, when I use an array of non-const data to feed my class
(having a pointer to const data as a template argument), the compiler
(GCC) seems to pick the wrong constructor.

I reduced the problem to the following (hopefully minimal) example:

template <typename T>
struct my_class
{
my_class(const T& begin, const T& end, const T& current = T()) :
_begin(begin), _end(end), _current(current != T() ? current :
begin)
{}
template <typename Container> explicit
my_class(Container& container, const T& current = T()) :
_begin(container.begin()), _end(container.end()),
_current(current != T() ? current : _begin)
{}
private:
const T _begin;
const T _end;
T _current;
};

int main()
{
float array[3] = { 1.5, 2.5, 3.5 };
my_class<float*> first(array, array + 3);
// this doesn't work:
my_class<const float*> second(array, array + 3);
// this, however, does:
my_class<const float*> third(&array[0], array + 3);
// even this works:
my_class<const float*> fourth(array + 0, array + 3);
// and with non-const data it also works:
my_class<float*> fifth(array, array + 3);
}

The error message (in the line where "second" is initialized) is:
error: request for member 'begin' in 'container', which is of non-
class type 'float [3]'

The question is, I guess, how can I tell the compiler, that "array" is
not a container but just a pointer to the first array element.

I'm sure I could avoid this special case in my code, but somehow I got
curious ...

Well, it's pretty much telling you, this is a problem:

my_class(Container& container, const T& current = T()) :
_begin(container.begin()), _end(container.end()),
_current(current != T() ? current : _begin)

a float array doesn't have a .begin(). It does, however, have a beginning
iterator, I.E. &array[0]
Instead of using container.begin() you'll need to accept the beginning
iterator and ending iterator as parameters.

If you look at anything in <algorithm> they aren't requesting container
references, they are requesting beginning and ending iterators (I.E.
std::copy). You should probalby do the same. If you accept beginning and
ending iterators any type of container can be used, STL or naked arrays or
anything that you can get a beginning iterator or pointer to and an ending
iterator or pointer.

 

[Andrey Tarasevich]

...
The question is, I guess, how can I tell the compiler, that "array" is
not a container but just a pointer to the first array element.
...

In this case overload resolution finds two viable functions to call.

The first function (your "range" constructor) has its parameter types already
fixed (by the class template parameter 'T'), while the second function (your
"container" constructor) has only it's second parameter type fixed, while the
first parameter type ('Container') is fully flexible. This means that the
compiler can (and will) always derive the 'Container' type so that it matches
the type of the argument exactly, and therefore never requires a conversion.

In this case the overload resolution will proceed roughly as follows:

1. If the type of the first argument is an exact match to type 'T' (or close
enough), then the first function requires no conversion. The second function
will also require no conversion, but since the first function is a non-template
one it wins over.

This is why

my_class<float*> first(array, array + 3);

call compiles fine.

2. If the first function requires any conversion for its first argument, it will
lose to the second function, since the second function requires no conversion.

This is why

my_class<const float*> second(array, array + 3);

call fails to compile.

The

my_class<const float*> third(&array[0], array + 3);
my_class<const float*> fourth(array + 0, array + 3);

calls compile for a different reason: the first parameter in not an lvalue and,
therefore, cannot be bound to a non-constant reference. This immediately
excludes the second constructor from the list of viable functions.

In your case (assuming that the code remain unchanged) the way to fix the
ill-formed call is either

- make sure that the first parameter is not an lvalue

my_class<const float*> third((float*) array, array);

(you also posted a few examples yourself)

or

- make sure that the first parameter type matches type 'T' exactly, as in

float* p = array;
my_class<const float*> second(p, p + 3); // ERROR

const float* p = array;
my_class<const float*> second(p, p + 3); // OK

Of course, all these methods are far from being elegant. The better approach
would be to change the declarations of your functions to somehow remove the
potential ambiguity.

 

[Andrey Tarasevich]

...
The question is, I guess, how can I tell the compiler, that "array" is
not a container but just a pointer to the first array element.
...

(In addition to what I said in my previous message)

You can also force the compiler to choose the correct constructor by using
SFINAE technique, although in my opinion it would be an overkill in this case.

For example, assume that you have some kind of iterator detector traits

is_iterator<T>::value

which evaluates to 1 for iterator types and to 0 for non-iterator types. Then
you can declare your template constructor as follows

template <typename Container>
explicit my_class(Container& container,
const T& current = T(),
char (*)[1 - is_iterator<Container>::value] = NULL)

If I did everything correctly, specialization failure should ensure that the
template constructor is not used with iterator types.

Of course for that you are going to need that 'is_iterator' trait (or,
alternatively, 'is_container' one). Maybe boost offers something like that...
Maybe not.

 

[brian tyler]

Unless you are going to do something fancy with type traits (http://
www.boost.org/doc/html/boost_typetraits.html), then if you want to be
able to pass a generic iterator (including a pointer) to a function,
you need to do it by value since "const int*&," for example, doesn't
make sense as int* is already a reference to memory.

If you want to pass by reference then you can use the boost::ref
wrapper http://www.boost.org/doc/html/ref.html

From what you are doing, it looks like you probably don't want the
container overload, since this automatically implies that your
container accesses it's iterators through begin and end, what if you
wanted to iterate in reverse?

If you want to detect an array type in your container overload then
you can do this using (again) the boost type-traits library, still it
seems like a hack.

 

[Matthias]

Hi Jim.

Thanks for your really fast response!

Matthias wrote: [...]

template <typename T>
struct my_class
{
my_class(const T& begin, const T& end, const T& current = T()) :
_begin(begin), _end(end), _current(current != T() ? current :
begin)
{}
template <typename Container> explicit
my_class(Container& container, const T& current = T()) :
_begin(container.begin()), _end(container.end()),
_current(current != T() ? current : _begin)
{}
private:
const T _begin;
const T _end;
T _current;
};

int main()
{
float array[3] = { 1.5, 2.5, 3.5 };
my_class<float*> first(array, array + 3);
// this doesn't work:
my_class<const float*> second(array, array + 3);
// this, however, does:
my_class<const float*> third(&array[0], array + 3);
// even this works:
my_class<const float*> fourth(array + 0, array + 3);
// and with non-const data it also works:
my_class<float*> fifth(array, array + 3);
}

The error message (in the line where "second" is initialized) is:
error: request for member 'begin' in 'container', which is of non-
class type 'float [3]'

The question is, I guess, how can I tell the compiler, that "array" is
not a container but just a pointer to the first array element.

Well, it's pretty much telling you, this is a problem:

my_class(Container& container, const T& current = T()) :
_begin(container.begin()), _end(container.end()),
_current(current != T() ? current : _begin)

a float array doesn't have a .begin(). It does, however, have a beginning
iterator, I.E. &array[0]
Instead of using container.begin() you'll need to accept the beginning
iterator and ending iterator as parameters.

Yes, that's why I wrote the other constructor which accepts beginning
and end iterators.
The reason why it's not selected was already explained in Andrey's
post.

If you look at anything in <algorithm> they aren't requesting container
references, they are requesting beginning and ending iterators (I.E.
std::copy). You should probalby do the same. If you accept beginning and
ending iterators any type of container can be used, STL or naked arrays or
anything that you can get a beginning iterator or pointer to and an ending
iterator or pointer.

The original and main constructor was the one taking the iterators. I
just wanted to add the other constructor as a shortcut because I would
use it most of the times with .begin() and .end() of a container
anyway.

Best regards,
Matthias

 

[Matthias]

(In addition to what I said in my previous message)

Thanks for both of your replies.
The explanation in the previous one was very enlightening.

You can also force the compiler to choose the correct constructor by using
SFINAE technique, although in my opinion it would be an overkill in this case.

I didn't know about this. Sounds very interesting, but maybe it's
really overkill.

For example, assume that you have some kind of iterator detector traits

is_iterator<T>::value

which evaluates to 1 for iterator types and to 0 for non-iterator types. Then
you can declare your template constructor as follows

template <typename Container>
explicit my_class(Container& container,
const T& current = T(),
char (*)[1 - is_iterator<Container>::value] = NULL)

If I did everything correctly, specialization failure should ensure that the
template constructor is not used with iterator types.

Of course for that you are going to need that 'is_iterator' trait (or,
alternatively, 'is_container' one). Maybe boost offers something like that...
Maybe not.

I did a little search, and there are several suggestions for an
is_container trait, but all I found seem either incomplete or too
complicated (for me).
Same for is_iterator.

I found also the has_begin trait in boost, but I didn't understand the
code, it's a little too fancy for my poor knowledge in generic
programming.
And I didn't want to include boost just because of this minor feature.

If there is a reasonably easy way to realize self-contained has_begin
and has_end traits and to select the constructor based on these, I
would appreciate your suggestions, if not, I might as well just get
rid of the container-constructor and just keep the one with the
iterator range.

Best regards,
Matthias

 

[Matthias]

Unless you are going to do something fancy with type traits (http://www.boost.org/doc/html/boost_typetraits.html), then if you want to be
able to pass a generic iterator (including a pointer) to a function,
you need to do it by value since "const int*&," for example, doesn't
make sense as int* is already a reference to memory.

Thanks for this hint. I didn't really think of this and used a const
reference out of habit.
I will change this to "by value".

If you want to pass by reference then you can use the boost::ref
wrapper http://www.boost.org/doc/html/ref.html

I don't insist on reference, "by value" is OK for me.

From what you are doing, it looks like you probably don't want the
container overload, since this automatically implies that your
container accesses it's iterators through begin and end, what if you
wanted to iterate in reverse?

I didn't consider reverse iterators.
I'll have to check if my class works with them.
The container-constructor would be just a shortcut for one special
case, so I wouldn't mind if reverse iteration is not possible with it.

If you want to detect an array type in your container overload then
you can do this using (again) the boost type-traits library, still it
seems like a hack.

I also got the impression that everything I try to solve this problem
degenerates into an ugly hack.

I'd just hoped there would be a simple and elegant solution, but maybe
the most simple and elegant solution would be to just throw away the
second constructor remembering the famous quote by Antoine de Saint-
Exupéry: "A designer knows he has achieved perfection not when there
is nothing left to add, but when there is nothing left to take away."

Best regards,
Matthias

 

[brian tyler]

Sounds like you are on the right track.

Generic programming is so tough because you need to deal with many
cases at once, most of the time those cases work as expected, but
sometimes, as with your case of the array things are a little
different. I think the elegant solution, as you put it, probably the
one which deals with as many cases as possible using the same code.

One thing you might want to consider is what happens when you pass in
const iterators: static_cast<const
container_type&>(container).begin(), is this allowed or do they need
to be able to mutate your container?

Regards,
Brian