How the vector gets returned even though it is a local variable inside a method of a class

Question

The vector<int> bfs is local to the method bfs_of_graph then how can we return the vector as it would be erased in the memory and only garbage values should be printed in the calling method. But I find the values are present. How ?

class Solution {
public:
    vector<int> bfs_of_graph(int no_of_nodes, vector<int> adj_list[]) {
        queue<int> qt;
        vector<int> bfs;
        vector<int> visited(no_of_nodes + 1, 0);
        
        for (int i = 1; i <= no_of_nodes; ++i) {
            // Node in graph not visited
            if (visited[i] == 0) {
                qt.push(i); 
                visited[i] = 1;
                while (!qt.empty()) {
                    int node = qt.front(); 
                    qt.pop();
                    bfs.push_back(node);
                    
                    for (auto ele: adj_list[node]) {
                        if (visited[ele] == 0) {
                            qt.push(ele);
                            visited[ele] = 1;
                        }
                    }
                }
                
            }
        }
        return bfs;
    }
};

Originally it returned a copy of the local. This copy is actually usually avoided, either by an optimization called RVO or copy-elision (https://en.wikipedia.org/wiki/Copy_elision), or by using move semantics (https://stackoverflow.com/questions/3106110/what-is-move-semantics). — wohlstad, May 14 '22 at 15:00

score 2 · Answer 1 · edited May 14 '22 at 17:04

Until C++11, the basic behavior according to the standard was to invoke the copy constructor of the returned object (vector<int> in your case). However, according to the as-if rule, some compilers and optimizers applied the copy-elision optimization (also known as RVO).

C++11 introduced move semantics. In some cases, local objects can be moved into the caller's object. You can see here for more info: C++11 rvalues and move semantics confusion (return statement). Some compilers and optimizers still continued to use the copy-elision optimization when appropriate.

C++17 introduced guaranteed copy-elision in certain cases. See here: How does guaranteed copy elision work?.

The bottom line: even without any modern C++ stuff, the code you mentioned can work by creating a copy of the local object (thus constructing the object on the caller side). But nowadays, usually there will be no copy (either a move, or copy-elision all the way).

score 1 · Answer 2 · answered May 14 '22 at 15:18

If you just look at it then you see that the return type is vector<int>. It's not a pointer nor a reference. The vector is returned as value. Which means it gets copied.

Copied to where? Say you have the following:

std::vector<int> v = bfs_of_graph(...);

Internally the compiler places v on the stack in passes the address of v in the structure return register. The return statement would then copy the temporary bfs into the object pointer to by the structure return register.

This is how it used to be. But over time people noticed that this can be rather slow and wanted to get rid of the extra copy on return and that is now possible in modern C++.

One of the ways the standard specified that is RVO (return value optimization) (Copy_elision. This is what the compiler will use in your example. There is only a single return bfs; so when you declare vector<int> bfs; at the start of the function that doesn't actually create a new object. Instead the compiler uses the object from the structure return register in place of bfs. So the function will modify the v from the caller directly and never have a temporary for bfs at al.

In cases where this is not possible there is another mechanism that at least reduces the cost of copying called move semantic. For a vector move semantic means that the destination vector will take over the data part of the source vector. So it only copies the size, capacity and data pointer, which takes constant time. None of the data (on the heap) itself is copied.

How the vector gets returned even though it is a local variable inside a method of a class

2 Answers2