algorith implementation

**Frederick Gotham** · Aug 21 '06, 09:25 PM

Re: algorith implementation

Bo Persson posted:

I don't think it is obvious how to select a proper integral type for
n, when you don't know what type Size might be. In this case, if n_arg
happens to be negative, converting it to size_t will not work well.

Perhaps something like this:

(It doesn't compile but you get the idea)

enum MyEnum { a,b,c,d,e,f };

template<class T, bool is_signed = ((T)-1 < 0)>
void Func(T arg);

template<class T>
void Func<T,true>(T arg)
{
long i = arg;
}

template<class T>
void Func<T,false>(T arg)
{
long unsigned i = arg;
}

int main()
{
MyEnum obj;

Func(obj);
}

--

Frederick Gotham

**Kai-Uwe Bux** · Aug 21 '06, 09:55 PM

Re: algorith implementation

Bo Persson wrote:

>
"Fraser Ross" <fraserATmember s.v21.co.ukskre v i meddelandet
news:1156174651 _15@sp6iad.supe rfeed.net...

>>A suitable implementation is easy enough to make. It surprises me
>>how
>much library code uses pre increment and decrement operators. They
>can
>be less efficient.
>>
>Fraser.

>
>
I don't think it is obvious how to select a proper integral type for
n, when you don't know what type Size might be. In this case, if n_arg
happens to be negative, converting it to size_t will not work well.
>
If Size happens to be a class type with a user defined convertion
operator, how do we know what type(s) it will convert to? Signed, or
unsigned?

Who says that it is necessary to make a guess as to whether Size converts to
signed or unsigned? What about:

template < typename OutIter, typename Size, typename T >
void fill_n ( OutIter first, Size n, const T & value ) {
for ( std::size_t i = 0; i < n; ++i ) {
*first = value;
++first;
}
}

One could use specialization tricks to save the local variable when Size is
an arithmetic type.

> void fill_n (OutputIterator first, Size n_arg, const T& value)
> {
> size_t n = n_arg; ...
>>
>, probably.
>>
>>>
>>That would fail for negative values instead.
>>>
>> This is tricky. :-)

Best

Kai-Uwe Bux

**Bo Persson** · Aug 21 '06, 09:55 PM

Re: algorith implementation

"Frederick Gotham" <fgothamNO@SPAM .comskrev i meddelandet
news:1JpGg.1292 4$j7.325132@new s.indigo.ie...

Bo Persson posted:
>
>

>I don't think it is obvious how to select a proper integral type
>for
>n, when you don't know what type Size might be. In this case, if
>n_arg
>happens to be negative, converting it to size_t will not work well.

>
>
Perhaps something like this:
>
(It doesn't compile but you get the idea)

Yes, it solves some of the problems, but not all.

How do we separate

enum E1 { a = -42 };

from

enum E2 { a = UINT_MAX};

??

Or, even worse

struct T1
{
operator int();
};

from

struct T2
{
operator unsigned long();
};

??

I don't know? Perhaps this really is a defect in the standard?

>
enum MyEnum { a,b,c,d,e,f };
>
template<class T, bool is_signed = ((T)-1 < 0)>
void Func(T arg);

This will not work for the structs, that are convertible *to* an
integral type, but not *from*.

Bo Persson

>
template<class T>
void Func<T,true>(T arg)
{
long i = arg;
}
>
template<class T>
void Func<T,false>(T arg)
{
long unsigned i = arg;
}
>
int main()
{
MyEnum obj;
>
Func(obj);
}
>
--
>
Frederick Gotham

**Bo Persson** · Aug 21 '06, 10:35 PM

Re: algorith implementation

"Kai-Uwe Bux" <jkherciueh@gmx .netskrev i meddelandet
news:ecda6a$bb9 $1@murdoch.acc. Virginia.EDU...

Bo Persson wrote:
>

>>
>"Fraser Ross" <fraserATmember s.v21.co.ukskre v i meddelandet
>news:115617465 1_15@sp6iad.sup erfeed.net...

>>>A suitable implementation is easy enough to make. It surprises me
>>>how
>>much library code uses pre increment and decrement operators.
>>They
>>can
>>be less efficient.
>>>
>>Fraser.

>>
>>
>I don't think it is obvious how to select a proper integral type
>for
>n, when you don't know what type Size might be. In this case, if
>n_arg
>happens to be negative, converting it to size_t will not work well.
>>
>If Size happens to be a class type with a user defined convertion
>operator, how do we know what type(s) it will convert to? Signed,
>or
>unsigned?

>
Who says that it is necessary to make a guess as to whether Size
converts to
signed or unsigned? What about:
>
template < typename OutIter, typename Size, typename T >
void fill_n ( OutIter first, Size n, const T & value ) {
for ( std::size_t i = 0; i < n; ++i ) {
*first = value;
++first;
}
}
>

Yes, we are getting closer. :-)

My compiler would complain about a signed/unsigned comparison when
Size really is signed.

One could use specialization tricks to save the local variable when
Size is
an arithmetic type.

Perhaps we could have an overload

template < typename OutIter, typename T >
void fill_n ( OutIter first, std::size_t n, const T & value );

to catch the cases where std::size_t is the proper type?

That would leave the signed case for the original version. Wouldn't
that work?

Bo Persson

**Kai-Uwe Bux** · Aug 21 '06, 11:05 PM

Re: algorith implementation

Bo Persson wrote:

>
"Kai-Uwe Bux" <jkherciueh@gmx .netskrev i meddelandet
news:ecda6a$bb9 $1@murdoch.acc. Virginia.EDU...

>Bo Persson wrote:
>>

>>>
>>"Fraser Ross" <fraserATmember s.v21.co.ukskre v i meddelandet
>>news:11561746 51_15@sp6iad.su perfeed.net...
>>>>A suitable implementation is easy enough to make. It surprises me
>>>>how
>>>much library code uses pre increment and decrement operators.
>>>They
>>>can
>>>be less efficient.
>>>>
>>>Fraser.
>>>
>>>
>>I don't think it is obvious how to select a proper integral type
>>for
>>n, when you don't know what type Size might be. In this case, if
>>n_arg
>>happens to be negative, converting it to size_t will not work well.
>>>
>>If Size happens to be a class type with a user defined convertion
>>operator, how do we know what type(s) it will convert to? Signed,
>>or
>>unsigned?

>>
>Who says that it is necessary to make a guess as to whether Size
>converts to
>signed or unsigned? What about:
>>
> template < typename OutIter, typename Size, typename T >
> void fill_n ( OutIter first, Size n, const T & value ) {
> for ( std::size_t i = 0; i < n; ++i ) {
> *first = value;
> ++first;
> }
> }
>>

>
Yes, we are getting closer. :-)
>
My compiler would complain about a signed/unsigned comparison when
Size really is signed.

It should not. Such comparison is handled gracefully by promotion rules. I
think, the code is required to compile.

>One could use specialization tricks to save the local variable when
>Size is an arithmetic type.

>
Perhaps we could have an overload
>
template < typename OutIter, typename T >
void fill_n ( OutIter first, std::size_t n, const T & value );
>
to catch the cases where std::size_t is the proper type?
>
That would leave the signed case for the original version. Wouldn't
that work?

I would add overloads for all integral types.

Best

Kai-Uwe Bux

**Bo Persson** · Aug 22 '06, 12:15 AM

Re: algorith implementation

"Kai-Uwe Bux" <jkherciueh@gmx .netskrev i meddelandet
news:ecde88$co2 $2@murdoch.acc. Virginia.EDU...

Bo Persson wrote:
>

>>
>"Kai-Uwe Bux" <jkherciueh@gmx .netskrev i meddelandet
>news:ecda6a$bb 9$1@murdoch.acc .Virginia.EDU.. .

>>Bo Persson wrote:
>>>
>>>>
>>>"Fraser Ross" <fraserATmember s.v21.co.ukskre v i meddelandet
>>>news:1156174 651_15@sp6iad.s uperfeed.net...
>>>>>A suitable implementation is easy enough to make. It surprises
>>>>>me
>>>>>how
>>>>much library code uses pre increment and decrement operators.
>>>>They
>>>>can
>>>>be less efficient.
>>>>>
>>>>Fraser.
>>>>
>>>>
>>>I don't think it is obvious how to select a proper integral type
>>>for
>>>n, when you don't know what type Size might be. In this case, if
>>>n_arg
>>>happens to be negative, converting it to size_t will not work
>>>well.
>>>>
>>>If Size happens to be a class type with a user defined convertion
>>>operator, how do we know what type(s) it will convert to? Signed,
>>>or
>>>unsigned?
>>>
>>Who says that it is necessary to make a guess as to whether Size
>>converts to
>>signed or unsigned? What about:
>>>
>> template < typename OutIter, typename Size, typename T >
>> void fill_n ( OutIter first, Size n, const T & value ) {
>> for ( std::size_t i = 0; i < n; ++i ) {
>> *first = value;
>> ++first;
>> }
>> }
>>>

>>
>Yes, we are getting closer. :-)
>>
>My compiler would complain about a signed/unsigned comparison when
>Size really is signed.

>
It should not. Such comparison is handled gracefully by promotion
rules. I
think, the code is required to compile.

It does with a warning, but the result is incorrect. :-(

If Size is ptrdiff_t for example, and n is negative, comparing to a
size_t doesn't work.

We are on the right track though, and I think this one could work:

template < typename OutIter, typename Size, typename T >
void fill_n ( OutIter first, Size n, const T & value ) {
if (0 < n) // n must be positive
{
for ( std::size_t count = n; 0 < count; --count ) {
*first = value;
++first;
}
}
}

If we sort out the possibly negative n first, the remaining values
must be convertible to size_t (assuming size_t is the largest unsigned
type :-).

Bo Persson

**Frederick Gotham** · Aug 22 '06, 12:25 AM

Re: algorith implementation

Bo Persson posted:

My compiler would complain about a signed/unsigned comparison when
Size really is signed.

Simply cast one of them -- I regularly use casts to suppress compiler
warnings, e.g.:

for(size_t i = MAX - 1; i != (size_t)-1; --i)

--

Frederick Gotham

**Bo Persson** · Aug 22 '06, 12:35 AM

Re: algorith implementation

"Frederick Gotham" <fgothamNO@SPAM .comskrev i meddelandet
news:CesGg.1292 6$j7.325394@new s.indigo.ie...

Bo Persson posted:
>

>My compiler would complain about a signed/unsigned comparison when
>Size really is signed.

>
>
Simply cast one of them -- I regularly use casts to suppress
compiler
warnings, e.g.:
>
for(size_t i = MAX - 1; i != (size_t)-1; --i)
>

That just works sometimes.

If the signed value really is negative, it doesn't help.

int x = -5;
unsigned y = UINT_MAX;

if (x < y)
...

Bo Persson

**Victor Bazarov** · Aug 22 '06, 12:45 AM

Re: algorith implementation

Bo Persson wrote:

"Frederick Gotham" <fgothamNO@SPAM .comskrev i meddelandet
news:CesGg.1292 6$j7.325394@new s.indigo.ie...

>Bo Persson posted:
>>

>>My compiler would complain about a signed/unsigned comparison when
>>Size really is signed.

>>
>>
>Simply cast one of them -- I regularly use casts to suppress
>compiler
>warnings, e.g.:
>>
> for(size_t i = MAX - 1; i != (size_t)-1; --i)
>>

>
That just works sometimes.
>
If the signed value really is negative, it doesn't help.
>
int x = -5;
unsigned y = UINT_MAX;
>
if (x < y)
...

What is the expected result? Since -5 converted to unsigned is the
same as unsigned((UINT_ MAX + 1) - 5), it's less than UINT_MAX. If
both of them are promoted to 'long', -5 is still less than UINT_MAX
which is positive. If they are promoted to unsigned long, see the
unsigned thing above.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

**Victor Bazarov** · Aug 22 '06, 12:45 AM

Re: algorith implementation

Victor Bazarov wrote:

[..] Since -5 converted to unsigned is the
same as unsigned((UINT_ MAX + 1) - 5)[..]

Now that I'm thinking about it again, it's probably implementation-
defined and not that simple... Sounded plausible, didn't it? :-)

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

**Kai-Uwe Bux** · Aug 22 '06, 07:25 AM

Re: algorith implementation

Bo Persson wrote:

>
"Kai-Uwe Bux" <jkherciueh@gmx .netskrev i meddelandet
news:ecde88$co2 $2@murdoch.acc. Virginia.EDU...

>Bo Persson wrote:
>>

>>>
>>"Kai-Uwe Bux" <jkherciueh@gmx .netskrev i meddelandet
>>news:ecda6a$b b9$1@murdoch.ac c.Virginia.EDU. ..
>>>Bo Persson wrote:
>>>>
>>>>>
>>>>"Fraser Ross" <fraserATmember s.v21.co.ukskre v i meddelandet
>>>>news:115617 4651_15@sp6iad. superfeed.net.. .
>>>>>>A suitable implementation is easy enough to make. It surprises
>>>>>>me
>>>>>>how
>>>>>much library code uses pre increment and decrement operators.
>>>>>They
>>>>>can
>>>>>be less efficient.
>>>>>>
>>>>>Fraser.
>>>>>
>>>>>
>>>>I don't think it is obvious how to select a proper integral type
>>>>for
>>>>n, when you don't know what type Size might be. In this case, if
>>>>n_arg
>>>>happens to be negative, converting it to size_t will not work
>>>>well.
>>>>>
>>>>If Size happens to be a class type with a user defined convertion
>>>>operator, how do we know what type(s) it will convert to? Signed,
>>>>or
>>>>unsigned?
>>>>
>>>Who says that it is necessary to make a guess as to whether Size
>>>converts to
>>>signed or unsigned? What about:
>>>>
>>> template < typename OutIter, typename Size, typename T >
>>> void fill_n ( OutIter first, Size n, const T & value ) {
>>> for ( std::size_t i = 0; i < n; ++i ) {
>>> *first = value;
>>> ++first;
>>> }
>>> }
>>>>
>>>
>>Yes, we are getting closer. :-)
>>>
>>My compiler would complain about a signed/unsigned comparison when
>>Size really is signed.

>>
>It should not. Such comparison is handled gracefully by promotion
>rules. I
>think, the code is required to compile.

>
It does with a warning, but the result is incorrect. :-(
>
If Size is ptrdiff_t for example, and n is negative, comparing to a
size_t doesn't work.

You'r right. My bad.

We are on the right track though, and I think this one could work:
>
template < typename OutIter, typename Size, typename T >
void fill_n ( OutIter first, Size n, const T & value ) {
if (0 < n) // n must be positive
{
for ( std::size_t count = n; 0 < count; --count ) {
*first = value;
++first;
}
}
}
>
If we sort out the possibly negative n first, the remaining values
must be convertible to size_t (assuming size_t is the largest unsigned
type :-).

Looks good. Maybe, I would do

template < typename OutIter, typename Size, typename T >
void fill_n ( OutIter first, Size n, const T & value ) {
if (0 <= n) // n must not be negative
{
for ( std::size_t count = n; 0 < count; --count ) {
*first = value;
++first;
}
}
}

to make it easier for the compiler to optimize the if-statement away if Size
is an unsigned type.

Best

Kai-Uwe Bux

**Fraser Ross** · Aug 22 '06, 09:45 AM

Re: algorith implementation

template <class OutputIterator, class Size, class T>
void fill_n (OutputIterator first, Size n, const T& value) {
if (1 <= n) {
size_t m= n;
do {
--m;
*first= value;
++first;
}
while (1 <= m);
}
};
I had roughly the same code. I would have written almost the same as
you after noticing that a for statement can be used. The optimisation
though I wouldn't have known about.

Fraser.

template < typename OutIter, typename Size, typename T >
void fill_n ( OutIter first, Size n, const T & value ) {
if (0 <= n) // n must not be negative
{
for ( std::size_t count = n; 0 < count; --count ) {
*first = value;
++first;
}
}
}
>
to make it easier for the compiler to optimize the if-statement away

if Size

is an unsigned type.

Posted Via Usenet.com Premium Usenet Newsgroup Services
----------------------------------------------------------
** SPEED ** RETENTION ** COMPLETION ** ANONYMITY **
----------------------------------------------------------

Best Usenet Service Providers 2026

http://www.usenet.com

Best Usenet Service Providers 2026 ranked by Newsgroup Access Newsservers, Usenet Search, Features & Free Trial. Add VPN for privacy.

algorith implementation

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment