Implementing library algorithms

[Pete]

I'm doing exercise 8-2 from "Accelerated 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>::size_type i = 1; i <= 10; ++i )
v1.push_back(i);

transform( v1.begin(), v1.end(), back_inserter(v2), 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]

* Pete:

I'm doing exercise 8-2 from "Accelerated C++" where we're supposed to
implement library algorithms, trying to minimize the number of iterator
operations.

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

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;
}

For std::accumulate the third argument provides an initial value for
what you call '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.

No, it only needs a type.

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.

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


[snip]

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


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

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

template< class In >
In mySquare( In arg );

int main( void )

C'ism. Don't.

{
vector<int> v1, v2;

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

transform( v1.begin(), v1.end(), back_inserter(v2), mySquare );

v1.begin(), v1.end() and std::back_inserter(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.

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.

 

[Peter]

C'ism. Don't.

I don't understand this. Don't what?

Unnecessary. If you do provide an explicit return from main, consider
using the constants EXIT_SUCCESS and EXIT_FAILURE. Saying what you're
doing.

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]

* Peter:

I don't understand this. Don't what?

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.

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

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.

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

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 intercontinental nuclear missiles. And that
could mean I would have to move from Oslo... ;-)

 

[Peter]

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<iostream>
#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>::size_type i = 1; i <= 10; ++i )
v1.push_back(i);

myTransform( v1.begin(), v1.end(), back_inserter(v2), 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::__normal_iterator<int*, std::vector<int,
std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int,
std::allocator<int> > >, std::back_insert_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]

* Peter:

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.

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.

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.

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.

 

[Alf P. Steinbach]

* Peter:

#include<iostream>
#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>::size_type i = 1; i <= 10; ++i )
v1.push_back(i);

myTransform( v1.begin(), v1.end(), back_inserter(v2), mySquare );

return EXIT_SUCCESS;
} [snip]

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

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_inserter(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::iterator 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?

 

[Alf P. Steinbach]

* Razzer:

* Alf P. Steinbach:

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.

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.com/c++-faq-lite/newbie.html#faq-29.4>.

«In fact, the f(void) style has been called an "abomination" 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]

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.

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]

 

[Default User]

* Pete:

Unnecessary. If you do provide an explicit return from main, consider
using the constants EXIT_SUCCESS and EXIT_FAILURE. Saying what you're
doing.

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]

Unnecessary. If you do provide an explicit return from main, consider
using the constants EXIT_SUCCESS and EXIT_FAILURE. Saying what you're
doing.

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]

// 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;
}

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.

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:

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.begin(),
vectOfStrings.end(), 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]

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).

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]

* Default User:

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.

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.

 

[Default User]

* Default User:

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

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.

Please think of something more constructive to do.

I'll give you the same advice.


Brian

 

[roberts.noah]

But there are reasons why so many expert programmers, including the
language creators, have ended up with the same bias on ["void" argument lists].

Like?

 

[Alf P. Steinbach]

* Default User:

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.

That is fabrication.

I wrote

"Unnecessary. If you do provide an explicit return from main, consider
using the constants EXIT_SUCCESS and EXIT_FAILURE. Saying what you're
doing."

Perhaps it's "dumb" (as you write) for newbies to know, perhaps it's
dumb to even consider using the features of the language and standard
library, perhaps it's chiding to mention that these things exist, but I
don't see it that way: I think especially newbies are helped by being
given information, and in no way helped by having purely informative
statements being given person-oriented, negative spins such as yours, so
that the newbie must doubt both the information and the source.

 

[Default User]

Alf P. Steinbach wrote:

I wrote

"Unnecessary. If you do provide an explicit return from main,
consider using the constants EXIT_SUCCESS and EXIT_FAILURE. Saying
what you're doing."

Perhaps I was a bit strong in my criticism. Let me just say that I feel
leaving out the return is bad policy, even though the language allows
it. It's a maintenance problem because it's not clear whether the
programmer intended to do that or just forgot.

Additionally, I think "return 0" is prefectly idiomatic and well
understood in this context. Obviously, if someone uses non-standard
forms like "return -1" or something similar, it is a problem. I
certainly would never object to someone who wanted to use EXIT_SUCCESS,
but it isn't necessary.



Brian

 

[Alf P. Steinbach]

* (e-mail address removed):

But there are reasons why so many expert programmers, including the
language creators, have ended up with the same bias on ["void" argument lists].

Like?

See my earlier posting in this thread (including the FAQ link I provided
there, and the link from that FAQ item to Bjarne Stroustrup's writings).

Bjarne Stroustrup said this in an interview with Dr. Dobbs Journal:

<quote>
Dennis Ritchie and Doug McIlroy famously gave me courage to break with
ANSI C in the issue of the declaration of a function with an empty
argument list. To preserve compatibility with K&R C, I had invented the

int f(void);

notation for C with Classes. Initially, I retained the old meaning of

int f();

as "f()" can accept any arguments that happens to be compatible with
f()'s (unseen) definition". Dennis and Doug called the f(void) style
declaration an abomination, so in C++

int f();

now has the obviuos meaning: "f() takes no arguments." Unfortunately,
ANSI C adopted f(void) so I had to introduce f(void) into C++ for ANSI C
compatibility.
</quote>

I.e., 'T f(void)' only exists in C++ for compatibility with C which
adopted this kludge from C++ before C++ evolved to a cleaner declaration
syntax where it wasn't needed -- except for (now) C compatibility...

Besides being ugly, of no technical consequence and thus misleading, and
more to read and write, it's a C'ism, and so a second reason for not
using it is the general one of avoiding C'isms. For the habit of coding
C style in C++ can have adverse consequences. And the more C'isms are
used, the easier it is to slip into a C mindset.

 

[JustBoo]

From the FAQ that is said to be the official FAQ of this ng.

http://www.parashift.com/c++-faq-lite/newbie.html
Section [29.3]:

<quote>
int main() // GOOD
{
...
}
As to the specific return value, if you don't know what else to
return just say return 0;
</quote>

"If you have ten thousand regulations you destroy
all respect for the law." - Winston Churchill

 

[Alf P. Steinbach]

* JustBoo:

From the FAQ that is said to be the official FAQ of this ng.

http://www.parashift.com/c++-faq-lite/newbie.html
Section [29.3]:

<quote>
int main() // GOOD
{
...
}
As to the specific return value, if you don't know what else to
return just say return 0;
</quote>

Yes. Unfortunately the FAQ doesn't discuss EXIT_SUCCESS and
EXIT_FAILURE. And mostly it teaches the common way to write a main
function by example: 1 example contains a "return 0", and the rest,
about ten or twenty main functions, simply end with "}".