C/C++: efficient way to use a vector returned by a function

Question

Suppose we have a vector called V of type vector<int> which is a private member of a class.

We also have this public function of the class:

 vector<int> getV(){ return V; }

now if I have an instance of this class and all I wanted to do is read the values and find the sum of all the values inside the vector,

I could say something like this:

 MyClass obj;
 //update vector
 size_t i, size;
 size = obj.getV().size();
 int sum = 0;
 for(size_t i = 0; i < size; i++){
     sum += obj.getV().at(i);
 }

or I could say something like this:

  MyClass obj;
 //update vector
 size_t i, size;
 vector<int> myV = obj.getV();
 size = myV.size();
 int sum = 0;
 for(size_t i = 0; i < size; i++){
     sum += myV[i];
 }

in the second case we copy the whole vector to vector myV. However, I'm not sure what exactly happens in the first case, do we use the vector as it already is or do we actually copy the vector every time we call the function getV()?

If no copying occurs, then I believe the first version is more efficient.

However I'm not 100% what exactly is happening.

I guess we could avoid doing any copying at all if we returned a reference to the vector V. So we could have the following function:

vector<int>* getV { return &V; }

and then

 MyClass obj;
 //update vector
 size_t i, size;
 vector<int> * myV = obj.getV();
 size = myV->size();
 int sum = 0;
 for(size_t i = 0; i < size; i++){
     sum += myV->at(i);
 }

however I would like to know what exactly is happening in the first case. Is there anything being copied? Even in the third case we return a pointer, so there is some kind of copying happening.

Thank you in advance

Answer 1

In principal, in the first case you are receiving a copy of the entire vector, calling size() on it, and then it goes out of scope immediately.

In practice, this is so common that modern compilers may be able to recognize it and optimize the copy out entirely. You can read more about this here, for example. The only way to know what's happening on your machine would be to read the compiled assembly code. EDIT: or to do a stack trace as Named did. :)

In the third case, the only thing you're copying is the value of the pointer, which is either 4 or 8 bytes (8 on a 64bit operating system).

If you're worried about efficiency, the best thing to do is always: try it both ways and see which is faster.

Answer 2

The first case is very bad because it can copy your vector several times. The compiler may optimize (or not) your code and hide this issue (it depends on the compiler you use). The best solution is to define a method which return a const reference like

const std::vector<int> & getV() const { return V; }

and use the following code

const vector<int> & myV = obj.getV();
int sum = 0;
for(size_t i = 0, size = myV.size(); i < size; ++i){
 sum += myV[i];
}

by the way the code that sums the vector can be replaced by:

int sum = std::accumulate(myV.begin(), myV.end(), 0);

Answer 3

Not considering possible compiler optimizations, the first version creates a copy of the whole vector on each iteration as a returned value. Which is very inefficient.

I don't think RVO is possible here since V is class member and not a free standing variable.

Here is an example of what is happening. From the tracer output for a vector of 3 elements.

starting loop

[(none)]    Tracer::Tracer(const Tracer&)
[(none)]    Tracer::Tracer(const Tracer&)
[(none)]    Tracer::Tracer(const Tracer&)
[(none)]    Tracer& Tracer::operator=(const Tracer&)
[(none)]    Tracer::~Tracer()
[(none)]    Tracer::~Tracer()
[(none)]    Tracer::~Tracer()

[(none)]    Tracer::Tracer(const Tracer&)
[(none)]    Tracer::Tracer(const Tracer&)
[(none)]    Tracer::Tracer(const Tracer&)
[(none)]    Tracer& Tracer::operator=(const Tracer&)
[(none)]    Tracer::~Tracer()
[(none)]    Tracer::~Tracer()
[(none)]    Tracer::~Tracer()

[(none)]    Tracer::Tracer(const Tracer&)
[(none)]    Tracer::Tracer(const Tracer&)
[(none)]    Tracer::Tracer(const Tracer&)
[(none)]    Tracer& Tracer::operator=(const Tracer&)
[(none)]    Tracer::~Tracer()
[(none)]    Tracer::~Tracer()
[(none)]    Tracer::~Tracer()

Ending loop

As you can see the whole vector (3 elements) is copied on every iteration.

---------------------------------------------------------------------------------------------

A much better implementation would be returning a reference to the vector.

 vector<int>& getV(){ return V; }
           ^^^

Now you won't make any copies. Here is what happens with this version. And this is the output from the tracer.

starting loop
[(none)]    Tracer& Tracer::operator=(const Tracer&)
[(none)]    Tracer& Tracer::operator=(const Tracer&)
[(none)]    Tracer& Tracer::operator=(const Tracer&)
Ending loop

Answer 4

There would be two different tales to tell. One with optimizations enabled and another with optimizations disabled. This article Want Speed? Pass by Value might shed some light.

Answer 5

How about extending your class by inheritance, then you can use all the STL algorithms with MyClass. You define MyClass as an extension of a Sequence Container, after which you inherit the Sequence public interface, and your object can be operated on by STL algorithms. Writing your own loops is o.k., but using STL to the full extent will result in more readible and easily maintainable code, you need to only be careful when working with the algorithms to ensure the efficiency (e.g. using range member functions v.s. single element ones).

#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <numeric>

template
<
    typename Type, 
    template
    <
        typename Element, 
        typename Allocator=std::allocator<Element>
    > class Sequence
>
class MyClass
:
    public Sequence<Type>
{
    public: 

        MyClass()
            :
                Sequence<Type>()
        {}

        template<typename Iterator>
        MyClass(Iterator begin, Iterator end)
        :
            Sequence<Type>(begin, end)
        {}
};

template<typename Type>
class add_element 
{
    Type const& t_; 

    public: 

        add_element(Type const& t)
            :
                t_(t)
        {}

        template<typename Element>
        void operator()(Element & lhs)
        {
            lhs += t_; 
        }
};

using namespace std;

int main(int argc, const char *argv[])
{
    MyClass<int, vector> m;

    m.push_back(0);
    m.push_back(1);
    m.push_back(2);
    m.push_back(3);

    copy(m.begin(), m.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    for_each(m.begin(), m.end(), add_element<int>(-10));

    copy(m.begin(), m.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    MyClass<int,vector>::value_type sum = accumulate(m.begin(), m.end(), 0); 

    cout << "sum = " << sum << endl;


    return 0;
}

Outputs:

0 1 2 3 
-10 -9 -8 -7 
sum = -34

Similarly, you can now work with std::accumulate to compute the sum of elements, std::sort to sort MyObject, etc.