使用迭代器仅在特定索引处访问值

Question

我对 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是否可行？

- ichherzcplusplus

---

std::remove_if 似乎是需要的。也就是说，使用 std::accumulate 是正确的。修改的是迭代的范围。请参阅 http://www.cplusplus.com/reference/algorithm/remove_if/，其中有一些示例。 - Thomas Bitonti

Answer 1

这里是您需要的内容

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

- Vlad from Moscow

---

你能解释一下Lambda函数是如何工作的吗？我不明白它是如何跳过奇数索引的值的。 - ichherzcplusplus

@learningtocodecplusplus 表达式 i ^= 1 控制索引。如果 i 等于 0，则将表达式设置为 1，并返回条件语句的 acc + value 部分。如果 i 等于 1，则表达式 i ^= 1 等于 0，将返回 acc 的原始值。 - Vlad from Moscow

这段话的意思是：这种方法过于复杂了。它会在0和1之间改变I的值，因此只会累加每隔一个元素。如果i是一个布尔值，在true和false之间交替，那就更清晰了。 - Marshall Clow

这个 BinaryOperation 是否保证每个元素只被执行一次，并且按顺序执行？我认为不是，你的解决方案依赖于此。 - Lightness Races in Orbit

@LightnessRacesinOrbit 我刚刚查看了标准。 :) - Vlad from Moscow

Answer 2

你有几种选择。快速且（真的）不太干净的方法是遍历整个集合，并调用一个函数来跟踪当前索引，并忽略奇数索引处的值。它可以工作，但它最好还是很丑陋的，并且更重要的是，在根本上它是错误的，它强制了本应该是累加功能的迭代责任。简而言之，这是一个问题，而不是解决方案。

干净的方法是意识到访问集合中每隔一个项实际上是关于“迭代”的，而不是关于特定算法（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 等）。

目前，无论底层迭代器是什么，它都只提供前向迭代器。根据情况（以及底层迭代器的类别），你也可以支持双向和/或随机访问。

- Jerry Coffin

---

这与 boost::strided_iterator 非常相似。 - Marshall Clow

@MarshallClow：啊，原来是这样——我猜我应该已经猜到Boost已经有这个了。 - Jerry Coffin