Solution

Believe it or not, this short function harbors three obvious cases of unnecessary temporaries, two subtler ones, and two red herrings.

The two more-obvious temporaries are buried in the function declaration itself:

string FindAddr( list<Employee> emps, string name ) 

The parameters should be passed by const&梩hat is, const list<Employee>& and const string&, respectively梚nstead of by value. Pass-by-value forces the compiler to make complete copies of both objects, which can be expensive and, here, is completely unnecessary.

The third more-obvious avoidable temporary occurs in the for loop's termination condition:

for( /*...*/ ; i != emps.end(); /*...*/ ) 

For most containers (including list), calling end() returns a temporary object that must be constructed and destroyed. Because the value will not change, recomputing (and reconstructing and redestroying) it on every loop iteration is both needlessly inefficient and unaesthetic. The value should be computed only once, stored in a local object, and reused.

Next, consider the way we increment i in the for loop:

for( /*...*/ ; i++ 

This temporary is more subtle, but it's easy to understand once you remember how preincrement and postincrement differ. Postincrement is usually less efficient than preincrement because it has to remember and return its original value. Postincrement for a class T should generally be implemented using the canonical form, as follows:

const T T::operator++(int) 


{


  T old( *this ); // remember our original value


  ++*this;        // always implement postincrement


                  //   in terms of preincrement


  return old;     // return our original value


}

Now it's easy to see why postincrement is less efficient than preincrement. Postincrement has to do all the same work as preincrement, but in addition it also has to construct and return another object containing the original value.

In the problem's code, the original value is never used, so there's no reason to use postincrement. Preincrement should be used instead. The accompanying box, "When Can Compilers Optimize Postincrement?" will tell you why compilers can't, in general, make the substitution for you automatically.

if( *i == name ) 

The Employee class isn't shown in the problem, but we can deduce a few things about it. For this code to work, Employee most likely has a conversion to string or a conversion constructor taking a string. Both cases create a temporary object, invoking either operator==() for strings or operator==() for Employees (only if there does happen to be an operator==() that takes one of each, or Employee has a conversion to a reference梩hat is, string&梚s a temporary not needed).

When Can Compilers Optimize Postincrement? Say you write a postincrement expression like "i++" but don't use the return value. Is the compiler allowed to notice this and simply rewrite the postincrement as preincrement as an optimization? The answer is: No, not in general. The only time the compiler is allowed to optimize away unnecessary postincrement by rewriting it as preincrement is for builtin and standard types, such as int and complex, whose semantics the compiler is allowed to know because they're standard. For class types, on the other hand, the compiler can't know the actual semantics of postincrement and preincrement梚ndeed, the two actually might not do the same thing. It would be a terrible thing indeed if the two functions didn't have the same semantics, and any programmer who wrote them with different semantics should be sacked on the spot. But, in general, that doesn't help the compiler, because it can't assume that the programmer is consistent. There is a way you can deliberately let the compiler see the relationship between pre- and postincrement for a class type: Implement the canonical form of postincrement, which calls preincrement, and declare it inline so that the compiler can see across the function-call boundary (if it respects the inline directive) and detect the unused temporary object. I don't recommend this, because using inline is never a panacea, might be ignored by the compiler, and creates tighter coupling, among other issues. The much easier solution is simply to get in the habit of using preincrement if you're not going to use the original value, and then the above optimization will never be needed.

return i->addr; 


return "";

This was one subtle red herring. It's true that both of these statements create temporary string objects, but those objects can't be avoided.

In the past, I've heard people argue that it's better to declare a local string object to hold the return value and have a single return statement that returns that string (string ret; ... ret = i->addr; break; ... return ret;). Although the single-entry/single-exit (SE/SE) discipline often makes for readable (and sometimes faster) code, whether it improves or degrades performance can depend greatly on your actual code and compiler.

In this case, the problem is that creating a single local string object and then assigning it would mean calling string's default constructor and then possibly its assignment operator, instead of just a single constructor, as in our original code. "But," you ask, "how expensive could a plain old string default constructor be?" Well, here's how the "two-return" version performs on one popular compiler:

• With optimizations disabled: 5% faster than a return value string object

• With aggressive optimizations: 40% faster than a return value string object

  
  
  string FindAddr( /*...*/ ) 
  
  
  

This was the second red herring. It may seem like you could avoid a temporary in all return cases simply by declaring the return type to be string& instead of string. Wrong! (In general; see the note below.) If you're lucky, your program will crash as soon as the calling code tries to use the reference, because the local object it refers to no longer exists. If you're unlucky, your code will appear to work and fail intermittently, causing you to spend long nights toiling away in the debugger.

Although I won't pursue it further, I feel obliged to point out that there is a defensible option that allows returning a reference and thus avoiding a temporary. In brief:

const string& 


FindAddr( /* pass emps and name by reference */ )


{


  for( /* ... */ )


  {


    if( i->name == name )


    {


      return i->addr;


    }


  }





  static const string empty;


  return empty;


}

Of course, the function's documentation must now define the valid lifetime of the reference. If the object is found, we are returning a reference to a string inside an Employee object inside the list, so the reference itself is only valid for the lifetime of the Employee object inside the list. Furthermore, the value of the string may change the next time the Employee object is changed.

I won't pursue this option further, because it often doesn't buy you much in practice, and because client programmers can be notoriously forgetful and careless about the lifetimes of the returned reference:

string& a = FindAddr( emps, "John Doe" ); 


emps.clear();


cout << a; // error

When the client programmer does something like this and uses a reference beyond its lifetime, the bug will typically be intermittent and very difficult to diagnose. Indeed, one of the most common mistakes programmers make with the standard library is to use iterators after they are no longer valid, which is pretty much the same thing as using a reference beyond its lifetime (see Item 1 for details about the accidental use of invalid iterators).

There are some other optimization opportunities. Ignoring these for now, here is a corrected version of FindAddr that fixes the unnecessary temporaries. Note that because the list<Employee> parameter is now const, the code has been changed to use const_iterators.

string FindAddr( const list<Employee>& emps, 


                 const string&         name )


{


  list<Employee>::const_iterator end( emps.end() );


  for( list<Employee>::const_iterator i = emps.begin();


       i != end;


       ++i )


  {


    if( i->name == name )


    {


      return i->addr;


    }


  }


  return "";


}