Implementing library algorithms

[Pete]

I'm doing exercise 8-2 from "Accelerate d C++" where we're supposed to
implement library algorithms, trying to minimize the number of iterator
operations. I have two questions so far.



First, it took me a while to figure out how to get accumulate() to compile
correctly:

// begin and begin2 must both be input iterators.
//
template< class In, class Out >
Out accumulate( In begin, const In end, Out )
{
Out ret = 0;

while ( begin != end )
ret += *begin++;

return ret;
}

The problem is that I don't understand the function's signature. When we
define a function, each argument needs a type and an argument name. So this
makes sense to me:


template< class In, class Out >
Out accumulate( In begin, const In end, Out t )
{
...
}


but not this:


template< class In, class Out >
Out accumulate( In begin, const In end, Out )
{
...
}


Of course, the one that makes sense to me doesn't compile. The compiler just
needs the type of the argument; the actual value is inconsequential :

int i = accumulate( v.begin(), v.end(), 0 );

But it still feels wierd to define a function with an argument with a type,
but no name. Is there a way to better understand why the language's syntax
is like this?




Secondly, I'm having trouble with transform().


template< class In >
bool transform( In b, const In e, In dest, In (*f)(In in) );
template< class In >
In mySquare( In arg );



int main( void )
{
vector<int> v1, v2;

for ( vector<int>::si ze_type i = 1; i <= 10; ++i )
v1.push_back(i) ;

transform( v1.begin(), v1.end(), back_inserter(v 2), mySquare );

return 0;
}



template< class In >
In mySquare( In arg )
{
return arg * arg;
}



// begin and begin2 must both be input iterators.
//
template< class In >
bool transform( In begin, const In end, In dest, In (*f)(In in) )
{
while ( begin != end )
*dest++ = f(*begin++);

return dest;
}


The compiler isn't finding any functions that match my call to transform(),
so I've blown it somewhere. How can this code be fixed?

Thanks,
Peter

[Alf P. Steinbach]

Re: Implementing library algorithms

* Pete:[color=blue]
> I'm doing exercise 8-2 from "Accelerate d C++" where we're supposed to
> implement library algorithms, trying to minimize the number of iterator
> operations.[/color]

If that exercise is relevant to your questions you should have quoted
it.

[color=blue]
> I have two questions so far.
>
>
> First, it took me a while to figure out how to get accumulate() to compile
> correctly:
>
> // begin and begin2 must both be input iterators.
> //
> template< class In, class Out >
> Out accumulate( In begin, const In end, Out )
> {
> Out ret = 0;
>
> while ( begin != end )
> ret += *begin++;
>
> return ret;
> }[/color]

For std::accumulate the third argument provides an initial value for
what you call 'ret'.

[color=blue]
> The problem is that I don't understand the function's signature. When we
> define a function, each argument needs a type and an argument name.[/color]

No, it only needs a type.
[color=blue]
> So this makes sense to me:
>
> template< class In, class Out >
> Out accumulate( In begin, const In end, Out t )
> {
> ...
> }
>
> but not this:
>
>
> template< class In, class Out >
> Out accumulate( In begin, const In end, Out )
> {
> ...
> }
>
> Of course, the one that makes sense to me doesn't compile.[/color]

If you have a question about that, do provide the code that doesn't
compile.


[snip][color=blue]
> Secondly, I'm having trouble with transform().
>
>
> template< class In >
> bool transform( In b, const In e, In dest, In (*f)(In in) );[/color]

Are you sure the function f should be a mapping from iterator to
iterator?

[color=blue]
> template< class In >
> In mySquare( In arg );
>
> int main( void )[/color]

C'ism. Don't.

[color=blue]
> {
> vector<int> v1, v2;
>
> for ( vector<int>::si ze_type i = 1; i <= 10; ++i )
> v1.push_back(i) ;
>
> transform( v1.begin(), v1.end(), back_inserter(v 2), mySquare );[/color]

v1.begin(), v1.end() and std::back_inser ter(v2) (assuming the latter is
the standard one) are not necessarily of the same type, as assumed by
your declaration of transform.

Btw., when you're mixing your own replacements for standard library
things, with standard library things, do use explicit qualification.


[color=blue]
>
> return 0;[/color]

Unnecessary. If you do provide an explicit return from main, consider
using the constants EXIT_SUCCESS and EXIT_FAILURE. Saying what you're
doing.
[color=blue]
> }[/color]

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[Peter]

Re: Implementing library algorithms

Alf P. Steinbach <alfps@start.no > wrote:[color=blue]
>[color=green]
>> template< class In >
>> In mySquare( In arg );
>>
>> int main( void )[/color]
>
> C'ism. Don't.[/color]

I don't understand this. Don't what?
[color=blue][color=green]
>> return 0;[/color]
>
> Unnecessary. If you do provide an explicit return from main, consider
> using the constants EXIT_SUCCESS and EXIT_FAILURE. Saying what you're
> doing.[/color]

0 means success in C. Is that no longer true for C++?

I've been trying to emulate the coding style of Koenig and Moo. Are they not
good coding role models?

[Alf P. Steinbach]

Re: Implementing library algorithms

* Peter:[color=blue]
> Alf P. Steinbach <alfps@start.no > wrote:[color=green]
> >[color=darkred]
> >> template< class In >
> >> In mySquare( In arg );
> >>
> >> int main( void )[/color]
> >
> > C'ism. Don't.[/color]
>
> I don't understand this. Don't what?[/color]

Don't write 'void' for an empty argument list, in C++. Do write 'void'
for an empty argument list, in C. In C you need the 'void' to specify
'no arguments', as opposed to 'any arguments'; in C++ the absence of any
formal argument means 'no arguments', and so in C++ the 'void' indicates
C code to the human reader -- and also, it's more to read.

[color=blue][color=green][color=darkred]
> >> return 0;[/color]
> >
> > Unnecessary. If you do provide an explicit return from main, consider
> > using the constants EXIT_SUCCESS and EXIT_FAILURE. Saying what you're
> > doing.[/color]
>
> 0 means success in C. Is that no longer true for C++?[/color]

In C++ both 0 and EXIT_SUCCESS mean success, and typically EXIT_SUCCESS
is defined as 0.

Again this is about readability and communicating intent.

If you write 'return 0' then that could mean 'just exit from main, I
don't care about the value', especially when there's no obvious other
reason for having a 'return' there (0 being the default), whereas if you
write 'return EXIT_SUCCESS' then there's no question of what it means:
in that case it means the return value is meaningful, and there is or
may in the future be some possibility of EXIT_FAILURE somewhere else.

[color=blue]
> I've been trying to emulate the coding style of Koenig and Moo. Are they not
> good coding role models?[/color]

They are; Andrew Koenig is a C++ expert and a good one. Barbara Moo is
probably also (I don't know anything about her, whereas Andrew often
participates in this forum). But no-one's perfect, and there are some
less than perfect constructions in that otherwise excellent, it's
probably the _best_ such, book. I know there are such imperfections, or
you might call them direct flaws, because some have been discussed in
this forum. Simply don't expect the best role models to be perfect.

However, coding style is another matter; extremely subjective and I'd
hesitate to say anything is "better" in some sense than anything else.

If I did then that would just _define_ my opinion of "better", which
theoretically could then be discussed. But someone, there's always a
SomeOne, would read that instead as an absolute judgement of the value
of some coding style, and disagree, applying not just rhetoric but also
heavy weaponry such as intercontinenta l nuclear missiles. And that
could mean I would have to move from Oslo... ;-)

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[Peter]

Re: Implementing library algorithms

All understood. Thanks for the good advice. I'll keep it all in mind. As
for the return from main(), I think "0" is appropriate for short "exercise
programs" where I don't do (or care) making the program robust. Since I'm
just now learning C++ and am really just concerned with basic concepts,
returning EXIT_SUCCESS might be overly wishful thinking on my part.


I'm still having problems with implementing transform(). Here's the full
program:



#include<iostre am>
#include<vector >
using namespace std;
template< class In, class Out >
bool myTransform( In b, const In e, In dest, Out (*f)(Out arg) );
template< class Out >
Out mySquare( Out arg );



int main()
{
vector<int> v1, v2;

for ( vector<int>::si ze_type i = 1; i <= 10; ++i )
v1.push_back(i) ;

myTransform( v1.begin(), v1.end(), back_inserter(v 2), mySquare );

return EXIT_SUCCESS;
}



template< class Out >
Out mySquare( Out arg )
{
return arg * arg;
}



template< class In, class Out >
bool myTransform( In begin, const In end, In dest, Out (*f)(Out arg) )
{
while ( begin != end )
*dest++ = f(*begin++);

return dest;
}


The error is:

g++ -g3 -W -Wall transform.cc -o transform
transform.cc: In function ???int main()???:
transform.cc:18 : error: no matching function for call to
???myTransform( __gnu_cxx::__no rmal_iterator<i nt*, std::vector<int ,
std::allocator< int> > >, __gnu_cxx::__no rmal_iterator<i nt*, std::vector<int ,
std::allocator< int> > >, std::back_inser t_iterator<std: :vector<int,
std::allocator< int> > >, <unknown type>)???
make: *** [transform] Error 1

I find it very difficult to parse compiler errors and warnings in C++, but I
don't understand why the 4th argument is listed as <unknown type>.

I've declared f as a pointer to a function that accepts an Out argument and
returns an Out argument. The prototype for mySquare() was given before the
call to myTransform(), so I don't understand what the problem is.

Why does the signature of myTransform() not match the call to myTransform()?

Thanks!
Pete

[Razzer]

Re: Implementing library algorithms


Alf P. Steinbach wrote:[color=blue]
> * Peter:[color=green]
> > Alf P. Steinbach <alfps@start.no > wrote:[color=darkred]
> > >
> > >> template< class In >
> > >> In mySquare( In arg );
> > >>
> > >> int main( void )
> > >
> > > C'ism. Don't.[/color]
> >
> > I don't understand this. Don't what?[/color]
>
> Don't write 'void' for an empty argument list, in C++. Do write 'void'
> for an empty argument list, in C. In C you need the 'void' to specify
> 'no arguments', as opposed to 'any arguments'; in C++ the absence of any
> formal argument means 'no arguments', and so in C++ the 'void' indicates
> C code to the human reader -- and also, it's more to read.[/color]

That is utter nonsense. An empty parameter list and a void-only
parameter list mean the exact same thing. Both convey the exact same
message: no arguments. The fact that you equate the latter as "C code"
is only a matter of personal bias and has nothing to do with writing
good code.

And if you are concerned about reading four more characters, I suggest
dropping the use of any word that is four or more letters as well. For
me, it takes a very simple scan to easily see what the programmer is
intending.
[color=blue]
>
>[color=green][color=darkred]
> > >> return 0;
> > >
> > > Unnecessary. If you do provide an explicit return from main, consider
> > > using the constants EXIT_SUCCESS and EXIT_FAILURE. Saying what you're
> > > doing.[/color]
> >
> > 0 means success in C. Is that no longer true for C++?[/color]
>
> In C++ both 0 and EXIT_SUCCESS mean success, and typically EXIT_SUCCESS
> is defined as 0.
>
> Again this is about readability and communicating intent.
>
> If you write 'return 0' then that could mean 'just exit from main, I
> don't care about the value', especially when there's no obvious other
> reason for having a 'return' there (0 being the default), whereas if you
> write 'return EXIT_SUCCESS' then there's no question of what it means:
> in that case it means the return value is meaningful, and there is or
> may in the future be some possibility of EXIT_FAILURE somewhere else.[/color]

EXIT_SUCCESS and 0 mean exactly the same thing. The implementation is
required to have the same implementation-defined form of successful
termination for either value. There is no difference between the two.
The distinction you make is only of personal bias.
[color=blue]
>
>[color=green]
> > I've been trying to emulate the coding style of Koenig and Moo. Are they not
> > good coding role models?[/color]
>
> They are; Andrew Koenig is a C++ expert and a good one. Barbara Moo is
> probably also (I don't know anything about her, whereas Andrew often
> participates in this forum). But no-one's perfect, and there are some
> less than perfect constructions in that otherwise excellent, it's
> probably the _best_ such, book. I know there are such imperfections, or
> you might call them direct flaws, because some have been discussed in
> this forum. Simply don't expect the best role models to be perfect.
>
> However, coding style is another matter; extremely subjective and I'd
> hesitate to say anything is "better" in some sense than anything else.
>
> If I did then that would just _define_ my opinion of "better", which
> theoretically could then be discussed. But someone, there's always a
> SomeOne, would read that instead as an absolute judgement of the value
> of some coding style, and disagree, applying not just rhetoric but also
> heavy weaponry such as intercontinenta l nuclear missiles. And that
> could mean I would have to move from Oslo... ;-)
>
> --
> A: Because it messes up the order in which people normally read text.
> Q: Why is it such a bad thing?
> A: Top-posting.
> Q: What is the most annoying thing on usenet and in e-mail?[/color]

[Alf P. Steinbach]

Re: Implementing library algorithms

* Peter:[color=blue]
> #include<iostre am>
> #include<vector >
> using namespace std;
> template< class In, class Out >
> bool myTransform( In b, const In e, In dest, Out (*f)(Out arg) );
> template< class Out >
> Out mySquare( Out arg );
>
> int main()
> {
> vector<int> v1, v2;
>
> for ( vector<int>::si ze_type i = 1; i <= 10; ++i )
> v1.push_back(i) ;
>
> myTransform( v1.begin(), v1.end(), back_inserter(v 2), mySquare );
>
> return EXIT_SUCCESS;
> }[/color]
[snip][color=blue]
>
> Why does the signature of myTransform() not match the call to myTransform()?[/color]

What type do you think the compiler should assume for 'Out', given only
the declarations above (no insight into what the implementation does)?

Apart from that, also consider what I wrote earlier:

"v1.begin() , v1.end() and std::back_inser ter(v2) (assuming the latter is
the standard one) are not necessarily of the same type, as assumed by
your declaration of transform."

In particular, in a C++ library implementation where a
std::vector::it erator is a simple pointer, there is no way a pointer
operation could result in a back insertion in a pointed to vector,
because you cannot (portably) obtain a poiner to the vector object from
a pointer to an element. A back_inserter is a more complicated and
intelligent beastie. So it cannot be the same type as v1.begin(), say.

Why not check the declaration of std::transform and compare it to the
declaration of myTransform?

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[Alf P. Steinbach]

Re: Implementing library algorithms

* Razzer:[color=blue]
> * Alf P. Steinbach:[color=green]
> >
> > Don't write 'void' for an empty argument list, in C++. Do write 'void'
> > for an empty argument list, in C. In C you need the 'void' to specify
> > 'no arguments', as opposed to 'any arguments'; in C++ the absence of any
> > formal argument means 'no arguments', and so in C++ the 'void' indicates
> > C code to the human reader -- and also, it's more to read.[/color]
>
> That is utter nonsense. An empty parameter list and a void-only
> parameter list mean the exact same thing. Both convey the exact same
> message: no arguments. The fact that you equate the latter as "C code"
> is only a matter of personal bias and has nothing to do with writing
> good code.[/color]

It's always a good idea to read the FAQ before posting in this group.

Check out the _newbie section_ in the C++ FAQ,
<url: http://www.parashift.c om/c++-faq-lite/newbie.html#faq-29.4>.

«In fact, the f(void) style has been called an "abominatio n" by Bjarne
Stroustrup, the creator of C++, Dennis Ritchie, the co-creator of C, and
Doug McIlroy, head of the research department where Unix was born.»

Of course, that's only a matter of personal bias, in that you are
correct.

But there are reasons why so many expert programmers, including the
language creators, have ended up with the same bias on this issue.


[excessive quoting snipped, please don't quote excessively][color=blue][color=green]
> > If you write 'return 0' then that could mean 'just exit from main, I
> > don't care about the value', especially when there's no obvious other
> > reason for having a 'return' there (0 being the default), whereas if you
> > write 'return EXIT_SUCCESS' then there's no question of what it means:
> > in that case it means the return value is meaningful, and there is or
> > may in the future be some possibility of EXIT_FAILURE somewhere else.[/color]
>
> EXIT_SUCCESS and 0 mean exactly the same thing. The implementation is
> required to have the same implementation-defined form of successful
> termination for either value. There is no difference between the two.
> The distinction you make is only of personal bias.[/color]

Unfortunately for that question I cannot refer you to the online version
of the FAQ, because it doesn't discuss all small issues (there's no room
for that), but the error in your reasoning is the same as before.

Yes, technically they mean the same thing.

And no, to the human reader they don't necessarily mean the same thing.


[excessive quoting snipped, please don't quote excessively]

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[Default User]

Re: Implementing library algorithms

Alf P. Steinbach wrote:
[color=blue]
> * Pete:[/color]
[color=blue][color=green]
> > return 0;[/color]
>
> Unnecessary. If you do provide an explicit return from main, consider
> using the constants EXIT_SUCCESS and EXIT_FAILURE. Saying what you're
> doing.[/color]

I think this is dumb advice. What the OP has is in no way incorrect or
non-standard. Find real things to complain about rather than this
bizarre hobbyhorse of yours.



Brian

[Earl Purple]

Re: Implementing library algorithms


Alf P. Steinbach wrote:
[color=blue]
> Unnecessary. If you do provide an explicit return from main, consider
> using the constants EXIT_SUCCESS and EXIT_FAILURE. Saying what you're
> doing.[/color]

There are worse sins in the world. When all the other awful things have
been removed from C++ code then we can think about using returns like
this.

But maybe by then EXIT_SUCCESS will be a reserved keyword in the
language like false is, because right now I think you have to #include
<cstdlib> to define it so it isn't exactly no-cost (if you consider
including headers a cost).

I do agree that int f(void) looks wrong because it looks like it takes
one argument of type void. (Can happen with templates).

One day they may even implement main in C++ to be

int main( const std::vector< std::string > argList )

Now of course if the operating system were written in C++ we could
throw a fail exception rather than return a failure code. (Return codes
are so C aren't they?)

[Earl Purple]

Re: Implementing library algorithms


Pete wrote:[color=blue]
>
> // begin and begin2 must both be input iterators.
> //
> template< class In, class Out >
> Out accumulate( In begin, const In end, Out )
> {
> Out ret = 0;
>
> while ( begin != end )
> ret += *begin++;
>
> return ret;
> }[/color]

It looks cool to do *begin++ and it looks like because it is only one
statement it is better than two statements, but in fact it is likely to
be more efficient (and highly unlikely to be less efficient) to use two
statements.

while ( begin != end )
{
ret += *begin;
++begin;
}

If you really want to make it a one-liner then use 'for' instead of
'while' thus:

for( ; begin != end; ++begin )
ret += *begin;

Now I'm not sure if the standard expects operator+= or operator+. I
wish it were operator+= but have a feeling that it is operator+ and
therefore you get the horrible

ret = ret + *begin;

which forces a copy of res (which may well be a class). Now of course
because the algorithms want to allow the user to input an r-value here
they have to force it to be an r-value, still it shouldn't be forced to
copy for every iteration.

By the way, the 3rd parameter is there for a reason so wipe out your
Out ret=0; and simply put "ret" as the name of the 3rd parameter.

In addition, your 2nd parameter should be const In & end rather than
const In end.
[color=blue]
> Of course, the one that makes sense to me doesn't compile. The compiler just
> needs the type of the argument; the actual value is inconsequential :[/color]

no because the user provides the start value. As I said, it may be a
class. 0 might not even be a possible value (why should it be? suppose
it's a string?)

(std:: left out for clarity below)

vector< string > vectOfStrings;
string concatenated = accumulate( vectOfStrings.b egin(),
vectOfStrings.e nd(), string() );

Might not be the optimal way to concatenate a vector of strings into
one string, but it's a way that would work. Perhaps this isn't a
performance-critical situation. Now putting in 0 for the 3rd parameter
would probably compile because string has an implicit constructor from
const char* but 0 (NULL) is an invalid pointer (it doesn't construct an
empty string).

I think others have addressed transform.

[ma740988]

Re: Implementing library algorithms


Earl Purple wrote:
[color=blue]
> But maybe by then EXIT_SUCCESS will be a reserved keyword in the
> language like false is, because right now I think you have to #include
> <cstdlib> to define it so it isn't exactly no-cost (if you consider
> including headers a cost).
>[/color]
How much 'cost' are we talking about here? I tend to have a
'common_header' file that - literally includes everything. For
instance:

// common_header.h
# ifndef COMMON_HEADER_H
# define COMMON_HEADER_H

# include <iostream>
# include <algorithm>
# include <map>
# include <vector>
// more stuff
#endif

// Later:
// foo.h
# include "common_header. h"

class foo {
public:
explicit foo() {}
};

// bar.h
# include "common_header. h"
class bar {
public:
explicit bar() {}
};

I've often wondered about the 'cost' (though I've never measured it )
but if memory serves - in some paper/text by Nicolai Josuttis was where
I picked up on that. He was an advocate for that for some reason I
cant remember.
Besides compile time ( which quite frankly is 'noise' at this point for
me) I'm not sure what other 'cost' I should factor in. Size of
executable maybe?

[Alf P. Steinbach]

Re: Implementing library algorithms

* Default User:[color=blue]
> Alf P. Steinbach wrote:
>[color=green]
> > * Pete:[/color]
>[color=green][color=darkred]
> > > return 0;[/color]
> >
> > Unnecessary. If you do provide an explicit return from main, consider
> > using the constants EXIT_SUCCESS and EXIT_FAILURE. Saying what you're
> > doing.[/color]
>
> I think this is dumb advice. What the OP has is in no way incorrect or
> non-standard. Find real things to complain about rather than this
> bizarre hobbyhorse of yours.[/color]

We who provide the help in this corner of Usenet unfortunately have to
put up with complaints and fabrications such as yours.

Please think of something more constructive to do.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[Default User]

Re: Implementing library algorithms

Alf P. Steinbach wrote:
[color=blue]
> * Default User:[/color]
[color=blue][color=green]
> > I think this is dumb advice. What the OP has is in no way
> > incorrect or non-standard. Find real things to complain about
> > rather than this bizarre hobbyhorse of yours.[/color]
>
> We who provide the help in this corner of Usenet unfortunately have to
> put up with complaints and fabrications such as yours.[/color]

Nonsense. You're dispensing stylistic preference. There's nothing AT
ALL wrong with returning 0 from main(). You just don't happen to like
it, so you chide newbies about it. That isn't help.
[color=blue]
> Please think of something more constructive to do.[/color]

I'll give you the same advice.


Brian
--
Please quote enough of the previous message for context. To do so from
Google, click "show options" and use the Reply shown in the expanded
header.

[roberts.noah@gmail.com]

Re: Implementing library algorithms


Alf P. Steinbach wrote:
[color=blue]
> But there are reasons why so many expert programmers, including the
> language creators, have ended up with the same bias on ["void" argument lists].[/color]

Like?