在C++中，每隔n个元素的数组

Question

有没有比下面简单的for循环更有效地获取数组中每个第二个（或者每个N个）元素的方法？例如，使用通用算法？

#include<iostream>
using namespace std;

int main()
{
    const int a_size = 6, b_size = 3;
    int a[a_size] = {1, 3, 6, 3, 2, 7}; 
    int b[b_size];
    int bx = 0;
    for ( int ax = 0; ax < a_size; ++ax )
    {   
        if (ax % 2 == 0)
            b[bx++] = a[ax];  
    }   
}

- cpp

---

使用for (int ax = 0; ax < a_size; ax += 2)或for (int ax = 0; ax < a_size; ax += N)。其中 N 是您选择的一个常量值。 - vdenotaris

请注意，在您的示例中，b 的奇数元素是未初始化的值。 - kfsone

它们不是（复制由bx跟踪）。但是，如果相对于步骤（例如示例中的2）给出了错误的b_size值，则目标数组中将存在未初始化的值。 - Luis Machuca

Answer 1

for (int ax = 0; ax < a_size; ax += 2)

如果a_size接近INT_MAX，要小心。

- Pete Becker

---

只需确保 a_size <= INT_MAX - 2。但如果您的数组大小接近 INT_MAX，那么您做错了什么。 - Cole Tobin

@Cole"Cole9"Johnson - 是的，当跳过2个元素时是这样。但问题更普遍地涉及到N个元素。 - Pete Becker

@PeteBecker 我打算将其作为一个单独的问题来问，但我需要以递归的方式执行此操作。第一次它应该跳过 n ，然后是 2n，然后是 4n 等等。 - gansub

Answer 2

一个循环就足够了。正如Pete所指出的那样，你可以避免模数测试。

 for (int ax = 0; ax < a_size; ax += 2)
   ...

C++提供了通过valarray头文件支持切片的功能(例如，请参考std::slice_array)。

我不知道这是否符合您的要求，它旨在用于大量的数值计算。如果您不确定，我认为使用简单的循环是正确的答案。

- Philipp Claßen

Answer 3

如果您所说的高效是指更快速且内存占用更小，那么我建议使用指针而非数组访问。例如，以下代码展示了如何使用指针实现您想要的功能。

int main() {
    const int a_size = 6, b_size = 3;
    int a[a_size] = {1, 3, 6, 3, 2, 7}; 
    int b[b_size];
    int* a_ptr = a;
    int* a_end_ptr = a_ptr + a_size;
    int* b_ptr = b;
    while(a_ptr < a_end_ptr) {
        *b_ptr = *a_ptr;
        b_ptr++;
        a_ptr += 2;
    }
}

这个例子应该比数组访问的例子稍微快一些，我鼓励你自己计时来确认。然而，在进行这些优化时，你应该始终注意是否在程序的整体方案中起到了作用（不要浪费时间）。

- JustKash

---

这段代码存在潜在的错误。如果 a_size 是一个奇数，你会将 a_ptr 的值增加到数组的末尾并继续执行直到程序崩溃。 - Blastfurnace

@Kai Petzke，你也说得对，编译器可以将循环优化为指针，但我认为写明确的代码很重要，而且我不认为编译器优化应该成为写未经优化的代码的借口（如果速度和内存很重要）。 - JustKash

如果指针指向同一数组的元素或最后一个元素之后，您可以通过这种方式进行比较。与崩溃不同，您的“修复”代码现在具有未定义的行为。 - Blastfurnace

您可能正在比较指针数组结束后的__两个元素__。语言标准明确规定结果是未定义的。当代码具有未定义行为时，“在我的机器上可以运行”不是一个令人信服的论据。 - Blastfurnace

换句话说，如果a_ptr指向数组的末尾，那么无法保证将任意偏移量添加到a_ptr仍然是有效地址，并且将大于a_ptr。 - Blastfurnace

Answer 4

你可以轻松地创建一个every_n谓词，并将其用于筛选copy_if等所需的内容。这是您可以获得的最通用的内容。

一个“每n个元素”谓词的近似（注意：尚未经过测试）示例：

/**
 @brief Un predicado que retorna @c true cada @a n invocaciones.
**/
template <typename Integer>
struct every_n {
    static_assert (std::numeric_limits<Integer>::is_integer, "Must behave like an integer");
    public:
    explicit every_n (Integer const& e)
    : n(e), x(1) {}

    every_n (every_n const& E)
    : n(E.n), x(E.x) {}

    bool operator () (...) {
        if (x<n) { ++x; return false; }
        else { x=Integer(1); return true; }
    }

    private:
    Integer x;
    const Integer n;
};

// "make_" idiom
template <typename Integer>
every_n<Integer> every (Integer const& c) { return every_n<Integer>(c); }


// sample usage
# include required headers, etc
using namespace std;
const int a_size = 6, b_size = 3;
int a[a_size] = {1, 3, 6, 3, 2, 7}; 
int b[b_size];
copy_if (begin(a), end(a), begin(b), every(3));

所有代码需要的是调用一个行为类似于整数的类型every()。

（该代码使用了C++11的static_assert、begin()、end()和copy_if()函数，但如果您回溯到足够的函数，它也可以在C++03中正常工作，就像我所做的那样）

- Luis Machuca

---

我不理解这个（对我来说太复杂了）。copy_if的一元谓词以数组元素作为参数，而不是该元素的位置。是否可能将元素位置传递给谓词？ - cpp

可以这样做，但不是必须的。every()调用创建一个谓词，每次调用它时都会“打勾”。copy_if在每一步中传递一个要测试的元素，但bool operator()(...)将其丢弃，因为元素并不重要，只有步数计数器才是谓词内部跟踪的重点。当every_n“打勾”时，无论其值如何，该元素都被标记为调用算法的正匹配项。 - Luis Machuca

Answer 5

这就是最快的速度：

void copy_n(int & a[], int & b[], int a_sz, int n) {
  int bx = 0;
  for (int i=0; i<a_sz; i+=n) {
    b[bx++]=a[i];
  }
}

- xtrm0

Answer 6

例子：

#include<iostream>
using namespace std;

int main() {
    const int a_size = 6;
    const int b_size = a_size / 2;

    int a[a_size] = {1, 3, 6, 3, 2, 7}; 
    int b[b_size];

    for (int ax = 0, bx = 0; ax < a_size; ax += 2) {
        b[bx++] = a[ax];
    }   
}

- Eldar Agalarov