Returning Vectors standard in C++

Question

Now, I know this is a common question, but I haven't been able to really find a straight answer on this. This is really a question about standards. I am working on a project involving the genetic algorithm. But I'm running into a bottleneck when it comes to returning a vector. Is there a "proper" way to do this. Normally I use dynamically allocated arrays, and return a pointer to a newly created array.

obj* func(obj* foo);

That way, everything is efficient and there is no copying of data. Is there an equivalent to doing this with a vector? This vector has objects in it, so returning it by value would be slow I imagine. Is the only solution to pass a "resultant" vector by reference?

void func(vector<obj> &input, vector<obj> &result);

And, on a side note for future reference, is it standard practice to use a vector or other STL container over a dynamically allocated array? Are dynamically allocated arrays only used as a low level tool for designing containers? Are they just a relic of the past?

Answer 1

If you want to be reasonably sure that your function doesn't copy the vector, then:

 void func(const vector<obj> &input, vector<obj> &result);

If you are OK with relying on compiler "return value optimisation" (RTVO) (most good compilers do this):

 vector<obj> func(const vector<obj> &input); 

Return value optimisation is essentially where the compiler knows that we're returning a copy of a vector, so it removes the "extra copy" that would normally be needed in returning the content of, in this case, vector<obj> from func. A C++11 compliant compiler should use the "move constructor" if it is not able to do RTVO, which is also small cost in the whole scheme of things.

If you are happy to dynamically allocate the vector itself, you can return a pointer to it, but this is a poor solution:

vector<obj>* func(const vector<obj> &input);

This solution relies on allocating vector<obj>, which means that something somewhere has to delete the result of the call to func. Maintenance of such code, if func is called many times, gets rather nasty (especially if func gets called lots of times, which may well be the case in a genetics analysis situation).

It is usually hard to achieve a return of a reference, so you are probably doing something wrong if you do - DO NOT DO THIS (unless you know what you are doing and why):

vector<obj>& func(const vector<obj> &input); 

Of course, it REALLY depends on what you are doing with the vectors, and there may be other solutions that are even better, if you give a more concrete example of what you are doing inside the function.

By the way:

obj *func(obj *input)

is a maintenance nightmare, because if obj* is allocated in func, it is now for the caller to maintain this structure.

Finally, ALWAYS when you deal with performance, it's important to benchmark with YOUR compiler, on YOUR machine(s). Different compilers and different systems behave differently - guessing based on looking at the source-code is a very poor solution for understanding what code will be generated and how fast it is.

Answer 2

vector<obj> func(const vector<obj>& input);

All compilers implement RVO either by default or when you turn optimizations on, if you don't turn optimizations on you don't care about performance, so that would not be an issue anyway.

If your compiler is C++11 conforming, then in the worst case instead of copying 1 pointer you will pay for 3 pointers when move semantics kick in, which compared with the cost of allocating the memory is really no cost.

Build a simple meaningfull interface, then measure the performance and bottlenecks and optimize from there.

Depending on your use pattern, if you can reuse the output container, you might want to transform the above into:

void func(vector<obj>& output, const vector<obj>& input);

This will have the same performance when creating a new vector, but if you call this function in a loop, you may be able to avoid a few allocations:

std::vector<obj> output;
for ( ... ) {
   output.clear();
   func(output, input);

// compare with
for ( ... ) {
   std::vector<obj> output = func(input);

In the first block of code, if all of the vectors are of the same size, the clear() will remove the elements but leave the buffer intact, so that the next call to func need not allocate. In the second case it needs to allocate inside func and will deallocate at the end of the scope.

This is a slightly uglier interface to use, so I would opt for the first one (which semantically is cleaner), and use the second only if the first proves to have an issue with multiple allocations.

Answer 3

If you can, always use a reference (&) instead of using the class itself. This even refers to smart pointers (std::shared_ptr), because you will avoid an extra copy even of the pointer itself. And just to make sure that your returned pointer does not get overwritten, pre-pend const to it, so:

void Function(const std::shared_ptr<SomeClass> &someObject);

Answer 4

Is the only solution to pass a "resultant" vector by reference?

No. You can also pass an iterator, like algorithms do:

void func( InputIt first, InputIt last, OutputIt res);

you can then make this a template:

template< class InputIt, class OutputIt >
void func( InputIt first, InputIt last, OutputIt res);