Returning container from function: optimizing speed and modern style

Question

Not entirely a question, although just something I have been pondering on how to write such code more elegantly by style and at the same time fully making use of the new c++ standard etc. Here is the example

Returning Fibonacci sequence to a container upto N values (for those not mathematically inclined, this is just adding the previous two values with the first two values equal to 1. i.e. 1,1,2,3,5,8,13, ...)

example run from main:

std::vector<double> vec;
running_fibonacci_seq(vec,30000000);

1)

template <typename T, typename INT_TYPE>
    void running_fibonacci_seq(T& coll, const INT_TYPE& N)
    {
        coll.resize(N);
        coll[0] = 1;
        if (N>1) {
        coll[1] = 1;
        for (auto pos = coll.begin()+2;
            pos != coll.end();
            ++pos)
        {
            *pos = *(pos-1) + *(pos-2);
        }
        }
    }

2) the same but using rvalue && instead of & 1.e.

void running_fibonacci_seq(T&& coll, const INT_TYPE& N)

EDIT: as noticed by the users who commented below, the rvalue and lvalue play no role in timing - the speeds were actually the same for reasons discussed in the comments

results for N = 30,000,000

Time taken for &:919.053ms

Time taken for &&: 800.046ms

Firstly I know this really isn't a question as such, but which of these or which is best modern c++ code? with the rvalue reference (&&) it appears that move semantics are in place and no unnecessary copies are being made which makes a small improvement on time (important for me due to future real-time application development). some specific ''questions'' are

a) passing a container (which was vector in my example) to a function as a parameter is NOT an elegant solution on how rvalue should really be used. is this fact true? if so how would rvalue really show it's light in the above example?

b) coll.resize(N); call and the N=1 case, is there a way to avoid these calls so the user is given a simple interface to only use the function without creating size of vector dynamically. Can template metaprogramming be of use here so the vector is allocated with a particular size at compile time? (i.e. running_fibonacci_seq<30000000>) since the numbers can be large is there any need to use template metaprogramming if so can we use this (link) also

c) Is there an even more elegant method? I have a feeling std::transform function could be used by using lambdas e.g.

    void running_fibonacci_seq(T&& coll, const INT_TYPE& N)
    {
        coll.resize(N);
        coll[0] = 1;
        coll[1] = 1;
        std::transform (coll.begin()+2,
                coll.end(),         // source
                coll.begin(),       // destination
                [????](????) {      // lambda as function object
                    return ????????;
                });
    }

[1] http://cpptruths.blogspot.co.uk/2011/07/want-speed-use-constexpr-meta.html

Answer 1

Due to "reference collapsing" this code does NOT use an rvalue reference, or move anything:

template <typename T, typename INT_TYPE>
void running_fibonacci_seq(T&& coll, const INT_TYPE& N);

running_fibonacci_seq(vec,30000000);

All of your questions (and the existing comments) become quite meaningless when you recognize this.

Answer 2

Profile this:

#include <vector>
#include <cstddef>
#include <type_traits>

template <typename Container>
Container generate_fibbonacci_sequence(std::size_t N)
{
    Container coll;
    coll.resize(N);
    coll[0] = 1;
    if (N>1) {
      coll[1] = 1;
      for (auto pos = coll.begin()+2;
        pos != coll.end();
        ++pos)
      {
        *pos = *(pos-1) + *(pos-2);
      }
    }
    return coll;
}

struct fibbo_maker {
  std::size_t N;
  fibbo_maker(std::size_t n):N(n) {}
  template<typename Container>
  operator Container() const {
    typedef typename std::remove_reference<Container>::type NRContainer;
    typedef typename std::decay<NRContainer>::type VContainer;
    return generate_fibbonacci_sequence<VContainer>(N);
  }
};

fibbo_maker make_fibbonacci_sequence( std::size_t N ) {
  return fibbo_maker(N);
}

int main() {
  std::vector<double> tmp = make_fibbonacci_sequence(30000000);
}

the fibbo_maker stuff is just me being clever. But it lets me deduce the type of fibbo sequence you want without you having to repeat it.

Answer 3

Obvious answer:

std::vector<double> running_fibonacci_seq(uint32_t N);

Why ?

Because of const-ness:

std::vector<double> const result = running_fibonacci_seq(....);

Because of easier invariants:

void running_fibonacci_seq(std::vector<double>& t, uint32_t N) {
    // Oh, forgot to clear "t"!
    t.push_back(1);
    ...
}

But what of speed ?

There is an optimization called Return Value Optimization that allows the compiler to omit the copy (and build the result directly in the caller's variable) in a number of cases. It is specifically allowed by the C++ Standard even when the copy/move constructors have side effects.

So, why passing "out" parameters ?

• you can only have one return value (sigh)
• you may wish the reuse the allocated resources (here the memory buffer of t)