Accelerated C++: exercise 6-1

[Pete]

Is anyone familiar with this book?

Exercise 6-1 of Accelerated C++ asks us to reimplement the frame() and hcat()
operations using iterators. I've posted my answers below, but I'm wondering
if I'm off track here.

First of all, the book has been brisk but reasonable up to chapter 5, and
then suddenly, it exploded. I had to grit my teeth to get through chapter 6,
but the exercises for chap 6 are pretty tame.

Secondly, it was astonishing to see the function that splits lines into words
evaporate into a really small and easily understandable piece of code. I
don't see that happening in my answers to 6-1. My iterator versions don't
look any more efficient or less cluttered.

If anyone is familiar with this book, I would appreciate hearing comments
about whether my answers are on the right track or whether I've missed the
point of the exercise.

Thanks!
Pete




// Horizontal concatenation of two vectors containing strings (indexes)
//
vector<string>
oldhcat( const vector<string> &left, const vector<string> &right )
{
vector<string> ret;

// Add one to leave a space between the pictures.
vector<string>::size_type width1 = maxWidth(left) + 1;

vector<string>::size_type i = 0, j = 0; // i: right, j: left

// Continue until we've seen all rows from both pictures.
while ( i != left.size() || j != right.size() )
{
string s;

// If there's a line of left, copy it to s.
if ( i != left.size() ) s = left[i++];

s += string(width1 - s.size(), ' '); // Pad to full width

// If there's a line of right, copy it to s.
if ( j != right.size() ) s += right[j++];

ret.push_back(s);
}

return ret;
}



// Horizontal concatenation of two vectors containing strings (iterators)
//
vector<string>
hcat( const vector<string> &left, const vector<string> &right )
{
vector<string> ret;

// Add one to leave a space between the pictures.
vector<string>::size_type width1 = maxWidth(left) + 1;

vector<string>::const_iterator i = left.begin();
vector<string>::const_iterator j = right.begin();

// Continue until we've seen all rows from both pictures.
while ( i != left.end() || j != right.end() )
{
string s;

// If there's a line of left, copy it to s.
if ( i != left.end() ) s = *(i++);

s += string(width1 - s.size(), ' '); // Pad to full width

// If there's a line of right, copy it to s.
if ( j != right.end() ) s += *(j++);

ret.push_back(s);
}

return ret;
}



// Put a frame around a vector of strings (indexes)
//
vector<string> oldframe( const vector<string> &v )
{
vector<string> ret;

string::size_type maxlen = maxWidth(v); // width of widest element

// Fix the anomalous zero-input border condition
int starNumber = ( maxlen == 0 ) ? 2 : maxlen + 4;
string border( starNumber, '*' );

ret.push_back(border); // Top border

for ( vector<string>::size_type i = 0; i != v.size(); ++i )
ret.push_back("* " + v + string(maxlen - v.size(), ' ') + " *");

ret.push_back(border); // Bottom border
return ret;
}



// Put a frame around a vector of strings (iterators)
//
vector<string> frame( const vector<string> &v )
{
vector<string> ret;

string::size_type maxlen = maxWidth(v); // width of widest element

// Fix the anomalous zero-input border condition
int starNumber = ( maxlen == 0 ) ? 2 : maxlen + 4;
string border( starNumber, '*' );

ret.push_back(border); // Top border

vector<string>::const_iterator iter;
for ( iter = v.begin(); iter != v.end(); ++iter )
ret.push_back("* " + *iter + string(maxlen - iter->size(), ' ') + " *");

ret.push_back(border); // Bottom border

return ret;
}

 

[Michiel.Salters]

Exercise 6-1 of Accelerated C++ asks us to reimplement the frame() and hcat()
operations using iterators. I've posted my answers below, but I'm wondering
if I'm off track here.

// Horizontal concatenation of two vectors containing strings (indexes)
//
vector<string>
oldhcat( const vector<string> &left, const vector<string> &right )
{
vector<string> ret;

// Add one to leave a space between the pictures.
vector<string>::size_type width1 = maxWidth(left) + 1;

vector<string>::size_type i = 0, j = 0; // i: right, j: left

// Continue until we've seen all rows from both pictures.
while ( i != left.size() || j != right.size() )
{
string s;

// If there's a line of left, copy it to s.
if ( i != left.size() ) s = left[i++];

s += string(width1 - s.size(), ' '); // Pad to full width

// If there's a line of right, copy it to s.
if ( j != right.size() ) s += right[j++];

ret.push_back(s);
}

return ret;
}

Why don't you use a function for the loop body? And why (considering
you
should be using iterators) do you use index variables, and name them i
and j? Your comment shows you too know they're not good names.
It's easier to use left_iter and right_iter.

HTH,
Michiel Salters
with i

 

[pH]

The iterator versions are fine; not much more concise than the indexer
version, but they should perform (a bit) faster. There's no obvious way
of improving on them (except perhaps more helpful variable names...). I
would probably pre-allocate ret, though, in both cases, and then write
to that through another iterator, as that would prevent having to
re-allocate the memory for ret every few iterations.

 

[Pete]

Exercise 6-1 of Accelerated C++ asks us to reimplement the frame() and hcat()
operations using iterators. I've posted my answers below, but I'm wondering
if I'm off track here.

// Horizontal concatenation of two vectors containing strings (indexes)
//
vector<string>
oldhcat( const vector<string> &left, const vector<string> &right )
{
vector<string> ret;

// Add one to leave a space between the pictures.
vector<string>::size_type width1 = maxWidth(left) + 1;

vector<string>::size_type i = 0, j = 0; // i: right, j: left

// Continue until we've seen all rows from both pictures.
while ( i != left.size() || j != right.size() )
{
string s;

// If there's a line of left, copy it to s.
if ( i != left.size() ) s = left[i++];

s += string(width1 - s.size(), ' '); // Pad to full width

// If there's a line of right, copy it to s.
if ( j != right.size() ) s += right[j++];

ret.push_back(s);
}

return ret;
}

Why don't you use a function for the loop body? And why (considering
you
should be using iterators) do you use index variables, and name them i
and j? Your comment shows you too know they're not good names.
It's easier to use left_iter and right_iter.

Oh, I had posted both the iterator and index versions of the functions. The
one you quoted is the index version. The index versions were named
"oldhcat()" (as this one is) and "oldframe"; the iterator versions were
"hcat()" and "frame()".

Pete

 

[Neil Cerutti]

Is anyone familiar with this book?

Exercise 6-1 of Accelerated C++ asks us to reimplement the
frame() and hcat() operations using iterators. I've posted my
answers below, but I'm wondering if I'm off track here.

First of all, the book has been brisk but reasonable up to
chapter 5, and then suddenly, it exploded. I had to grit my
teeth to get through chapter 6, but the exercises for chap 6
are pretty tame.

Secondly, it was astonishing to see the function that splits
lines into words evaporate into a really small and easily
understandable piece of code. I don't see that happening in my
answers to 6-1. My iterator versions don't look any more
efficient or less cluttered.

You need to change the signature of the iterator versions so that
you receive input iterators and write to an output iterator.

// Horizontal concatenation of two vectors containing strings (iterators)
//
vector<string>
hcat( const vector<string> &left, const vector<string> &right )

I believe you instead need something like this as your function
signature:

template <class In, class Out>
Forward
hcat(In left_begin, In left_end, In right_begin, In right_end, Out output)

Start with that and see if you get more felicitous results.

 

[Gavin Deane]

You need to change the signature of the iterator versions so that
you receive input iterators and write to an output iterator.


I believe you instead need something like this as your function
signature:

template <class In, class Out>
Forward
hcat(In left_begin, In left_end, In right_begin, In right_end, Out output)

Start with that and see if you get more felicitous results.

Sound advice in general, but in the context of the Accelerated C++
book, the OP hasn't encountered writing your own generic functions yet.
That's in chapter 8.

Gavin Deane

 

[Gavin Deane]

Secondly, it was astonishing to see the function that splits lines into words
evaporate into a really small and easily understandable piece of code. I
don't see that happening in my answers to 6-1. My iterator versions don't
look any more efficient or less cluttered.

The string splitting function didn't evaporate into a concise piece of
code by substituting iterators for indices. It did it by substituting
standard algorithms function calls for hand-coded loops.

As you have found, just changing from indices to iterators does not
necessarily make the code more concise. But it does mean that, when the
opportunity arises, you are able to interface with the standard
library's algorithms - something that code using indices can't do.

Gavin Deane

 

[Roland Pibinger]

First of all, the book has been brisk but reasonable up to chapter 5, and
then suddenly, it exploded. I had to grit my teeth to get through chapter 6,

It's not a gentle introduction to C++ programming but an 'accelerated'
intruduction to STL programming.

vector<string>
oldhcat( const vector<string> &left, const vector<string> &right ) [...]
vector<string>
hcat( const vector<string> &left, const vector<string> &right ) [...]
vector<string> oldframe( const vector<string> &v ) [...]
vector<string> frame( const vector<string> &v )

[...]

Returning a vector<something> _by value_ is always bad style. You
should pass an empty vector by reference.

Best wishes,
Roland Pibinger

 

[E. Mark Ping]

Returning a vector<something> _by value_ is always bad style. You
should pass an empty vector by reference.

False. That is often a reasonable solution (though be careful about
module boundaries). Like most generalizations, however, your "always"
is simply not true.

 

[Roland Pibinger]

False. That is often a reasonable solution (though be careful about
module boundaries). Like most generalizations, however, your "always"
is simply not true.

One real world example where returning a vector by value is a
'reasonable solution'?

 

[ferdinand.stefanus]

One real world example where returning a vector by value is a
'reasonable solution'?

One obvious case that I can think of is returning a temporary, e.g.:

vector<int> foo()
{
vector<int> result;

//... calculation

return result;
}

Of course, one can always change the above function to

void foo(vector<int>& result)
{
//... calculation
}

I'm not sure which function is more efficient though, especially if the
compiler performs named return value optimization.

 

[Gavin Deane]

First of all, the book has been brisk but reasonable up to chapter 5, and
then suddenly, it exploded. I had to grit my teeth to get through chapter 6,

It's not a gentle introduction to C++ programming but an 'accelerated'
intruduction to STL programming.

vector<string>
oldhcat( const vector<string> &left, const vector<string> &right ) [...]
vector<string>
hcat( const vector<string> &left, const vector<string> &right ) [...]
vector<string> oldframe( const vector<string> &v ) [...]
vector<string> frame( const vector<string> &v )

[...]

Returning a vector<something> _by value_ is always bad style. You
should pass an empty vector by reference.

Only if you happen to be stuck with a complier that still can't do
return value optimisation. Returning the vector by value results in
clearer code so should be the default choice. Only use the less clear
technique when necessary. Even without return value optimisation,
returning by value should still be preferred unless it causes an
identifiable performance problem.

Gavin Deane

 

[Neil Cerutti]

Sound advice in general, but in the context of the Accelerated
C++ book, the OP hasn't encountered writing your own generic
functions yet. That's in chapter 8.

Ah. Thanks for correcting me. I no longer have my copy, and
couldn't find my solutions to the exercises any more.

 

[Roland Pibinger]

One obvious case that I can think of is returning a temporary, e.g.:

vector<int> foo()
{
vector<int> result;

//... calculation

return result;
}

What do you do with the returned vector<int>? You assign (copy) it to
another vector<int>.

Of course, one can always change the above function to

void foo(vector<int>& result)
{
//... calculation
}

I'm not sure which function is more efficient though, especially if the
compiler performs named return value optimization.

Internally RVO is probably implemented as you describe in your second
example.

Best wishes,
Roland Pibinger

 

[Roland Pibinger]

Roland Pibinger wrote:

Only if you happen to be stuck with a complier that still can't do
return value optimisation.

There are many cases where compilers don't perform (N)RVO even if they
can do (N)RVO. Check your compiler documentation.

Returning the vector by value results in
clearer code so should be the default choice.

I beg to differ on what is 'clearer code'. Also, entity objects (which
have no copy constructor) cannot be returned by value.

Only use the less clear technique when necessary.

At least one sentence I can endorse.

Even without return value optimisation,
returning by value should still be preferred unless it causes an
identifiable performance problem.

Even with full return value optimisation, returning a large object
(vector) by value should be avoided. I guess, we agree to disagree.

Best regards,
Roland Pibinger