Exploiting fact that elements of vector are stored in heap?

Question

Lets say you have something like this

#include <iostream>
#include <vector>


using namespace std;

vector<int> test()
{
    vector <int> x(1000);
    for (int i = 0; i < 1000; i++)
    {
        x[i] = 12345;
    }
    return x;
}

int main(int argc, const char * argv[])
{
    vector<int> a = test();
    return 0;
}

where within a function you create a vector and fill it with some elements (in this case I chose 12345 but they won't necessarily all be the same).

I have read that the elements of the vector are stored on the heap whereas the reference and header data are stored on the stack. In the above code, when x is returned a copy-constructor must be called, and this takes O(n) time to copy all the elements into a new vector.

However, is it possible to take advantage of the fact that all the elements already exist on the heap in order to just return something like a pointer to those elements and later just create a vector that uses that pointer in order to point to those exact same elements — thus avoiding the need to make a copy all the elements of a vector?

[`std::move`](http://en.cppreference.com/w/cpp/algorithm/move) is a good start. — Captain Obvlious, Jul 07 '14 at 01:39
@CaptainObvlious, No, don't do that explicitly to move a return value out. — chris, Jul 07 '14 at 01:40
@Xaqq, It's moved out for you already (if NRVO doesn't happen), and if you then make the return type an rvalue reference, you start getting into [this problem](http://stackoverflow.com/questions/6441218/can-a-local-variables-memory-be-accessed-outside-its-scope). — chris, Jul 07 '14 at 01:41
As chris intimates, there's only one vector ever constructed in your example program using any acceptable compiler. Regarding `std::move()` the Captain mentions: I made that pessimization once as well... — Deduplicator, Jul 07 '14 at 01:42
@chris Sure it's done automagically, but it won't cause trouble manually moving the return value. — Xaqq, Jul 07 '14 at 01:50
@chris Yes, but by trouble I meant dangerous problem (like the memory error you linked). — Xaqq, Jul 07 '14 at 01:55
@Xaqq, Well, it's easily enough for someone to extrapolate on that and change a couple things to rvalue references to match the `move` call, and then boom. — chris, Jul 07 '14 at 01:56

score 8 · Accepted Answer · answered Jul 07 '14 at 01:44

The compiler does this for you, freeing you up to write nice , easy-to-read code, rather than mangling your code for the sake of optimization.

When you return a value for a function, the compiler is allowed to elide the return value object. The net effect is that the compiler can just create x in the actual memory location of a.

Even if it doesn't do this (e.g. it chooses not to for some reason, or you disable it by a compiler switch), then there is still the possibility of a move.

When a move happens, the vector will just transfer ownership of the pointer from x to the return value, and then from the return value to a. This leaves x etc. as an empty vector, which is then correctly destroyed.

You could explore this by writing a test class (instead of vector<int>) which prints something out for its default constructor, copy-constructor, and move-constructor, e.g.

#include <iostream>

struct A
{
    A() { std::cout << "default\n"; }
    A(A const &) { std::cout << "copy\n"; }
    A(A &&) { std::cout << "move\n"; }
};

A func() { A a; return a; }

int main()
{
    A b (func());
}

Output with g++:

default

Output with g++ -fno-elide-constructors:

default
move
move

Exploiting fact that elements of vector are stored in heap?

1 Answers1