Поведение std :: partition при вызове в пустом контейнере?

Question

Я столкнулся с проблемой при вызове std :: partition в пустом контейнере (std :: list).

std::list<int>::iterator end_it = std::partition(l.begin(), l.end(), SomeFunctor(42));
std::list<int>::iterator it = l.begin();

while (it != end_it)
{
  // do stuff
}

Если список пуст, std :: partition возвращает итератор, который не равен давать взаймы(). Это поведение по умолчанию?

Answer 1

Я что-то упустил или не должен:

std::list<int>::iterator end_it = l.begin();

быть:

std::list<int>::iterator end_it = l.end();

Но на самом деле я думаю, что возвращаемое значение partition () не определено для пустого набора значений. Возвращаемое значение определено как:

Итератор я такой, что для любого итератор j в диапазоне [first, i), pred (* j)! = false и для любого итератор k в диапазоне [i, last), пред (* j) == ложь.

ИМХО, предикат нельзя применить к конечному итератору, поскольку он не может быть разыменован.

Answer 2

Сейчас действительно нет хорошего ответа. Библиотечная рабочая группа комитета по С ++ номер выпуска 1205 охватывает именно этот вопрос. Эта проблема включает в себя как первичное, так и альтернативное предлагаемое решение, но ни одно еще не было принято или отклонено (и мне не нравится ни одно).

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

Редактировать, в основном в ответ на комментарий Мартина Б.: проблема указана для [alg.partitions], которая включает в себя std::partition и std::stable_partition. К сожалению, предлагаемая формулировка не , кажется, имеет прямое отношение к любой из них. Цитируемый абзац (по крайней мере, в N2960) описан в std::is_paritioned, что в значительной степени соответствует описанию Мартина Б., хотя он использовал для него неправильное название. Хуже того, основная предлагаемая резолюция представлена ​​в виде ненормативных примечаний.

Как я уже сказал, мне не очень нравится ни одно из предложенных решений. Основной пытается разместить требования в ненормативных примечаниях. Такие примечания хороши, если они разъясняют требования, которые действительно уже существуют в других местах, но их может быть трудно найти. В этом случае я почти уверен, что требования действительно отсутствуют. Альтернативное разрешение лучше, но не решает основной вопрос, является ли пустой диапазон допустимым диапазоном.

ИМО, лучшее разрешение началось бы с § 24.1 / 7. Это уже говорит нам о том, что: «Диапазон [i, i) является пустым диапазоном; ...» Я думаю, что он должен добавить нормативный язык, чтобы явно указать, что пустой диапазон либо является, либо не является допустимым диапазоном. Если это недопустимый диапазон, больше ничего не нужно добавлять - уже очевидно, что применение алгоритма к недопустимому диапазону дает неопределенное поведение.

Если пустой диапазон действителен, то необходимо добавить нормативную формулировку, чтобы определить результаты применения каждого алгоритма к пустому диапазону. Это ответит на основной вопрос, а затем укажет, что этот ответ подразумевает для каждого конкретного алгоритма.

Answer 3

Указывая предварительное условие partition, что диапазон [first, last) должен быть действительным, SGI говорит :

Диапазон [i, j) является допустимым диапазоном, если и i, и j являются действительными итераторами, а j достижим из i [2].

Что позволяет использовать partition в пустом диапазоне.

Конечно, sgi не является стандартом. Но это довольно близко:)

Answer 4

Нет, std::partition должен возвращать конечный итератор, а для меня (gcc-4.4.2) он возвращает.

Я думаю, у вас есть ошибка где-то. Либо в вашем коде, либо в компиляторе.

Answer 5

Эта страница показывает код, который std::partition ведет себя как.