Is returning a std::list costly?

Question

I was wondering if returning a list, instead of returning a pointer to one, was costly in term of performance because if I recall, a list doesn't have a lot of attributes (isn't it something like 3 pointers? One for the current position, one for the beginning and one for the end?).

Answer 1

If you return a std::list by value it won't just copy the list head, it will copy one list node per item in the list. So yes, for a large list it is costly.

If the list is built in the function which is returning it, then you might be able to benefit from the named return value optimisation, to avoid an unnecessary copy. That's specific to your compiler, though. It never applies if for example the list already existed before the function was called (for example if it's a member variable of an object).

A common idiom in C++, to avoid returning containers by value, is to take an output iterator as a parameter. So instead of:

std::list<int> getListOfInts() {
    std::list<int> l;
    for (int i = 0; i < 10; ++i) {
        l.push_back(i);
    }
    return l;
}

You do:

template<typename OutputIterator>
void getInts(OutputIterator out) {
    for (int i = 0; i < 10; ++i) {
        *(out++) = i;
    }
}

Then the caller does:

std::list<int> l;
getInts(std::back_inserter(l));

Often once the compiler has finished inlining and optimising, the code is more or less identical.

The advantage of this is that the caller isn't tied to a particular collection - for instance he can have the items added to a vector instead of a list if that is more useful for the particular circumstances. If he only needs to see each item once, instead of all of them together, then he can save memory by processing them in streaming mode using an output iterator of his own devising.

The disadvantages are the same as with any template code: the implementation must be available to the caller at compile time, and you can end up with a lot of "duplicate" object code for multiple instantiations of the template. Of course you can use the same pattern without using templates, by taking a function pointer (plus a user data pointer if desired) as a parameter and calling it once with each item, or by defining an IntVisitor abstract class, with a pure virtual member function, and having the caller provide an instance of it.

[Edit: T.E.D points out in a comment that another way to avoid the copy without using templates is for the caller to pass in a list by reference. This certainly works, it just gives the caller less flexibility than the template, and hence is not the idiom used by the STL. It's a good option if you don't want the "advantage of this" that I describe above. One of the original intentions behind the STL, though, is to separate "algorithms" (in this case whatever determines the values) from "containers" (in this case, the fact that the values happen to be stored in a list, as opposed to a vector or an array or a self-sorting set, or just printed out without storing them at all).]

Answer 2

I believe, the copy-constructor is called.

Answer 3

It may be costly, in that it will copy every element in the list. More importantly, it has different behaviour: do you want a copy of the list or do you want a pointer to the original list?

Answer 4

If you return by value the copy constructor will be called and the items will be copied one by one. Sometimes you will be saved by the named value optimization as onebyone pointed out.

Your main options to ensure the copy will not take place are:

• Pass in a list by reference to be filled in by the function. This way you tell the function where to put the data and no copy will need to be made because you put it in it's final place.
• Allocate a list on the heap and return it. You should return it in a smart pointer like a std::auto_ptr or a boost::shared_ptr to ensure it gets delete and to be exception safe.

Answer 5

It (as always) depends. The copy constructor may or may not be invoked by return in the following code.

std::list<int> foo() {
  std::list<int> bar;
  // ...
  return bar;
};

It may not be invoked if the compiler applies return value optimization. If the copy-constructor is called, then it is probably more expensive relative to a pointer for larger lists, and if it isn't called, then it is faster to return the straight list (because it avoids a dynamic allocation)

Personally, I don't worry about it and return the straight list. Then, only when my profiler says this a problem do I consider optimizations.