使用迭代器将数组分成大小不等的部分

Question

我有一个数组，我需要将其分成 3 个元素的子数组。我想用迭代器来做到这一点，但我最终迭代了数组的末尾并出现段错误 ，即使我没有取消引用迭代器。给出：auto foo = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 我在做：

auto bar = cbegin(foo);

for (auto it = next(bar, 3); it < foo.end(); bar = it, it = next(bar, 3)) {
    for_each(bar, it, [](const auto& i) { cout << i << endl; });
}

for_each(bar, cend(foo), [](const auto& i) { cout << i << endl; });

现在我可以通过定义一个finish迭代器来解决这个问题：

auto bar = cbegin(foo);
auto finish = next(cend(foo), -(size(foo) % 3));

for (auto it = next(bar, 3); it != finish; bar = it, it = next(bar, 3)) {
    for_each(bar, it, [](const auto& i) { cout << i << endl; });
}

for_each(bar, finish, [](const auto& i) { cout << i << endl; });
for_each(finish, cend(foo), [](const auto& i) { cout << i << endl; });

但是当我不取消引用迭代器时，这似乎是不必要的。为什么我不能做第一个版本？

Answer 1

您看到的段错误来自 next checking the range for you is an assertion in your Debug implementation to check against undefined behavior. The behavior of iterators and pointers is not defined beyond the their allocated range, and the "one past-the-end" element:

这意味着递增超过 "one past-the-end" 元素是未定义的行为独立于迭代器的后续使用。为了定义行为，您必须使用像您的 Integer Modulo 算法或类似的解决方案，但您必须将 auto it = next(bar, 3) 更改为根据 at 的可用性进行条件化的方法至少你的子数组的大小，所以像：auto it = size(foo) <= 3 ? finish : next(bar, 3).

如果可用，这里最好的解决方案将导致最少的冗余迭代是跟踪容器中剩余的大小作为一个整数，当它超出范围时不会出现未定义的行为 "one past-the-end" .这可以通过以下方式完成：

auto bar = cbegin(foo);

for (auto i = size(foo); i > STEP; i -= STEP) {
    for(auto j = 0; j < STEP; ++j, ++bar) cout << *bar << '\t';
    cout << endl;
}

for(auto i = 0; j < STEP; ++j, ++bar) cout << *bar << '\t';
cout << endl;

编辑：我之前建议使用非调试条件的指针，这是未定义的行为。

问题是 next 正在为您检查范围。我们一直在分配的内存之外使用指针，例如 nullptr 和 end，这里就是 it。如果你只是在这里使用 C 风格的指针算法，你会没事的：

auto bar = cbegin(foo); for (auto it = bar + 3; it < cend(foo); bar = it, it = bar + 3) { for_each(bar, it, [](const auto& i) { cout << i << endl; }); } for_each(bar, cend(foo), [](const auto& i) { cout << '\t' << i << endl; });

Live Example

~~或者，如果您运行在 Release 配置中应该删除范围检查，这样您就可以使用代码的第一个版本。~~

Answer 2

您的其他问题很好地说明了禁止这样做的原因，所以我将只讨论改进的解决方案。

对于随机访问迭代器（如果您使用 < 则必须拥有），完全不需要昂贵的模运算。

要点是：

it + stride 在 it 接近尾声时失败
end() - stride 失败
end() - it 总是合法的

从那里开始，将 it + stride < end() 变为合法形式（从两边减去 it）是简单的代数运算。

我用过很多次的最终结果：

for( auto it = c.cbegin(), end = c.cend(); end - it >= stride; it += stride )

如果内存模型是平坦的，编译器可以自由优化返回到与预先计算的 end - stride * sizeof(*it) 的比较——C++ 行为的限制不适用于编译器将 C++ 转换成的原始操作.

如果您更喜欢使用命名函数而不是运算符，您当然可以使用 std::distance(it, end)，但这只对随机访问迭代器有效。

为了与前向迭代器一起使用，您应该使用结合增量和终止条件的东西，例如

struct less_preferred { size_t value; less_preferred(size_t v) : value(v){} };

template<typename Iterator>
bool try_advance( Iterator& it, less_preferred step, Iterator end )
{
     while (step.value--) {
         if (it == end) return false;
         ++it;
     }
     return true;
}

有了这个额外的重载，您将获得随机访问迭代器的高效行为：

template<typename RandomIterator>
auto try_advance( RandomIterator& it, size_t stride, RandomIterator end )
     -> decltype(end - it < stride) // SFINAE
{
     if (end - it < stride) return false;
     it += stride;
     return true;
}

Answer 3

关于通过数组分区完成此迭代的最有效方法。

首先是一次性整数取模方法，除了 because gcc does not yet support size:

的变化外，还必须定义 auto size

auto foo = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };  
auto size = distance(cbegin(foo), cend(foo));
auto bar = cbegin(foo);
auto finish = prev(cend(foo), size % 3);

for(auto it = size <= 3 ? cend(foo) : next(bar, 3); it != finish; bar = it, it = next(bar, 3)) {
    for_each(bar, it, [](const auto& i) { cout << i << '\t'; });
    cout << endl;
}

for_each(bar, finish, [](const auto& i) { cout << i << '\t'; });
cout << endl;
for_each(finish, cend(foo), [](const auto& i) { cout << i << '\t'; });
cout << endl;

这会创建 112 lines of assembly，最值得注意的是条件 it != finish 会生成这些指令：

cmpq    %r12, %r13
je      .L19
movq    %r12, %rbx
jmp     .L10

第二次使用重复迭代器减法，但仅使用随机访问特化，因为随机访问迭代器存在编译器冲突：

auto foo = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };  
auto bar = cbegin(foo);

for (auto it = cbegin(foo), end = cend(foo); try_advance(it, 3, end); bar = it) {
    for_each(bar, it, [](const auto& i) { cout << i << '\t'; });
    cout << endl;
}

for_each(bar, cend(foo), [](const auto& i) { cout << i << '\t'; });
cout << endl;

这会创建 119 lines of assembly，最值得注意的是 try_advance 中的条件：if (end - it < stride) return false; 导致每次迭代生成代码：

movq    %r12, %rax
subq    %rbp, %rax
cmpq    , %rax
ja      .L3

得知 cmpq is really just a subtract and compare operation I have written some bench-marking code: http://coliru.stacked-crooked.com/a/ad869f69c8dbd96f I needed to use Coliru to be able to turn on optimization, but it keeps giving me bogus increments of my test count for times, I'm not sure what's going on there. ~~What I can say is locally, the repeated iterator subtraction is always faster, sometimes significantly so. Upon learning this I believe that 应该被标记为正确的。~~

编辑：

我有一个有趣的发现。总是失败的是先行的算法。我重写了代码以在每次通过时交换第一个算法。完成此操作后，整数模方法总是胜过迭代器减法方法，正如通过查看程序集所怀疑的那样，Coliru 又发生了一些可疑的事情，但是您可以在本地获取此代码并运行：http://coliru.stacked-crooked.com/a/eb3e0c70cc138ecf

下一个问题是这两种算法都是惰性的；如果 size(foo) 是 3 的倍数，他们会在 vector 的末尾分配一个空的 vector。这需要对整数模算法进行大量分支才能补救，但对于重复迭代器减法算法来说，这只是最简单的更改。生成的算法表现出有效相等的基准数，但为简单起见，边缘转到重复的迭代器减法：

整数取模算法：

auto bar = cbegin(foo);
const auto size = distance(bar, cend(foo));

if (size <= 3) {
    for_each(bar, cend(foo), [](const auto& i) { cout << i << '\t'; });
    cout << endl;
}
else {
    auto finish = prev(cend(testValues), (size - 1) % 3 + 1);

    for (auto it = next(bar, 3); it != finish; bar = it, advance(it, 3)) {
        for_each(bar, it, [](const auto& i) { cout << i << '\t'; });
        cout << endl;
    }

    for_each(bar, finish, [](const auto& i) { cout << i << '\t'; });
    cout << endl;
    for_each(finish, cend(foo), [](const auto& i) { cout << i << '\t'; });
    cout << endl;
}

重复迭代器减法算法：

auto bar = cbegin(foo);

for (auto it = cbegin(foo); distance(it, cend(foo)) > 3; bar = it) {
    advance(it, 3);
    for_each(bar, it, [](const auto& i) { cout << i << '\t'; });
    cout << endl;
}

for_each(bar, cend(foo), [](const auto& i) { cout << i << '\t'; });
cout << endl;

编辑：将剩余大小算法扔进帽子

上面的整数模和重复减法算法都在输入序列上迭代不止一次，除了速度较慢之外，这并没有那么严重，因为目前我们使用的是双向迭代器，但我们的输入迭代器应该无法获得双向迭代器的资格，这将非常昂贵。独立于迭代器类型，剩余大小算法每次在 10,000,000+ 测试台迭代时击败所有挑战者：

auto bar = cbegin(foo);

for (auto i = size(foo); i > STEP; i -= STEP) {
    for(auto j = 0; j < STEP; ++j, ++bar) cout << *bar << '\t';
    cout << endl;
}

for(auto i = 0; j < STEP; ++j, ++bar) cout << *bar << '\t';
cout << endl;

我再次将本地测试复制到 Coliru，结果很奇怪，但您可以在本地验证：http://coliru.stacked-crooked.com/a/361f238216cdbace

使用迭代器将数组分成大小不等的部分

Using an iterator to Divide an Array into Parts with Unequal Size

c++

iterator

termination

modulo

data-partitioning