Acessing Values only at certain indexes using iterators

Question

I have a trouble understanding std::accumulate. Can it be used to add up the values at only even indices from a vector?

int rob(vector<int>& nums) {

    int a = std::accumulate(nums.begin(), nums.end(), 0);

   std::cout <<" a: " <<a; 
   return a;

}

So if I have a vector y = {1, 2, 3, 4}

How could I change the above code, so that std::accumulate only iterates over indices [0] and [2]. Is that even possible using std::accumulate?

Answer 1

You have a couple of choices. The quick and (really) dirty way is to walk across the whole collection, and invoke a function that keeps track of the current index, and ignores the values at the odd indices. It works, but it's ugly at best, and more importantly it's wrong on a rather fundamental level, forcing what's supposed to be an accumulation function to take responsibility for doing iteration. In short, this is much more of a problem than a solution.

The clean way would be to realize that visiting every other item in the collection is really about iteration, not about a specific algorithm (std::accumulate or any other). So what we should be using here is an iterator that visits the items we want to visit. Here's a minimal implementation:

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

template <class Iterator>
class n_iterator { 
     Iterator i;
     size_t n;
public:
    // We construct this iterator from some other iterator, plus a "step" value
    // to tell us how many items to skip forward when `++` is applied.
    n_iterator(Iterator i, size_t n) : i(i), n(n) {}

    // When you dereference this iterator, it's equivalent to dereferencing
    // the underlying iterator.
    typename std::iterator_traits<Iterator>::value_type operator *() { return *i; }

    // ...but when you increment it, you move ahead N places instead of 1.
    n_iterator &operator++() { std::advance(i, n); return *this; }

    // iterator comparisons just compare the underlying iterators.
    bool operator==(n_iterator const &other) const { return i == other.i; }
    bool operator!=(n_iterator const &other) const { return i != other.i; }
};

int main() { 
    std::vector<int> y { 1, 2, 3, 4};
    auto total = std::accumulate(y.begin(), y.end(), 0);

    std::cout << "total: " << total << "\n";

    auto skip_total = std::accumulate(n_iterator(y.begin(), 2), n_iterator(y.end(), 2), 0);

    std::cout << "Skipped total: " << skip_total << "\n";
}

This implementation seems to suffice for g++ 7.1 to compile the code, but for real use, you should probably implement the entire interface for an iterator (e.g., as a minimum, it should really have definitions for value_type, reference, etc.)

For the moment, this also supplies only a forward iterator, regardless of the underlying iterator. Depending on the situation (and category of underlying iterator) you could also support bidirectional and/or random iteration.

Answer 2

Here you are

int rob( const vector<int>& nums) {

    int i = 0;
    int a = std::accumulate(nums.begin(), nums.end(), 0,
                            [&i]( const auto &acc, const auto &value )
                            {
                                return ( i ^= 1 ) ? acc + value : acc;
                            } );

   std::cout <<" a: " <<a; 
   return a;

}

Here is a demonstrative program

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

int rob( const std::vector<int> &nums )
{
    int i = 0;

    int a = std::accumulate( std::begin( nums ), std::end( nums ), 0,
                             [&i]( const auto &acc, const auto &value )
                             {
                                return ( i ^= 1 ) ? acc + value : acc;
                             } );

   return a;
}

int main() 
{
    std::vector<int> v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    std::cout << rob( v ) << '\n';

    return 0;
}

Its output is

20

You can add one more parameter to the function that you could select whether to sum even or odd numbers. For example

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

int rob( const std::vector<int> &nums, bool odds = false )
{
    int i = odds;

    int a = std::accumulate( std::begin( nums ), std::end( nums ), 0,
                             [&i]( const auto &acc, const auto &value )
                             {
                                return ( i ^= 1 ) ? acc + value : acc;
                             } );

   return a;
}

int main() 
{
    std::vector<int> v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    std::cout << rob( v ) << '\n';

    std::cout << rob( v, true ) << '\n';
    return 0;
}

The program output is

20
25

In this case you can remove the declaration of the variable i. For example

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

int rob( const std::vector<int> &nums, bool odds = false )
{
    int a = std::accumulate( std::begin( nums ), std::end( nums ), 0,
                             [&odds]( const auto &acc, const auto &value )
                             {
                                return ( odds = !odds ) ? acc + value : acc;
                             } );

   return a;
}

int main() 
{
    std::vector<int> v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    std::cout << rob( v ) << '\n';

    std::cout << rob( v, true ) << '\n';
    return 0;
}