Невалиден. Как минимум потому что нет специализации iterator_traits. find_if может иметь разные реализации для разных категорий iterator_traits<I>::iterator_category
Здравствуйте, B0FEE664, Вы писали:
BFE>Является ли следующий код валидным? И если нет, то почему?
Мне кажется, что такой код — прямой прыжок в область implementation-defined или undefined behavior.
Тут даже не понятно, что вы имеете ввиду под "валидный": что он соберется? что значение it будет изменено в коде find_if? что значение it не будет изменено в коде find_if?
Говорить дальше не было нужды. Как и все космонавты, капитан Нортон не испытывал особого доверия к явлениям, внешне слишком заманчивым.
Здравствуйте, B0FEE664, Вы писали:
BFE>Является ли следующий код валидным?
Не является, если под валидностью подразумевается, что код скомпилируется и что после вызова find_if возвращённое значение совпадёт со значением it.
Здравствуйте, VTT, Вы писали:
BFE>>Является ли следующий код валидным? И если нет, то почему? VTT>Мне кажется, что такой код — прямой прыжок в область implementation-defined или undefined behavior.
Почему?
VTT>Тут даже не понятно, что вы имеете ввиду под "валидный": что он соберется? что значение it будет изменено в коде find_if? что значение it не будет изменено в коде find_if?
Меня интересует результат и соответствие стандарту. Вот по стандарту он должен работать или нет?
Здравствуйте, watchmaker, Вы писали:
BFE>>Является ли следующий код валидным? W>Не является, если под валидностью подразумевается, что код скомпилируется и что после вызова find_if возвращённое значение совпадёт со значением it.
Код не должен компилироваться? Почему? И почему значение может не совпадать?
Здравствуйте, B0FEE664, Вы писали:
BFE>Здравствуйте, watchmaker, Вы писали:
BFE>>>Является ли следующий код валидным? W>>Не является, если под валидностью подразумевается, что код скомпилируется и что после вызова find_if возвращённое значение совпадёт со значением it.
BFE>И почему значение может не совпадать?
Нет, давай лучше ты сначала расскажешь, почему считаешь, что оно должно совпадать :)
Я вот не вижу в стандарте ни единого основания для такой уверенности. Это, разумеется, если смотреть как описан алгоритм find_if в стандарте, а не в художественном изложении на всяких сайтах в интернете вроде cplusplus.com. На последнем, например, написано, что поведение функции эквивалентно некой представленной реализации, хотя на самом деле такого требования нет и на практике реализация как раз отличается. Причём часть отличий как раз затрагивает процесс копирования итераторов. Хотя для равенства it и возвращаемого занчения важна детерминистичность этого процесса.
Чего-то я не понимаю. Т.е. сначала Вы ищете итератор, указывающий на "элемент больше либо равный двух", затем, если нашлось, забываете про этот итератор и модифицируете первый элемент массива? Или Вы хотите модифицировать найденный элемент?
Стандарт вроде бы говорит что
25.2.5.1
Returns: The first iterator i in the range [first,last) for which the following corresponding conditions hold: *i == value, pred(*i) != false, pred(*i) == false. Returns last if no such iterator is found.
Так что код на первый взгляд выглядит нормальным. Странным, но нормальным.
Здравствуйте, watchmaker, Вы писали:
W>>>Не является, если под валидностью подразумевается, что код скомпилируется и что после вызова find_if возвращённое значение совпадёт со значением it. BFE>>И почему значение может не совпадать? W>Нет, давай лучше ты сначала расскажешь, почему считаешь, что оно должно совпадать
find_if в качестве возвращаемого значения имеет то же тип, что и итератор, поэтому, если передаётся ссылка, то должна быть возвращена легальная ссылка на найденный объект. Насколько я понимаю, не существует способа вернуть валидную ссылку на локальный объект. Значит ссылка на найденный аргумент и на первый параметер должны совпадать. .
MD>Чего-то я не понимаю. Т.е. сначала Вы ищете итератор, указывающий на "элемент больше либо равный двух", затем, если нашлось, забываете про этот итератор и модифицируете первый элемент массива?
Почему первый? Я же ссылку передал. Её же ожидаю в качестве результата. А какую ещё валидную ссылку может вернуть find_if?
Я ожидаю, что it будет указывать на найденный элемент.
Здравствуйте, B0FEE664, Вы писали:
VTT>>Мне кажется, что такой код — прямой прыжок в область implementation-defined или undefined behavior. BFE>Почему?
BFE>Меня интересует результат и соответствие стандарту. Вот по стандарту он должен работать или нет?
В стандарте определяется только значение итератора, возвращаемого из функции, что именно делается с аргументами там не описывается.
В стандарте говорится, что первые два аргумента должны соответствовать требованиям для InputIterator, т.е. среди прочего быть CopyConstructible, CopyAssignable, и Destructible. Вообще говоря, я не уверен что InputIterator & соответствует этим требованиям.
Так или иначе, функция принимающая эти итераторы, может их копировать и присваивать (и предикат тоже!), как хочет (разрешение на копирование предиката там даже специально отмечено). Так что соответствующая стандарту реализация вполне может делать так:
...
find_if(InputIterator first, InputIterator last, Predicate pred)
{
auto iter = first;
while(iter != last)
{
if(pred(*iter))
{
break;
}
++iter;
}
return(iter);
}
или даже так:
...
find_if(InputIterator first, InputIterator last, Predicate pred)
{
auto iter = first;
while(iter != last)
{
if(pred(*iter))
{
break;
}
++iter;
}
first = last;
return(iter);
}
Говорить дальше не было нужды. Как и все космонавты, капитан Нортон не испытывал особого доверия к явлениям, внешне слишком заманчивым.
Здравствуйте, B0FEE664, Вы писали:
BFE>Значит ссылка на найденный аргумент и на первый параметер должны совпадать. .
А, например, со вторым аргументом ей что мешает совпадать?
Рассмотри все варианты. А то почему-то делаешь выбор в пользу какого-то одного, игнорируя остальные.
BFE>Насколько я понимаю, не существует способа вернуть валидную ссылку на локальный объект.
Тут скорее другой принцип: Garbage in, garbage out.
Здравствуйте, VTT, Вы писали:
VTT>В стандарте определяется только значение итератора, возвращаемого из функции, что именно делается с аргументами там не описывается.
Ну, тип то его явно указан.
VTT>В стандарте говорится, что первые два аргумента должны соответствовать требованиям для InputIterator, т.е. среди прочего быть CopyConstructible, CopyAssignable, и Destructible. Вообще говоря, я не уверен что InputIterator & соответствует этим требованиям.
VTT>Так или иначе, функция принимающая эти итераторы, может их копировать и присваивать (и предикат тоже!), как хочет (разрешение на копирование предиката там даже специально отмечено). Так что соответствующая стандарту реализация вполне может делать так: VTT>
VTT>...
VTT>find_if(InputIterator first, InputIterator last, Predicate pred)
VTT>{
VTT> auto iter = first;
VTT>...
VTT> return(iter);
VTT>}
VTT>
VTT>или даже так: VTT>
VTT>...
VTT>find_if(InputIterator first, InputIterator last, Predicate pred)
VTT>{
VTT> auto iter = first;
VTT>...
VTT> return(iter);
VTT>}
VTT>
Я бы сказал, что это ошибка — возвращение висячей ссылки.
Здравствуйте, watchmaker, Вы писали:
BFE>>Значит ссылка на найденный аргумент и на первый параметер должны совпадать. . W>А, например, со вторым аргументом ей что мешает совпадать? W>Рассмотри все варианты. А то почему-то делаешь выбор в пользу какого-то одного, игнорируя остальные.
Чтож. Это аргумент.
BFE>>Насколько я понимаю, не существует способа вернуть валидную ссылку на локальный объект. W>Тут скорее другой принцип: Garbage in, garbage out.
Ну нет. Данные валидные. Более того, заставляют платить за то, что не используется: за копирование итераторов.
Может не скомпилироваться, если find_if внутри использует указатель на итератор. Или ссылку на итератор, если используешь старый С++, где reference collapsing не работает.
Здравствуйте, B0FEE664, Вы писали:
BFE>Почему первый? Я же ссылку передал. Её же ожидаю в качестве результата. А какую ещё валидную ссылку может вернуть find_if? BFE>Я ожидаю, что it будет указывать на найденный элемент.
Хорошо, давайте снова процитирую Стандарт, но более полно (если быт точным, то это draft n3290, но тут давно ничего не меняется):
25.2.5 Find [alg.find]
template<class InputIterator, class T> InputIterator find(InputIterator first, InputIterator last, const T& value);
template<class InputIterator, class Predicate> InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);
template<class InputIterator, class Predicate> InputIterator find_if_not(InputIterator first, InputIterator last, Predicate pred);
1 Returns: The first iterator i in the range [first,last) for which the following corresponding conditions hold: *i == value, pred(*i) != false, pred(*i) == false. Returns last if no such iterator is found.
2 Complexity: At most last — first applications of the corresponding predicate.
Здесь ничего не говорится про взаимосвязь входных параметров и внутреннего tmp, бегущего по диапазону [first, last). Итого, Вы можете предполагать иммутабельность входных параметров, но никак не можете ожидать мутабельность — это ни из чего не следует. И даже если какая-то реализация даёт такой эффект, он именно side effect, implementation-defined.
Что касается ссылки, то у меня ощущение, что она сыграет лишь как "передача it по ссылке, а не copy construction". Ведь Вы сравниваете результат find_if() с итератором itEnd, а не указателем на него — и всё компилируется? Ну и опять же, что ссылка, что не ссылка — это будет соптимизировано любым уважающим себя компилятором, так что не ожидаю разницы в итоговом коде, если честно.
На толкователя стандарта не претендую, но reference to object-это non-type template-parameter, а прототип find_if определён
с type template-parameter, поэтому строка std::find_if<std::vector<int>::iterator&, decltype(oFn)>(it, itEnd, oFn) есть
нарушение, так как содержит type-referеnce в параметрах шаблона. И вообще не понятно зачем такие качели, если копирование
итераторов по ссылке не есть дорогостоящая операция, можно смело делать it=std::find_if(itBeg, itEnd, oFn)
MD>template<class InputIterator, class Predicate> InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);
MD>Здесь ничего не говорится про взаимосвязь входных параметров и внутреннего tmp, бегущего по диапазону [first, last). Итого, Вы можете предполагать иммутабельность входных параметров, но никак не можете ожидать мутабельность — это ни из чего не следует. И даже если какая-то реализация даёт такой эффект, он именно side effect, implementation-defined.
то я считаю, что вправе рассчитывать на корректную работу этой функции с ссылками если обратное не оговорено в документации.
Т.е. вызов:
int n = 32;
ink k = fun<int&>(n);
должен отработать корректно. Корректно — это значит не иметь Undefined Behavior.
Согласны?
MD>Что касается ссылки, то у меня ощущение, что она сыграет лишь как "передача it по ссылке, а не copy construction". Ведь Вы сравниваете результат find_if() с итератором itEnd, а не указателем на него — и всё компилируется?
Компилируется или нет — зависит от реализации std::find_if
MD>Ну и опять же, что ссылка, что не ссылка — это будет соптимизировано любым уважающим себя компилятором, так что не ожидаю разницы в итоговом коде, если честно.
Разница в том, куда будет указывать переданный аргумент.
, но могу дополнить. Если я вижу функцию, типа: BFE>
BFE>template<class T> T fun(T t);
BFE>
BFE>то я считаю, что вправе рассчитывать на корректную работу этой функции с ссылками если обратное не оговорено в документации. BFE>Т.е. вызов: BFE>
BFE> int n = 32;
BFE> ink k = fun<int&>(n);
BFE>
BFE>должен отработать корректно. Корректно — это значит не иметь Undefined Behavior. BFE>Согласны?
Согласен, безусловно. Более того, k и n имеют один и тот же тип. Но почему Вы ожидаете, что k и n должны быть взаимосвязаны по своему значению, если в специализации шаблона фигурирует символ ссылки на тип? Вот краеугольный камень, вокруг которого мы бродим уже второй день.
Копировать по ссылке, клонировать, делать swap или ещё что — это внутренняя кухня имплементации. Не закладывайтесь на неё.
Здравствуйте, Mr.Delphist, Вы писали:
MD>Копировать по ссылке, клонировать, делать swap или ещё что — это внутренняя кухня имплементации. Не закладывайтесь на неё.
Что если в реализации:
template<class InputIterator, class Predicate> InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);
Здравствуйте, smeeld, Вы писали:
S>На толкователя стандарта не претендую, но reference to object-это non-type template-parameter,
Вот ещё! Откуда такие странные идеи? Ссылка это вам не какая-нибудь константа!
S>а прототип find_if определён S>с type template-parameter, поэтому строка std::find_if<std::vector<int>::iterator&, decltype(oFn)>(it, itEnd, oFn) есть S>нарушение, так как содержит type-referеnce в параметрах шаблона. И вообще не понятно зачем такие качели, если копирование S>итераторов по ссылке не есть дорогостоящая операция, можно смело делать it=std::find_if(itBeg, itEnd, oFn)
Ага, скажите ещё, что кроме векторов в find_if ничего нельзя подставить:
Здравствуйте, B0FEE664, Вы писали:
BFE>Ага, скажите ещё, что кроме векторов в find_if ничего нельзя подставить:
Ну там выше больше постебался, а вообще с ссылками нужно поосторожней, это не такой
универсальный и безопасный инструмент как указатель. Выше в коментах написал про ненулевую
возможность появления в реализации строчки InputIterator& tmp, тогда что?
MD>Согласен, безусловно. Более того, k и n имеют один и тот же тип. Но почему Вы ожидаете, что k и n должны быть взаимосвязаны по своему значению, если в специализации шаблона фигурирует символ ссылки на тип? Вот краеугольный камень, вокруг которого мы бродим уже второй день.
Потому, что для того, чтобы вернуть ссылку на что-то, это что-то должно существовать вне функции. Отсюда вывод: либо функция T& f<T&>(..) использует глобальную переменную, либо содержит в себе static переменную, либо мы имеем утечку памяти, либо fun<int&>(n) вернёт ссылку на n. (Либо мы имеем чёрное колдунство, которое мистическим способом позволяет продлить жизнь возвращённой ссылки до конца scope)
В любом случае, единственным разумным решением является вернуть переданную ссылку, так как в противном случае мы имеем либо side-effect, либо undefined behavior.
MD>Копировать по ссылке, клонировать, делать swap или ещё что — это внутренняя кухня имплементации. Не закладывайтесь на неё.
Невозможно клонировать ссылку. Можно дать ей другое имя, не более того.
Здравствуйте, smeeld, Вы писали:
BFE>>Ага, скажите ещё, что кроме векторов в find_if ничего нельзя подставить: S>Ну там выше больше постебался,
Не, это я вчера спал всего 2 часа и реально закомитил код с ссылками...
S>а вообще с ссылками нужно поосторожней, это не такой S>универсальный и безопасный инструмент как указатель. Выше в коментах написал про ненулевую S>возможность появления в реализации строчки InputIterator& tmp, тогда что?
template<class InputIterator, class Predicate> InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);
в реализации, для удобства или для других целей, создают ссылку вида InputIterator& tmp=first.
За уши притянуто, но возможность такая есть, а ссылку на ссылку создавать нельзя, поэтому такое
Здравствуйте, smeeld, Вы писали:
S>в реализации, для удобства или для других целей, создают ссылку вида InputIterator& tmp=first.
Мы говорим о текущем стандарте
, но могу дополнить. Если я вижу функцию, типа: BFE>
BFE>template<class T> T fun(T t);
BFE>
BFE>то я считаю, что вправе рассчитывать на корректную работу этой функции с ссылками если обратное не оговорено в документации.
Обратное тоже верно, когда я пишу fun(T t), то подразумеваю что будет передано по значению, если я хочу менять аргумент я напишу fun(T& t)
Здравствуйте, Igore, Вы писали:
I>Обратное тоже верно, когда я пишу fun(T t), то подразумеваю что будет передано по значению, если я хочу менять аргумент я напишу fun(T& t)
А почему так? Ведь T — это любой тип удовлетворяющий условиям написанным в документации для функции. Если вы не хотите менять параметр, то почему не написать fun(const T& t)?
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Невалиден. Как минимум потому что нет специализации iterator_traits.
Разве наличие iterator_traits является обязательным?
EP>find_if может иметь разные реализации для разных категорий iterator_traits<I>::iterator_category
,Здравствуйте, B0FEE664, Вы писали:
BFE>Мы говорим о текущем стандарте или о старом?
Если серьёзно, то тема топика есть проблема на ровном месте. В стандарте есть рекомендации по
менеджменту возвращения объектов из функций-фабрик. Те, что имеют прототипы
template <typename T>
T func(...);
Эти рекомендации реализованиы во всех известных компиляторах. И когда делаете так:
Любой компилятор здесь сначала создаст и проинициализирует itEnd, потом создаст it, проинициализирует его it=arr.begin()
потом вызовется find_if, с передачей объектов it и itEnd по их адресам в стеке той функции, что вызывает find_if,
из find_if возвратится (значение rax на x86_64) тот же адрес объекта it, состояние которого в функции find_if
было изменено с arr.begin() на соответствующее результатам поиска.
Что до поиска истин в стандарте, то это занятия не благородное.
Здравствуйте, B0FEE664, Вы писали:
I>>Обратное тоже верно, когда я пишу fun(T t), то подразумеваю что будет передано по значению, если я хочу менять аргумент я напишу fun(T& t) BFE>А почему так? Ведь T — это любой тип удовлетворяющий условиям написанным в документации для функции. Если вы не хотите менять параметр, то почему не написать fun(const T& t)?
Согласен, для параметров в основном это (const T&, T*), просто T обычно для результата или объявления, и в этих случаях я ссылку не ожидаю.
Что то вроде такого.
template< class T >
class Test
{
public:
Test( const T& t ) : t_(t){}
T getT() const {
return t_;
}
private:
T t_;
};
Здравствуйте, smeeld, Вы писали: S>Если серьёзно, то тема топика есть проблема на ровном месте. S>В стандарте есть рекомендации по S>менеджменту возвращения объектов из функций-фабрик. Те, что имеют прототипы S>
S>template <typename T>
S>T func(...);
Это в каком пункте? Или по каким ключевым словам искать? S>Эти рекомендации реализованиы во всех известных компиляторах. И когда делаете так:
В том-то и дело, что, например, для gcc 4.7.3 тут нет эквивалентности. S>Любой компилятор здесь сначала создаст и проинициализирует itEnd, потом создаст it, проинициализирует его it=arr.begin() S>потом вызовется find_if, с передачей объектов it и itEnd по их адресам в стеке той функции, что вызывает find_if, S>из find_if возвратится (значение rax на x86_64) тот же адрес объекта it, состояние которого в функции find_if S>было изменено с arr.begin() на соответствующее результатам поиска. S>Что до поиска истин в стандарте, то это занятия не благородное.
Ну, если посмотреть на реализацию, то всё совсем не так:
/**
* @brief Find the first element in a sequence for which a
* predicate is true.
* @ingroup non_mutating_algorithms
* @param __first An input iterator.
* @param __last An input iterator.
* @param __pred A predicate.
* @return The first iterator @c i in the range @p [__first,__last)
* such that @p __pred(*i) is true, or @p __last if no such iterator exists.
*/template<typename _InputIterator, typename _Predicate>
inline _InputIterator
find_if(_InputIterator __first, _InputIterator __last,
_Predicate __pred)
{
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
typename iterator_traits<_InputIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
return std::__find_if(__first, __last, __pred,
std::__iterator_category(__first));
}
И если задать ссылку, то будет ошибка:
stl_algo.h:4490:41: error: invalid initialization of non-const reference of type ‘__gnu_cxx::__normal_iterator<...>&’ from an rvalue of type ‘__gnu_cxx::__normal_iterator<...>’
в последней строке функции.
Но дело даже не в этом, а в том, что __first будет передан в __find_if по значению...
Здравствуйте, B0FEE664, Вы писали:
BFE>Это в каком пункте? Или по каким ключевым словам искать?
[class.temporary]
[ Example: Consider the following code:
class X {
public:
X(int);
X(const X&);
X& operator=(const X&);
~X();
};
class Y {
public:
Y(int);
Y(Y&&);
~Y();
};
X f(X);
Y g(Y);
void h() {
X a(1);
X b = f(X(2));
Y c = g(Y(3));
a = f(a);
};
An implementation might use a temporary in which to construct X(2) before passing it to f() using X’s
copy constructor; alternatively, X(2) might be constructed in the space used to hold the argument. Likewise,
an implementation might use a temporary in which to construct Y(3) before passing it to g() using Y’s
move constructor; alternatively, Y(3) might be constructed in the space used to hold the argument. Also,
a temporary might be used to hold the result of f(X(2)) before copying it to b using X’s copy constructor;
alternatively, f()’s result might be constructed in b. Likewise, a temporary might be used to hold the result
of g(Y(3)) before moving it to c using Y’s move constructor; alternatively, g()’s result might be constructed
in c. On the other hand, the expression a=f(a) requires a temporary for the result of f(a), which is then
assigned to a. — end example ]
BFE>В том-то и дело, что, например, для gcc 4.7.3 тут нет эквивалентности.
BFE>Ну, если посмотреть на реализацию, то всё совсем не так:
Загляните в ассемблерный листинг, проследите передаваемые в функцию find_if объекты, и где они
находятся (находятся в стеке вызывающей функции ) компилятор максимально ориентирован на сохранение
объектов в пределах одной области памяти, передавая их в функции по указателям. Ваши попытки передать
ссылку полностью повторят то, что компилятор делает автоматически. Только с ссылками можно нарваться на
различные ошибки компиляции.
Валидный он или нет, но, определённо, это хак.
Можно заметить, что все алгоритмы, принимающие input iterator (а не только forward iterator и далее), должны работать нормально.
Потому что в каждый момент времени существует единственный рабочий экземпляр input iterator'а на данном диапазоне, а нерабочие копии игнорируются.
Таким образом, инициализация и присваивание (то, на чём ссылки отличаются от значений) здесь суть одно.
template<class It>
It foo(It i)
{
++i; // с этого момента экземпляр It, остававшийся в вызывающей стороне, условно-невалиден
It j = i;
++j; // с этого момента i условно-невалиденreturn j;
}
foo(istream_iterator<int>(cin));
vector<int> arr(100);
vector<int>::iterator i = arr.begin();
i = foo(i);
foo<vector<int>::iterator&>(i);
Для forward iterator это уже не так
template<class It>
It foo(It i, It end)
{
It j = i;
if(j != end)
{
++j;
assert(i != j); // если It чистый input iterator, то сравнивать i больше нельзяif(j != end) // а вот end - сколько угодно
{
++j;
assert( distance(i,j)==2 ); // если It чистый input, то использовать его в distance бессмысленно и вредно
}
}
return j;
}
template<class It>
It middle(It i, It end)
{
advance(i,
distance(i,end)/2 // внутри distance мы изменили локальную копию i
); // поэтому передаваемая в advance ссылка должна быть на валидный итераторreturn i;
}
Ну а в твоём случае — вместо хака есть более чистое решение
if( (it = find_if(it,itEnd,oFn)) != itEnd )
.....
Оно делает РОВНО то же самое, но избавлено от заморочек.
Если такая идиома встречается регулярно, ну запиши её
template<class It, class V>
bool skip_unequal(It& it, It end, V const& v) { it = find(it,end,v); return it != end; }
template<class It, class Pred>
bool skip_unless(It& it, It end, Pred pred) { it = find_if(it,end,pred); return it != end; }