CODEWITHSUNDEEP
c++loopsfor-loopvectorbit-manipulation
Loie Benedicte
Loie Benedicte

Reputation: 149

Adding Two Vectors of Different Size: Optimal Run-time and Optimal Memory Management

I am looking for a run-time-efficient gadget that adds (pairwise) the value of integers stored in two vectors of integers (vector<int> a and vector<int> b) that is memory-efficient as well. The vector sizes will be assumed to be either different or equal.

What I've got is this:

    vector<int> c;
    if( a.size() > b.size() )
    {
       for( size_t i = 0 ; i < b.size() ; ++i )
       {
          c.push_back(a[i]+b[i]);
       }
    else if ( a.size() < b.size() )
    {
       for( size_t i = 0 ; i < a.size() ; ++i )
       {
          c.push_back(a[i]+b[i]);
       }
    }
    else
    {
       for( size_t i = 0 ; i < a.size() ; ++i )
       {
          c.push_back(a[i]+b[i]);
       }
    }

Example:

vector<int> a -> (0)(12)(0)(0)(123)(12)

vector<int> b -> (305)(10)(3)(4)(8201)(230)(0)(0)(0)

vector<int> c -> (305)(22)(3)(4)(8324)(242)(0)(0)(0)

Upvotes: 0

Views: 2203

Answers (2)

jrok
jrok

Reputation: 55425

You can use std::transform:

#include <algorithm>  // for transform and min
#include <functional> // for std::plus
#include <iterator>   // for std::begin, but it's
                      // implicitly included by <vector>
std::vector<int> a;
std::vector<int> b;
auto size = std::min(a.size(), b.size()); 
std::vector<int> c(size); // creates the third vector big enough for results

std::transform(
    begin(a), begin(a)+size, begin(b),
    begin(c), std::plus<int>()
);

Underneath std::transform is just a loop that takes one element from each range (defined by first three parameters), applies the binary function on them (the last parameter, std::plus<int>) and stores the result in the third range (fourth parameter).

It doesn't get any better w.r.t. "runtime efficiency" than iterating through all the elements. Your solution is near optimal. But standard algorithms have the added benefit of clear intent and that the compiler probably knows how to optimize them efficiently.

Upvotes: 3

syam
syam

Reputation: 15089

std::vector<int> c;
const size_t minSize = std::min(a.size(), b.size());
c.reserve(minSize); // avoids useless reallocation
for (size_t i = 0; i < minSize; ++i)
    c.push_back(a[i] + b[i]);

Upvotes: 0

Related Questions