Efficient way to return a std::vector in c++

How much data is copied, when returning a std::vector in a function and how big an optimization will it be to place the std::vector in free-store (on the heap) and return a pointer instead i.e. is:

std::vector *f() < std::vector *result = new std::vector(); /* Insert elements into result */ return result; >

std::vector f() < std::vector result; /* Insert elements into result */ return result; >

As answers flow in, it may help you to clarify whether you are using C++03 or C++11. The best practices between the two versions vary quite a bit.

@Morten - I didn't get your question. The way to do what I suggested is what you wrote void f(std::vector &result) . Note, that this is a comment, not an answer. I just suggested one more method, you didn't mention.

9 Answers 9

In C++11, this is the preferred way:

std::vector f(); 

That is, return by value.

With C++11, std::vector has move-semantics, which means the local vector declared in your function will be moved on return and in some cases even the move can be elided by the compiler.

@LeonidVolnitsky: Yes if it is local. In fact, return std::move(v); will disable move-elision even it was possible with just return v; . So the latter is preferred.

@juanchopanza: I dont think so. Before C++11, you could argue against it because the vector will not be moved; and RVO is a compiler-dependent thing! Talk about the things from 80s & 90s.

My understanding about the return value (by value) is: instead of 'been moved', the return value in the callee is created on the caller's stack, so all operations in the callee are in-place, there is nothing to move in RVO. Is that correct?

You should return by value.

The standard has a specific feature to improve the efficiency of returning by value. It's called "copy elision", and more specifically in this case the "named return value optimization (NRVO)".

Compilers don't have to implement it, but then again compilers don't have to implement function inlining (or perform any optimization at all). But the performance of the standard libraries can be pretty poor if compilers don't optimize, and all serious compilers implement inlining and NRVO (and other optimizations).

When NRVO is applied, there will be no copying in the following code:

std::vector f() < std::vectorresult; . populate the vector . return result; > std::vector myvec = f(); 

But the user might want to do this:

std::vector myvec; . some time later . myvec = f(); 

Copy elision does not prevent a copy here because it's an assignment rather than an initialization. However, you should still return by value. In C++11, the assignment is optimized by something different, called "move semantics". In C++03, the above code does cause a copy, and although in theory an optimizer might be able to avoid it, in practice its too difficult. So instead of myvec = f() , in C++03 you should write this:

std::vector myvec; . some time later . f().swap(myvec); 

There is another option, which is to offer a more flexible interface to the user:

template void f(OutputIterator it)

You can then also support the existing vector-based interface on top of that:

std::vector f() < std::vectorresult; f(std::back_inserter(result)); return result; > 

This might be less efficient than your existing code, if your existing code uses reserve() in a way more complex than just a fixed amount up front. But if your existing code basically calls push_back on the vector repeatedly, then this template-based code ought to be as good.

Upvoted the really best and detailed answer. However, in your swap() variant (for C++03 without NRVO) you still will have one copy-constructor copy made inside f(): from variable result to a hidden temporary object which will be at last swapped to myvec.

@JenyaKh: sure, that's a quality-of-implementation issue. The standard didn't require that the C++03 implementations implemented NRVO, just like it didn't require function inlining. The difference from function inlining, is that inlining doesn't change the semantics or your program whereas NRVO does. Portable code must work with or without NRVO. Optimised code for a particular implementation (and particular compiler flags) can seek guarantees regarding NRVO in the implementation's own documentation.

A common pre-C++11 idiom is to pass a reference to the object being filled.

Then there is no copying of the vector.

void f( std::vector & result ) < /* Insert elements into result */ >

@Nawaz I agree. I'm not sure what the best practice is now on SO regarding questions on C++ but not specifically C++11. I suspect I should be inclined to give C++11 answers to a student, C++03 answers to someone waist-deep in production code. Do you have an opinion?

Actually, after the release of C++11 (which is 19 months old), I consider every question to be C++11 question, unless it is explicitly stated to be C++03 question.

It's time I post an answer about RVO, me too.

If you return an object by value, the compiler often optimizes this so it doesn't get constructed twice, since it's superfluous to construct it in the function as a temporary and then copy it. This is called return value optimization: the created object will be moved instead of being copied.

If the compiler supports Named Return Value Optimization (http://msdn.microsoft.com/en-us/library/ms364057(v=vs.80).aspx), you can directly return the vector provide that there is no:

1. Different paths returning different named objects
2. Multiple return paths (even if the same named object is returned on all paths) with EH states introduced.
3. The named object returned is referenced in an inline asm block.

NRVO optimizes out the redundant copy constructor and destructor calls and thus improves overall performance.

There should be no real diff in your example.

vector getseq(char * db_file) 

And if you want to print it on main() you should do it in a loop.

int main() < vectorstr_vec = getseq(argv[1]); for(vector::iterator it = str_vec.begin(); it != str_vec.end(); it++) < cout > 

follow code will works without copy constructors:

std::vector foo() < std::vectorv; v.resize(16, 0); return std::move(v); // move the vector > 

After, You can use foo routine for get the vector without copy itself:

std::vector&& moved_v(foo()); // use move constructor 

Result: moved_v size is 16 and it filled by [0]

As nice as "return by value" might be, it's the kind of code that can lead one into error. Consider the following program:

 #include #include #include using namespace std; static std::vector strings; std::vector vecFunc(void) < return strings; >; int main(int argc, char * argv[]) < // set up the vector of strings to hold however // many strings the user provides on the command line for(int idx=1; (idx// now, iterate the strings and print them using the vector function // as accessor for(std::vector::interator idx=vecFunc().begin(); (idx!=vecFunc().end()); ++idx)< cout c_str() return 0; >; 

• Q: What will happen when the above is executed? A: A coredump.
• Q: Why didn't the compiler catch the mistake? A: Because the program is syntactically, although not semantically, correct.
• Q: What happens if you modify vecFunc() to return a reference? A: The program runs to completion and produces the expected result.
• Q: What is the difference? A: The compiler does not have to create and manage anonymous objects. The programmer has instructed the compiler to use exactly one object for the iterator and for endpoint determination, rather than two different objects as the broken example does.

The above erroneous program will indicate no errors even if one uses the GNU g++ reporting options -Wall -Wextra -Weffc++

If you must produce a value, then the following would work in place of calling vecFunc() twice:

 std::vector lclvec(vecFunc()); for(std::vector::iterator idx=lclvec.begin(); (idx!=lclvec.end()); ++idx). 

The above also produces no anonymous objects during iteration of the loop, but requires a possible copy operation (which, as some note, might be optimized away under some circumstances. But the reference method guarantees that no copy will be produced. Believing the compiler will perform RVO is no substitute for trying to build the most efficient code you can. If you can moot the need for the compiler to do RVO, you are ahead of the game.