Доступ к значениям только в определенных индексах с использованием итераторов - PullRequest
Новая
       15

Доступ к значениям только в определенных индексах с использованием итераторов

7 голосов
/ 04 октября 2019

У меня проблемы с пониманием std::accumulate. Можно ли его использовать для суммирования значений только по четным индексам вектора? 

int rob(vector<int>& nums) {

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

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

}

Итак, если у меня есть vector y = {1, 2, 3, 4}

Как я могу изменить приведенный выше код, чтобы std::accumulate перебирал только индексы [0] и [2]. Это возможно даже с помощью std::accumulate?

Ответы [ 2 ]

3 голосов
/ 04 октября 2019

У вас есть несколько вариантов. Быстрый и (действительно) грязный способ - пройтись по всей коллекции и вызвать функцию, которая отслеживает текущий индекс и игнорирует значения с нечетными индексами. Это работает, но в лучшем случае уродливо, и что еще более важно, это неправильно на довольно фундаментальном уровне, заставляя то, что должно быть функцией накопления, взять на себя ответственность за выполнение итерации. Короче говоря, это гораздо большая проблема, чем решение.

Чистым способом было бы осознать, что посещение любого другого элемента в коллекции - это, действительно, итерация , а не конкретныйалгоритм (std::accumulate или любой другой). Так что мы должны использовать здесь итератор, который посещает элементы, которые мы хотим посетить. Вот минимальная реализация: 

#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";
}

Эта реализация кажется достаточной для g ++ 7.1 для компиляции кода, но для реального использования вам, вероятно, следует реализовать весь интерфейс для итератора (например, как минимум, этодолжно действительно иметь определения для value_type, reference и т. д.)

На данный момент это также предоставляет только прямой итератор, независимо от базового итератора. В зависимости от ситуации (и категории основного итератора) вы также можете поддерживать двунаправленную и / или случайную итерацию.

3 голосов
/ 04 октября 2019

Вот вам 

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;

}

Вот демонстрационная программа 

#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;
}

Ее вывод 

20

Вы можете добавить еще один параметр в функциючто вы можете выбрать, суммировать ли четные или нечетные числа. Например, 

#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;
}

Вывод программы: 

20
25

В этом случае вы можете удалить объявление переменной i. Например 

#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;
}
...