TITLE: guru question #2 - temporaries

(Newsgroups: comp.lang.c++.moderated, 24 Feb 97)

From: herbs@cntc.com (Herb Sutter)

(Background: Internally in my company, I post weekly C++ problems of
varying difficulty.  They're intended as tools to stimulate thinking and
discussion among developers, and at the same time they let programmers pick
up useful tidbits of C++ knowledge from each other.  I'll start posting the
problems to this group too, since they may be of general interest.

I hope this stimulates discussion here, too.  Each week I'll post my answer
to the last week's problem.  Note: the problem statement doesn't always
tell you everything to look for.  For example, in this one it says there
are "at least three" instances of a particular problem... there are
actually several more than that.)



Guru of the Week #2     Difficulty: 5/10
                        Subject:    Temporaries


You are doing a code review.  A programmer has written the following
function, which uses unnecessary temporary objects in at least three
places.

How many can you identify, and how should the programmer fix them?


    string FindAddr( list<Employee> l, string name )
    {
        for( list<Employee>::iterator i = l.begin(); i != l.end(); i++ )
        {
            if( *i == name )
            {
                return (*i).addr;
            }
        }
        return "";
    }


POTTER: jpotter@falcon.lhup.edu (John E. Potter)

The purpose of Herb's post was to stimulate discussion.  I have found that
prose provokes more discussion than code; so, I will produce little code.

     string FindAddr( list<Employee> l, string name )
     ^^^1^^           ^^^^^^^^2^^^^^^^  ^^^^^^3^^^^
     {
          for( list<Employee>::iterator i = l.begin(); i != l.end(); i++ )
                                            ^^^^4^^^^       ^^^5^^^  ^6^
          {
                if( *i == name )
                    ^^^^^7^^^^
                {
                     return (*i).addr;
                }
          }
          return "";
                 ^8^
     }
*/

The (*i).addr seems to indicate that Employee is a struct with possibly
some member functions.  I make this assumption.

1.  This is a temp which could be replaced by a string const&.  It would
reduce the possibilities, but knowing that Herb would not miss the ability
to say
    string result(((FindAddr(l, n) += " was found for ") += n) += '\n');
I will assume that string const& is acceptable.

[ This is likely a mistake since the return of string("") will leave
  a dangling reference. -adc ] 

2.  No question that it should be a const&.

3.  We can also make this a const&.  A char* can still produce a string to
be passed as a parameter to a const&.  So a string would be no cost and
char* is still usable.

4.  This is needed in some form and can not be removed.

5.  We could remove this function call.  It is likely not very costly
since an iterator is about as complicated as an int in the standard
classes.  Possibly some slight savings by using a local variable set to
end().

6.  OK, we should all use ++i not i++ even if this is C++ not ++C.  Scott
Meyers in "More Effective C++" has quietly proposed this.  Herb and I
agree with him; so, I know that this is one of the temps to be removed.

7.  This is the real open question.  We have Employee == string.  I see
three possibilities.  (1)There is an operator== which takes an Employee
and a string and returns e.name == name using the string ==.  This is no
temporary cost.  (2)Employee has operator string or operator string const&
which returns the name field.  This could be a temp cost.  (3)There
is an Employee(string) constructor which uses the string to initialize
the name field and an operator== for Employee which compares name fields.
This would also be a temp cost.  Just to keep things simple, I will
assume that the operator==(Employee const&, string const&) exists.  If
I were going to rewrite this, I would use (*i).name == name which would
leave no confusion.

8.  This is a temp; however, the empty string is spelled string() not
"".  The latter is a conversion which involves allocating no memory.

I feel that items 2,3,6,7,8 are worth changing to form good habits.  Items
1 and 5 should only be considered when profiling indicates a need.  They
change a natural style to less than natural.

With the above assumption on operator==, here is my recomendation:

string const EMPTY_STRING;
string const& FindAddr( list<Employee> const& l, string const& name ) {
    list<Employee>::const_iterator it(find(l.begin(), l.end(), name));
    return it != l.end() ? (*it).addr : EMPTY_STRING;
    }

I consider global constants acceptable.  It would be nice if it were
std::string::EMPTY_STRING, but this will do.

If the assumption on operator== is not correct, then a predicate
functor is appropriate.

class EmployeeNameMatcher {
    public :
        EmployeeNameMatcher (string const& n) : name(n) { }
        bool operator() (Employee const& e) {
             return e.name == name;
             }
    private :
        string const& name;
    };

    list<Employee>::const_iterator it(find_if(l.begin(), l.end(),
            EmployeeNameMatcher(name));

Finally, I think that this function may loose information.  Assuming
that this equal opportunity company is willing to hire the homeless,
it is possible that the addr field may be empty.  Does the empty
string returned indicate not found or no address?  Why should a
function do a search and return a value which must be tested for
success when it has already tested it?  Perhaps another string&
parameter to store the found value and a bool return value.  I found
little use for the C library binary search since I almost always was
interested in what was found as well as whether it found it.  I have yet
to use binary_search; however, I have found many uses for lower_bound
and upper_bound.  I think that the most useful return for this function
would be the iterator.  So throw the whole thing away and replace it
with the standard library find/find_if.  No unneeded temps now.