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