Returning stl containers from functions

Question

What is the best way (performance-wise) of returning stl containers from a function? The container returned would usually contain several thousands of items.

Method 1:

typedef std::list<Item> ItemContainer;

ItemContainer CreateManyItems() {
    ItemContainer result;

    // fill the 'result' ...

    return result;
}

ItemContainer a = CreateManyItems();

Method 2:

void CreateManyItems(ItemContainer &output) {
    ItemContainer result;

    // fill the 'result' ...

    output.swap(result);
} 

ItemContainer a;
CreateManyItems(a);

Method 3:

void std::auto_ptr<ItemContainer> CreateManyItems() {
    std::auto_ptr<ItemContainer> result(new ItemContainer);

    // fill the 'result' ...

    return result;
}

std::auto_ptr<ItemContainer> a = CreateManyItems();

Or is there any better way?

Answer 1

None: if you just want to fill std::list with items, then you can use std::fill or std::fill_n or a combination of standard library functions.

It's not clear how exactly you want to fill your list, so I can't comment on your code precisely. If possible, use the standard library. If you cannot, then go for Method 1, and the compiler may optimize away the return value in your code eliding the unnecessary copies, as most compilers implement RVO.

See these articles on copy elision and return value optimization (RVO):

• Copy elision – Wikipedia
• Copy elision – cppreference

Related questions:

• In C++, is it still bad practice to return a vector from a function?
• Returning a c++ std::vector without a copy?

An article by Dave Abrahams:

• Want Speed? Pass by Value

---

I would still emphasize this: have you seen all the generic functions provided by <algorithm> header? If not, then I would suggest you to first look into them and see if any of them (or a combination of them) can do what you want to do in your code.

If you want to create and fill the list, then you can use std::generate() or std::generate_n function.

Answer 2

I usually use method 4 (almost identical to method 2):

void fill(ItemContainer& result) {
    // fill the 'result'
}

ItemContainer a;
fill(a);

Answer 3

I would use Method 1 and hope that the compiler optimizes away the copy of the return value.

Named Return Value Optimization

Answer 4

Method 1 is fine. It's called copy ellision, and you will find it automatically applied to transform Method 1 into Method 2, basically, but it's way less ugly to maintain.

A linked list? If you're even vaguely performance-orientated, use a std::vector.

Answer 5

Method 1 can benefit from copy elision, but the following very similar code cannot:

ItemContainer a = CreateManyItems();
// do some stuff with a
a = CreateManyItems();
// do some different stuff with a

This requires C++0x move semantics in order to efficiently avoid copying the container. When you design your function, you don't know how clients are going to want to use it, so relying on copy elision in this way might catch someone out with an unpleasant performance hit. Their fix in C++03 would be as follows, and they should be alert to situations where they need it:

ItemContainer a = CreateManyItems();
// do some stuff with a
CreateManyItems().swap(a);

Since this is basically the same as Method 2, you could offer both 1 and 2, as overloads, which hints to the caller that they should think about a potential performance trap.

Provided that the Items in the collection don't refer to each other, my preferred form of the API is as follows, but it depends what kind of interface you're exposing - because it's a template the implementation must be available when the caller is compiled (unless you can predict in advance the types it will be used with and extern those specializations):

template <typename OutputIterator>
void CreateManyItems(OutputIterator out) {
     *out++ = foo; // for each item "foo"
}

ItemContainer a;
CreateManyItems(std::back_inserter(a));
// do some stuff with a
a.clear();
CreateManyItems(std::back_inserter(a));

Now, if the caller would prefer to have the items in a deque, because they want random access, then they just need to tweak their code:

std::deque<Item> a;
CreateManyItems(std::back_inserter(a));

Or if they don't need them in a collection at all, they could write a streaming algorithm that does its work in their output iterator, and save a lot of memory.

You could instead write an iterator class that generates the Items one after another, but that tends to be a bit more fiddly because the control flow is "inside out", and doesn't necessarily make the callers code look any nicer (witness istream_iterator).

Answer 6

Of these, number three has probably the best performance. Perhaps slightly better, and more flexible, would be a variation of number 2 without the swap -- just filling the container directly. Of course, that wouldn't be exception-safe.

Answer 7

There is a much better way and I'm surprised none of the answers has pointed this out. You basically use output iterator. This makes your function independent of container and much more flexible.

template<typename OutIter>
void CreateManyItems(OutIter it)
{
    //generate some data
    *it++ = 1;
    *it++ = 2;
    *it++ = 3;
}

Here's how you use it:

void main()
{
    //use array as output container
    int arr[3];
    CreateManyItems(arr);

    //use vector as output container
    std::vector<float> v;
    CreateManyItems(std::back_inserter(v));
}

Answer 8

Encapsulate away the container in an appropriate class using the pimpl idiom. Then pass/return that class by value.