Подтвердить что ты не робот

Использование итератора для разделения массива на части с неравным размером

У меня есть массив, который мне нужно разделить на 3-элементные подмассивы. Я хотел сделать это с помощью итераторов, но я заканчиваю итерацию мимо конца массива и segfault, даже если я не разыскиваю итератор. данный: 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; });

Но это кажется ненужным, когда я не разыскиваю итератор. Почему я не могу сделать первую версию?

4b9b3361

ОТВЕТЫ

Ответ 1

Причина, по которой это запрещено, хорошо освещена в вашем другом вопросе Являются ли итераторы прошлым "одним прошлым" iterator undefined?, поэтому я просто рассмотрю усовершенствованные решения.

Для итераторов с произвольным доступом (которые вы должны иметь, если используете <), нет никакой необходимости в дорогостоящей операции по модулю.

Основные моменты заключаются в следующем:

  • 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), если модель памяти плоская. Ограничения поведения С++ не применяются к примитивным операциям, которые компилятор переводит С++ в.

Конечно, вы можете использовать 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;
}

Ответ 2

Segfault, который вы видите, исходит от next проверка диапазона для вас - это утверждение в вашей реализации Debug для проверки на undefined. Поведение итераторов и указателей не определяется за пределами их выделенного диапазона, а элемент "один мимо конца": Являются ли итераторы прошлым "одним прошлым" , iterator undefined поведение?

Это означает, что приращение по сравнению с элементом "один конец" означает undefined поведение, не зависящее от последующего использования итератора. Чтобы определить поведение, вы должны использовать такое решение, как ваш алгоритм Integer Modulo или аналогичный, но вам придется изменить auto it = next(bar, 3) на что-то, что обусловлено наличием по крайней мере размера вашего подматрица, поэтому что-то вроде: auto it = size(foo) <= 3 ? finish : next(bar, 3).

Если доступное решение лучше всего подходит для наименее избыточной итерации, это отслеживать оставшийся в контейнере размер как целое число, которое не страдает от поведения undefined, когда оно выходит за пределы диапазона, и "одно прошлое - -конец". Это может быть достигнуто:

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;

EDIT: ранее я предлагал использовать указатели, не зависящие от Debug, это поведение undefined.

Проблема заключается в том, что 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, проверки диапазона должны быть удалены, поэтому вы сможете использовать первую версию своего кода.

Ответ 3

Существует некоторое несогласие о наиболее эффективном способе выполнения этой итерации через массивные разделы.

Сначала однопользовательский метод по модулю, он должен определить auto size в дополнение к изменениям моего ответа, поскольку gcc еще не поддерживает 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 строк сборки, наиболее условно it != finish генерирует следующие инструкции:

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

Во-вторых, повторное вычитание итератора с помощью Ben Voigt try_advance, но только со специализацией случайного доступа, потому что существует конфликт компилятора для итераторов произвольного доступа:

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 строк сборки, наиболее заметно условное значение в try_advance: if (end - it < stride) return false; на каждую итерацию генерирует код:

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

Узнав, что cmpq действительно просто операция вычитания и сравнения, я написал некоторый код для маркировки: http://coliru.stacked-crooked.com/a/ad869f69c8dbd96f Мне нужно было использовать Coliru, чтобы иметь возможность включить оптимизацию, но он продолжает давать мне фиктивные приращения моего количества тестов на время, я не уверен, что происходит там. То, что я могу сказать, локально, повторное вычитание итератора всегда быстрее, иногда значительно. Узнав об этом, я считаю, что ответ Ben Voigt должен быть помечен как правильный.

EDIT:

Я сделал интересное открытие. Это алгоритм, который идет первым, который всегда теряет. Я перезаписал код, чтобы поменять первый алгоритм на каждом проходе. Когда это делается, целочисленный метод по модулю всегда превосходит метод вычитания итератора, как можно было бы подозревать, глядя на сборку, снова что-то подозрительное происходит с Coliru, но вы можете взять этот код и запустить его локально: http://coliru.stacked-crooked.com/a/eb3e0c70cc138ecf

Следующая проблема заключается в том, что оба этих алгоритма ленивы; в случае, если size(foo) является кратным 3, они выделяют пустой vector в конце vector. Это требует значительного разветвления для целочисленного модульного алгоритма для исправления, но только простейших изменений для повторного алгоритма вычитания итератора. Результирующие алгоритмы демонстрируют эффективные равные контрольные числа, но для простоты край идет на повторное вычитание итератора:

Integer модульный алгоритм:

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;

РЕДАКТИРОВАТЬ: Бросить оставшийся алгоритм размера в шляпу

Как алгоритмы Integer Modulo, так и повторные вычитания выше, страдают от повторения по входной последовательности более одного раза, кроме того, что это медленнее, это не так серьезно, потому что в настоящее время мы используем двунаправленный итератор, но если наш итератор ввода не сможет для двунаправленного итератора это будет чрезмерно дорого. Независимо от типа итератора алгоритм остаточного размера каждый раз ударяет всех соперников при итерациях 10 000 000+ testbench:

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