When using std::search with binary comparison predicate, reference obtained from iterator outlives iterator itself which violates part 24.2.1 [iterator.requirements.general] of C++ standard: 10. Destruction of an iterator may invalidate pointers and references previously obtained from that iterator. The iterator is being dereferenced when converting binary predicate to unary for later use in std::find_if: template<typename _ForwardIterator1, typename _ForwardIterator2, typename _BinaryPredicate> _ForwardIterator1 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __predicate) { ... __first1 = std::__find_if(__first1, __last1, __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2)); In this expression __first2 is passed to a _Iter_equals_iter wrapper (from bits/predefined_ops.h): template<typename _Iterator1> struct _Iter_equals_iter { typename std::iterator_traits<_Iterator1>::reference _M_ref; <-- reference obtained from iterator _Iter_equals_iter(_Iterator1 __it1) : _M_ref(*__it1) { } template<typename _Iterator2> bool operator()(_Iterator2 __it2) { return *__it2 == _M_ref; } }; Since _Iterator1 __it1 is passed to constructor by value, _M_ref can become invalid after iterator leaves the scope; This behavior can be observed when using std::search with boost::filesystem::path, since boost::filesystem::path::iterator::dereference returns reference to a local member: http://melpon.org/wandbox/permlink/58aIbfJWeGgMKMdF As a proposed solution, _Iter_equals_iter might store copy of iterator rather than dereferenced value.
(In reply to reagentoo from comment #0) > boost::filesystem::path::iterator::dereference returns reference to a local > member: This means boost::filesystem::path::iterator fails to meet the ForwardIterator requirements, see 24.2.5 [forward.iterators] paragraph 6 in the C++14 standard. > http://melpon.org/wandbox/permlink/58aIbfJWeGgMKMdF > > As a proposed solution, _Iter_equals_iter might store copy of iterator > rather than dereferenced > value. That is not necessary for a type that meets the ForwardIterator requirements.
There is a related bug though, because we make use of that __iter_comp_iter helper function in the implementation if std::includes() which is required to work with InputIterator arguments, so the ForwardIterator requirements don't need to be met. I have a fix ...
Actually, std::includes() doesn't use the problematic function objects that store a reference, so there's no bug. We do have a regression for this standalone testcase, which violates the ForwardIterator requirements, but worked previously: #include <algorithm> struct bad_iterator { typedef std::forward_iterator_tag iterator_category; typedef int value_type; typedef value_type const* pointer; typedef value_type const& reference; typedef std::ptrdiff_t difference_type; bad_iterator() : ptr(), stash() { } bad_iterator(pointer p) : ptr(p), stash() { update(); } bad_iterator(const bad_iterator& i) : ptr(i.ptr), stash() { update(); } ~bad_iterator() { ptr = 0; update(); } bad_iterator& operator=(const bad_iterator& i) { ptr = i.ptr; update(); return *this; } bad_iterator& operator++() { ++ptr; update(); return *this; } bad_iterator operator++(int) { bad_iterator i = *this; ++*this; return i; } reference operator*() const { return *stash; } pointer operator->() const { return stash; } bool operator==(const bad_iterator& i) const { return ptr == i.ptr; } bool operator!=(const bad_iterator& i) const { return !(*this == i); } private: void update() { #ifdef VALID_FWD_ITER stash = ptr; #else pointer p = 0; if (ptr) p = new value_type(*ptr); delete stash; stash = p; #endif } pointer ptr; pointer stash; }; int main() { int s[] = { 0, 1, 2, 3, 4, 5 }; std::search(s, s+3, bad_iterator(s), bad_iterator(s+4)); } This stopped working with GCC 4.9.0 when we added the __iter_comp_iter stuff that stores the reference. Technically this is invalid, but I think we can support it without too much difficulty. That's reasonable given that std::filesystem::path::iterator also violates the ForwardIterator requirements, and the Ranges TS removes the reference-quality requirement anyway.
Author: redi Date: Wed Feb 1 12:57:35 2017 New Revision: 245090 URL: https://gcc.gnu.org/viewcvs?rev=245090&root=gcc&view=rev Log: PR78346 make <bits/predefined_ops.h> handle stashing iterators PR libstdc++/78346 * include/bits/predefined_ops.h (_Iter_equals_iter): Store iterator not its referent. (_Iter_comp_to_iter): Likewise. * testsuite/25_algorithms/search/78346.cc: New test. Added: trunk/libstdc++-v3/testsuite/25_algorithms/search/78346.cc Modified: trunk/libstdc++-v3/ChangeLog trunk/libstdc++-v3/include/bits/predefined_ops.h
Author: redi Date: Wed Feb 1 12:57:46 2017 New Revision: 245091 URL: https://gcc.gnu.org/viewcvs?rev=245091&root=gcc&view=rev Log: PR78346 make <bits/predefined_ops.h> handle stashing iterators PR libstdc++/78346 * include/bits/predefined_ops.h (_Iter_equals_iter): Store iterator not its referent. (_Iter_comp_to_iter): Likewise. * testsuite/25_algorithms/search/78346.cc: New test. Added: branches/gcc-6-branch/libstdc++-v3/testsuite/25_algorithms/search/78346.cc Modified: branches/gcc-6-branch/libstdc++-v3/ChangeLog branches/gcc-6-branch/libstdc++-v3/include/bits/predefined_ops.h
Author: redi Date: Wed Feb 1 12:57:58 2017 New Revision: 245092 URL: https://gcc.gnu.org/viewcvs?rev=245092&root=gcc&view=rev Log: PR78346 make <bits/predefined_ops.h> handle stashing iterators PR libstdc++/78346 * include/bits/predefined_ops.h (_Iter_equals_iter): Store iterator not its referent. (_Iter_comp_to_iter): Likewise. * testsuite/25_algorithms/search/78346.cc: New test. Added: branches/gcc-5-branch/libstdc++-v3/testsuite/25_algorithms/search/78346.cc Modified: branches/gcc-5-branch/libstdc++-v3/ChangeLog branches/gcc-5-branch/libstdc++-v3/include/bits/predefined_ops.h
Fixed for 5.5, 6.4 and 7.1
Thank you very much! Good work!