std::sort(zip_iterator...) does not compile
Hello, I tried to use boost::zip_iterator to sort 2 parallel arrays. Unfortunatly gcc does not compile the appended example because it can not convert boost::detail::iterator_category_with_traversal<std::input_iterator_tag, boost::random_access_traversal_tag> to either std::bidirectional_iterator_tag or std::random_access_iterator_tag. Thus it cannot dispatch the correct stl::__copy_backward() procedure. Is sort() not yet supported? mfg Gunter PS: please CC your replies to my eMail. 8<-----------part of error log--------------- /usr/include/c++/3.3/bits/stl_algobase.h: In static member function `static _BidirectionalIter2 std::__copy_backward_dispatch<_BidirectionalIter1, _BidirectionalIter2, _BoolType>::copy(_BidirectionalIter1, _BidirectionalIter1, _BidirectionalIter2) [with _BidirectionalIter1 = boost::zip_iterator<boost::tuples::tuple<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type> >, _BidirectionalIter2 = boost::zip_iterator<boost::tuples::tuple<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type> >, _BoolType = __false_type]': [...] /usr/include/c++/3.3/bits/stl_algobase.h:392: error: no matching function for call to `__copy_backward( boost::zip_iterator<...>&, boost::zip_iterator<...>&, boost::detail::iterator_category_with_traversal<std::input_iterator_tag, boost::random_access_traversal_tag>)' /usr/include/c++/3.3/bits/stl_algobase.h:360: error: candidates are: _BidirectionalIter2 std::__copy_backward(_BidirectionalIter1, _BidirectionalIter1, _BidirectionalIter2, std::bidirectional_iterator_tag) /usr/include/c++/3.3/bits/stl_algobase.h:371: error: _BidirectionalIter std::__copy_backward(_RandomAccessIter, _RandomAccessIter, _BidirectionalIter, std::random_access_iterator_tag) 8<-----------zip_iter.cpp------------ // sort 2 parallel arrays #include <boost/iterator.hpp> #include <boost/iterator/zip_iterator.hpp> #include <boost/tuple/tuple.hpp> #include <boost/tuple/tuple_comparison.hpp> #include <vector> #include <iostream> int main(int argc, char *argv[]) { typedef std::vector<int> VEC; typedef boost::zip_iterator< boost::tuple<VEC::iterator, VEC::iterator> > zip_iter; VEC v1(10); VEC v2(10); zip_iter iter( boost::make_tuple(v1.begin(), v2.begin()) ); zip_iter iter_end( boost::make_tuple(v1.end(), v2.end()) ); std::sort(iter, iter_end); return EXIT_SUCCESS; }
Gunter Winkler <guwi17@gmx.de> writes:
Hello,
I tried to use boost::zip_iterator to sort 2 parallel arrays. Unfortunatly gcc does not compile the appended example because it can not convert
boost::detail::iterator_category_with_traversal<std::input_iterator_tag, boost::random_access_traversal_tag>
to either std::bidirectional_iterator_tag or std::random_access_iterator_tag. Thus it cannot dispatch the correct stl::__copy_backward() procedure.
Is sort() not yet supported?
Here's the thing: std::bidirectional_iterator_tag and std::random_access_iterator_tag both would imply that the iterator statisfied the Forward Iterator Requirements. Forward Iterator Requirements say that *a must be T&. zip_iterator returns a tuple of references, not a reference itself, from its operator*. Therefore, you can't legally call it a Forward Iterator, and using either std::bidirectional_iterator_tag or std::random_access_iterator_tag would be lying. Now, _does_ sort actually need a Forward Iterator in order to do its work? It's not clear that it does, but the original iterator requirements didn't account for beasts like zip_iterator. It's a bad situation, and it's made worse because I don't know how to write a specification for sort() that would allow a zip_iterator to work. How would you describe the result? -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
Gunter Winkler <guwi17@gmx.de> writes:
I tried to use boost::zip_iterator to sort 2 parallel arrays. Unfortunatly gcc does not compile the appended example because it can not convert
boost::detail::iterator_category_with_traversal<std::input_iterator_tag, boost::random_access_traversal_tag>
to either std::bidirectional_iterator_tag or std::random_access_iterator_tag. Thus it cannot dispatch the correct stl::__copy_backward() procedure.
Is sort() not yet supported?
As Dave already posted, zip_iterator doesn't support return forward or bidirectional iterators, so std::sort() cannot be used. What you need is something like my tuple iterator (tupleit.zip from the files area on the boost yahoo group), which *does* support use with std::sort --- the iterator category of the tuple iterator is the minimum category of the supplied iterators. Anthony -- Anthony Williams Senior Software Engineer, Beran Instruments Ltd.
Anthony Williams <anthony_w.geo@yahoo.com> writes:
Gunter Winkler <guwi17@gmx.de> writes:
I tried to use boost::zip_iterator to sort 2 parallel arrays. Unfortunatly gcc does not compile the appended example because it can not convert
boost::detail::iterator_category_with_traversal<std::input_iterator_tag, boost::random_access_traversal_tag>
to either std::bidirectional_iterator_tag or std::random_access_iterator_tag. Thus it cannot dispatch the correct stl::__copy_backward() procedure.
Is sort() not yet supported?
As Dave already posted, zip_iterator doesn't support return forward or bidirectional iterators, so std::sort() cannot be used.
What you need is something like my tuple iterator (tupleit.zip from the files area on the boost yahoo group), which *does* support use with std::sort --- the iterator category of the tuple iterator is the minimum category of the supplied iterators.
How can sorting work? What type is returned from its operator* ? -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
David Abrahams <dave@boost-consulting.com> writes:
Anthony Williams <anthony_w.geo@yahoo.com> writes:
Gunter Winkler <guwi17@gmx.de> writes:
I tried to use boost::zip_iterator to sort 2 parallel arrays. Unfortunatly gcc does not compile the appended example because it can not convert
boost::detail::iterator_category_with_traversal<std::input_iterator_tag, boost::random_access_traversal_tag>
to either std::bidirectional_iterator_tag or std::random_access_iterator_tag. Thus it cannot dispatch the correct stl::__copy_backward() procedure.
Is sort() not yet supported?
As Dave already posted, zip_iterator doesn't support return forward or bidirectional iterators, so std::sort() cannot be used.
What you need is something like my tuple iterator (tupleit.zip from the files area on the boost yahoo group), which *does* support use with std::sort --- the iterator category of the tuple iterator is the minimum category of the supplied iterators.
How can sorting work? What type is returned from its operator* ?
For Forward, Bidi and Random-access Iterators, it returns a reference to a value held in the iterator. This value is a tuple of references to the value types of the supplied iterators. Actually it is a new class derived from the appropriate instantiation of boost::tuple, which ensures that copies are true copies --- the references in the boost::tuple base point *inside* the object, whereas access through the original object will reference the source. The downside of this is that the iterator has to hold the refernce tuple, which has to have space for a copy of the value tuple. This can be big if the value types are big. I could make this heap-allocated, which would reduce that size back again, at the expense of increased copy times, and an extra source of exceptions.... I've done that and it works OK. Looking at the code, operator[] returns a ref to a temporary, so that needs changing to just return the value_type (current discussions in the LWG notwithstanding), but that's not a big issue. (I've also done that in my copy) Here are some samples of usage; the testtupleit.cpp file from the archive has an example using std::sort. typedef std::vector<int> VecInt; VecInt v1,v2; // initialize v1 and v2 v1.resize(3); v2.resize(3); v1[0]=42; v2[0]=23; typedef TupleIt<boost::tuple<VecInt::iterator,VecInt::iterator> > TupleIteratorType; TupleIteratorType tupleIterator=makeTupleIterator(v1.begin(),v2.begin()); *tupleIterator=boost::tuple<int,int>(1,3); // write to vectors assert(v1[0]==1); assert(v2[0]==3); TupleIteratorType::value_type valueCopy=*tupleIterator; // read values valueCopy=boost::tuple<int,int>(9,27); // write to copy only // verify original vector unchanged assert(v1[0]==1); assert(v2[0]==3); // Ok, operator* returns a reference TupleIteratorType::value_type& opStarResult=*tupleIterator; int& intRef=opStarResult.get<0>(); // ref to element in v1 intRef=46; assert(v1[0]==46); Anthony -- Anthony Williams Senior Software Engineer, Beran Instruments Ltd.
Anthony Williams <anthony_w.geo@yahoo.com> writes:
David Abrahams <dave@boost-consulting.com> writes:
Anthony Williams <anthony_w.geo@yahoo.com> writes:
Gunter Winkler <guwi17@gmx.de> writes:
I tried to use boost::zip_iterator to sort 2 parallel arrays. Unfortunatly gcc does not compile the appended example because it can not convert
boost::detail::iterator_category_with_traversal<std::input_iterator_tag, boost::random_access_traversal_tag>
to either std::bidirectional_iterator_tag or std::random_access_iterator_tag. Thus it cannot dispatch the correct stl::__copy_backward() procedure.
Is sort() not yet supported?
As Dave already posted, zip_iterator doesn't support return forward or bidirectional iterators, so std::sort() cannot be used.
What you need is something like my tuple iterator (tupleit.zip from the files area on the boost yahoo group), which *does* support use with std::sort --- the iterator category of the tuple iterator is the minimum category of the supplied iterators.
How can sorting work? What type is returned from its operator* ?
For Forward, Bidi and Random-access Iterators, it returns a reference to a value held in the iterator.
I'm afraid those aren't conforming forward iterators :( 24.1.3: "If a and b are both dereferenceable, then a == b if and only if *a and *b are the same object. " Which is why we have to change counting_iterator to not be a forward iterator. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
David Abrahams <dave@boost-consulting.com> writes:
For Forward, Bidi and Random-access Iterators, it returns a reference to a value held in the iterator.
I'm afraid those aren't conforming forward iterators :(
24.1.3:
"If a and b are both dereferenceable, then a == b if and only if *a and *b are the same object. "
Which is why we have to change counting_iterator to not be a forward iterator.
Darn. I missed that requirement --- I was working off table 74, which just requires *a==*b if a==b (amusingly adding a requirement that the value type supports operator== in the process). This requirement makes it actually impossible to make an aggregating iterator anything other than an input or output iterator. :( On the plus side, my tuple iterator works with std::sort on every compiler I've tested it on. Do you know of any implementations that depend on this requirement being met for any of the standard algorithms? Maybe your effort on the new iterator categories can help with the problem? Anthony -- Anthony Williams Senior Software Engineer, Beran Instruments Ltd.
Anthony Williams <anthony_w.geo@yahoo.com> writes:
Which is why we have to change counting_iterator to not be a forward iterator.
Darn. I missed that requirement --- I was working off table 74, which just requires *a==*b if a==b (amusingly adding a requirement that the value type supports operator== in the process). This requirement makes it actually impossible to make an aggregating iterator anything other than an input or output iterator.
:(
On the plus side, my tuple iterator works with std::sort on every compiler I've tested it on. Do you know of any implementations that depend on this requirement being met for any of the standard algorithms?
I don't know, but it seems to me that there's another problem. If one of the component sequences contains types whose copy ctor may throw, how do you write the internal cache back to the sequence without potentially throwing during destruction? Consider passing the tuple iterator and a new value to this: template <class Iterator, class Value> void f(Iterator a, Value const& x) { *a = x; }
Maybe your effort on the new iterator categories can help with the problem?
Maybe. I hope so. It's currently a political as well as a technical mess. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
David Abrahams <dave@boost-consulting.com> writes:
Anthony Williams <anthony_w.geo@yahoo.com> writes:
Which is why we have to change counting_iterator to not be a forward iterator.
Darn. I missed that requirement --- I was working off table 74, which just requires *a==*b if a==b (amusingly adding a requirement that the value type supports operator== in the process). This requirement makes it actually impossible to make an aggregating iterator anything other than an input or output iterator.
:(
On the plus side, my tuple iterator works with std::sort on every compiler I've tested it on. Do you know of any implementations that depend on this requirement being met for any of the standard algorithms?
I don't know, but it seems to me that there's another problem. If one of the component sequences contains types whose copy ctor may throw, how do you write the internal cache back to the sequence without potentially throwing during destruction? Consider passing the tuple iterator and a new value to this:
template <class Iterator, class Value> void f(Iterator a, Value const& x) { *a = x; }
The internal cache in the iterator does not hold any values, it is essentially just an aggregator of references (derived from boost::typle<Iter1::value_type&,Iter2::value_type&....>). Since the sources are separate there is no real object to reference for the return value of operator*, so I had to make one. Updates like in your example therefore directly update the objects in the original containers, and so the problem you outline doesn't exist (thankfully). However, this tuple object is special. When you copy it, then it actually copies the referenced objects into a cache within the new copy. This avoids accidental modification of the source data.
Maybe your effort on the new iterator categories can help with the problem?
Maybe. I hope so. It's currently a political as well as a technical mess.
Yes, I've been following the discussions. Anthony -- Anthony Williams Senior Software Engineer, Beran Instruments Ltd.
Anthony Williams <anthony_w.geo@yahoo.com> writes:
David Abrahams <dave@boost-consulting.com> writes:
Anthony Williams <anthony_w.geo@yahoo.com> writes:
Which is why we have to change counting_iterator to not be a forward iterator.
Darn. I missed that requirement --- I was working off table 74, which just requires *a==*b if a==b (amusingly adding a requirement that the value type supports operator== in the process). This requirement makes it actually impossible to make an aggregating iterator anything other than an input or output iterator.
:(
On the plus side, my tuple iterator works with std::sort on every compiler I've tested it on. Do you know of any implementations that depend on this requirement being met for any of the standard algorithms?
I don't know, but it seems to me that there's another problem. If one of the component sequences contains types whose copy ctor may throw, how do you write the internal cache back to the sequence without potentially throwing during destruction? Consider passing the tuple iterator and a new value to this:
template <class Iterator, class Value> void f(Iterator a, Value const& x) { *a = x; }
The internal cache in the iterator does not hold any values, it is essentially just an aggregator of references (derived from boost::typle<Iter1::value_type&,Iter2::value_type&....>). Since the sources are separate there is no real object to reference for the return value of operator*, so I had to make one.
Oh, then it doesn't conform in another way. operator* on a ForwardIterator must return a real reference. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
David Abrahams <dave@boost-consulting.com> writes:
Anthony Williams <anthony_w.geo@yahoo.com> writes:
David Abrahams <dave@boost-consulting.com> writes:
Anthony Williams <anthony_w.geo@yahoo.com> writes:
Which is why we have to change counting_iterator to not be a forward iterator.
Darn. I missed that requirement --- I was working off table 74, which just requires *a==*b if a==b (amusingly adding a requirement that the value type supports operator== in the process). This requirement makes it actually impossible to make an aggregating iterator anything other than an input or output iterator.
:(
On the plus side, my tuple iterator works with std::sort on every compiler I've tested it on. Do you know of any implementations that depend on this requirement being met for any of the standard algorithms?
I don't know, but it seems to me that there's another problem. If one of the component sequences contains types whose copy ctor may throw, how do you write the internal cache back to the sequence without potentially throwing during destruction? Consider passing the tuple iterator and a new value to this:
template <class Iterator, class Value> void f(Iterator a, Value const& x) { *a = x; }
The internal cache in the iterator does not hold any values, it is essentially just an aggregator of references (derived from boost::typle<Iter1::value_type&,Iter2::value_type&....>). Since the sources are separate there is no real object to reference for the return value of operator*, so I had to make one.
Oh, then it doesn't conform in another way. operator* on a ForwardIterator must return a real reference.
I am somehow failing to communicate the design to you; it may be best for you to look at the code, or read my article on the original pair-based implementation (http://web.onetel.com/~anthony_w/cplusplus/pair_iterators.pdf) I worked hard on this to ensure it met all the requirements of the various iterator categories. I am disturbed that I missed the requirement about == implying the same object, but please do not assume that other requirements are not met unless you have direct evidence. operator* returns a real reference to an object stored within the iterator. This object is a tuple of references to the objects returned by dereferencing the source iterators, with some custom behaviour to handle copying. This custom behaviour means that copies of this tuple actually hold copies of the originally-referenced data, and the references on this new copy point back within itself to the copies of the data. Anthony -- Anthony Williams Senior Software Engineer, Beran Instruments Ltd.
Anthony Williams <anthony_w.geo@yahoo.com> writes:
I am somehow failing to communicate the design to you; it may be best for you to look at the code, or read my article on the original pair-based implementation (http://web.onetel.com/~anthony_w/cplusplus/pair_iterators.pdf)
I worked hard on this to ensure it met all the requirements of the various iterator categories. I am disturbed that I missed the requirement about == implying the same object, but please do not assume that other requirements are not met unless you have direct evidence.
I wasn't assuming; I was just wrong ;-)
operator* returns a real reference to an object stored within the iterator. This object is a tuple of references to the objects returned by dereferencing the source iterators, with some custom behaviour to handle copying.
This custom behaviour means that copies of this tuple actually hold copies of the originally-referenced data, and the references on this new copy point back within itself to the copies of the data.
That is evil and sneaky! I love it! Thanks for the explanation. Is that object the same as the iterator's value_type? If so, I don't see how swap(*i1, *i2) can work, and thus most sort implementations should fail. If not, it's not conforming in another way because operator* must be a reference to value_type. Have I missed something else? -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
David Abrahams <dave@boost-consulting.com> writes:
Anthony Williams <anthony_w.geo@yahoo.com> writes:
operator* returns a real reference to an object stored within the iterator. This object is a tuple of references to the objects returned by dereferencing the source iterators, with some custom behaviour to handle copying.
This custom behaviour means that copies of this tuple actually hold copies of the originally-referenced data, and the references on this new copy point back within itself to the copies of the data.
That is evil and sneaky! I love it!
<G>
Is that object the same as the iterator's value_type?
Yes, otherwise it wouldn't be conforming (as you point out below)
If so, I don't see how swap(*i1, *i2) can work, and thus most sort implementations should fail. If not, it's not conforming in another way because operator* must be a reference to value_type. Have I missed something else?
The default implementation of swap is generally along the lines of template<typename T> void swap(T& lhs,T& rhs) { T temp(lhs); lhs=rhs; rhs=temp; } The initialization of temp creates a genuine copy of the data. The two assignments then use the assignment operator of boost::tuple to assign through the references. Does that make it clearer? Anthony -- Anthony Williams Senior Software Engineer, Beran Instruments Ltd.
Anthony Williams <anthony_w.geo@yahoo.com> writes:
The default implementation of swap is generally along the lines of
template<typename T> void swap(T& lhs,T& rhs) { T temp(lhs); lhs=rhs; rhs=temp; }
The initialization of temp creates a genuine copy of the data.
How so? Didn't you say that *i is a reference to a tuple of references? That makes T a tuple of references, and the initialization of a tuple of references just copies a bunch of pointers IIUC.
The two assignments then use the assignment operator of boost::tuple to assign through the references.
Does that make it clearer?
Not yet. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
David Abrahams <dave@boost-consulting.com> writes:
Anthony Williams <anthony_w.geo@yahoo.com> writes:
The default implementation of swap is generally along the lines of
template<typename T> void swap(T& lhs,T& rhs) { T temp(lhs); lhs=rhs; rhs=temp; }
The initialization of temp creates a genuine copy of the data.
How so? Didn't you say that *i is a reference to a tuple of references?
With some nifty code that ensures copies are real copies (which you commented was evil and sneaky). The type is OwningRefTuple<boost::tuple<type1,type2,type3...> > and derives from boost::tuple<type1&, type2&,type3&...>
That makes T a tuple of references, and the initialization of a tuple of references just copies a bunch of pointers IIUC.
Yes. That's why the nifty code is there. Time for some code. MakeTupleTypeWithReferences does just that --- it takes a tuple and produces a new tuple type where every element is a reference to the corresponding type in the original tuple. OwningBase is there to ensure that the owned data is initialized before we try and bind references to it (if necessary). OwningRefTuple binds it all together. namespace detail { struct PreserveReferences {}; template<typename OwnedType> struct OwningBase { std::auto_ptr<OwnedType> tupleBuf; OwningBase() {} template<typename SomeType> OwningBase(SomeType &source): tupleBuf(new OwnedType(source)) {} }; template<typename SourceTuple> struct MakeTupleTypeWithReferences { typedef MakeTupleTypeWithReferences<typename SourceTuple::tail_type> TailTupleTypeBuilder; typedef typename TailTupleTypeBuilder::Type TailTupleType; typedef boost::tuples::cons<typename boost::add_reference<typename SourceTuple::head_type>::type, TailTupleType> Type; template<typename Tuple> static Type makeTuple(Tuple& source) { return Type(source.get_head(),TailTupleTypeBuilder::makeTuple(source.get_tail())); } }; template<> struct MakeTupleTypeWithReferences<boost::tuples::null_type> { typedef boost::tuples::null_type Type; static Type makeTuple(boost::tuples::null_type) { return Type(); } }; } template<typename TupleType> struct OwningRefTuple: private detail::OwningBase<TupleType>, public detail::MakeTupleTypeWithReferences<TupleType>::Type { private: typedef detail::MakeTupleTypeWithReferences<TupleType> BaseTypeBuilder; typedef typename BaseTypeBuilder::Type BaseType; typedef detail::OwningBase<TupleType> OwningBaseType; public: typedef typename BaseType::head_type head_type; typedef typename BaseType::tail_type tail_type; private: typedef TupleType OwnedTuple; OwnedTuple* getTuplePtr() { return this->tupleBuf.get(); } public: // copy from other types of tuples too template<typename SomeTuple> OwningRefTuple(const SomeTuple& other): OwningBaseType(other),BaseType(BaseTypeBuilder::makeTuple(*getTuplePtr())) { } // copying copies values by default OwningRefTuple(const OwningRefTuple& other): OwningBaseType(other),BaseType(BaseTypeBuilder::makeTuple(*getTuplePtr())) { } // overload used for building the initial instance that references // data elsewhere template<typename SomeTuple> OwningRefTuple(SomeTuple& other,detail::PreserveReferences const&): BaseType(BaseTypeBuilder::makeTuple(other)) { } // assignment assigns to referenced values template<typename SomeTuple> OwningRefTuple& operator=(const SomeTuple& other) { BaseType::operator=(other); return *this; } OwningRefTuple& operator=(const OwningRefTuple& other) { BaseType::operator=(other); return *this; } }; Anthony -- Anthony Williams Senior Software Engineer, Beran Instruments Ltd.
participants (3)
-
Anthony Williams -
David Abrahams -
Gunter Winkler