Использование итератора для разделения массива на части с неравным размером
У меня есть массив, который мне нужно разделить на 3-элементные подмассивы. Я хотел сделать это с помощью итераторов, но в итоге я перебрал конец массива и segfaulting хотя я не разыменовываю итератор. дано: 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; });
Но это кажется ненужным, когда Я не разыскиваю итератор. Почему я не могу сделать первую версию?
Решение
Причина, по которой это запрещено, хорошо освещена на вашем другом вопросе. Проходят ли итераторы мимо "один конец" итератор неопределенного поведения? поэтому я просто расскажу об улучшенных решениях.
Для итераторов с произвольным доступом (которые вы должны иметь, если используете <), нет необходимости в дорогостоящей операции по модулю.
Существенными моментами являются:
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;
}
Другие решения
Segfault, который вы видите, исходит от next проверка диапазона для вас — это утверждение в вашей реализации отладки для проверки неопределенного поведения. Поведение итераторов и указателей определяется не за пределами выделенного им диапазона и элемента «один за другим»: Проходят ли итераторы мимо "один конец" итератор неопределенного поведения?
Это означает, что увеличение значения после элемента «один конец» является неопределенным поведением. независимо от последующего использования итератора. Для того, чтобы определить поведение, которое вы должен используйте решение, подобное вашему алгоритму Integer Modulo или аналогичному, но вам придется изменить auto it = next(bar, 3) к чему-то, что обусловливает на основе доступности по крайней мере размера вашего подмассива, так что-то вроде: auto it = size(foo) <= 3 ? finish : next(bar, 3),
Там, где это возможно, лучшим решением здесь будет вызывать наименьшую избыточность итерации, которая состоит в том, чтобы отслеживать размер, оставшийся в контейнере, как целое число, которое не страдает от неопределенного поведения, когда оно выходит за пределы диапазона и «один за другим». Это может быть достигнуто путем:
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; });
В качестве альтернативы, если вы запускаете конфигурацию выпуска, проверки диапазона должны быть удалены, чтобы вы могли использовать первую версию своего кода.
Есть некоторые разногласия о наиболее эффективном способе выполнения этой итерации через разделы массива.
Сначала метод одноразового целочисленного модуля, это должно определить 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
Второе повторное вычитание итератора с использованием Бен Фойгта 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, чтобы иметь возможность включить оптимизацию, но она постоянно дает мне ложные приращения количества тестов, я не уверен, что там происходит. Что я могу сказать, это локально, повторное вычитание итератора всегда быстрее, иногда значительно. Узнав об этом, я верю, что Ответ бен фойгта должен быть помечен как правильный.
РЕДАКТИРОВАТЬ:
Я сделал интересное открытие. Это алгоритм, который идет первым, который всегда проигрывает. Я переписал код, чтобы поменять местами первый алгоритм на каждом проходе. Когда это сделано, метод целочисленного модуля по модулю всегда превосходит метод вычитания итератора, как можно было бы предположить, глядя на сборку, опять же что-то подозрительное происходит с 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;
РЕДАКТИРОВАТЬ: бросить алгоритм остаточного размера в шапку
Оба алгоритма Integer Modulo и Repeated Subtraction, описанные выше, страдают от итерации входной последовательности более одного раза, кроме того, что это медленнее, это не так уж и серьезно, потому что в настоящее время мы используем двунаправленный итератор, но если наш входной итератор не подходит для двунаправленного Итератор это будет чрезмерно дорогим. Независимо от типа итератора алгоритм оставшегося размера побеждает всех претендентов каждый раз при 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