Using single-pass ranges. - Boost-users - lists.preview.boost.org

newer
How to create array of...

Using single-pass ranges.

older
Connecting signals2::signal to...

Robert Jones

24 Jul 2012 24 Jul '12

10:04 a.m.

I have a class that hands out a sequence of Things through a getNextThing() interface, ie., struct Thing { }; struct ThingFeed { Thing * getNextThing( ); }; returning null when there's no more things. I'd like to be able to feed this into the Boost range-based algorithms, something like boost::for_each( thingFeedProxy | filter( someCondition ), doSomething ); But it's not clear to me how or if I can represent my ThingFeed as a range. Any thoughts or advice appreciated. Thx, Rob

Attachments:

attachment.html (text/html — 1.0 KB)

Reply

Sign in to reply online Use email software

Show replies by date

Neil Groves

24 Jul 24 Jul

10:17 a.m.

Robert, On Tuesday, July 24, 2012, Robert Jones wrote:

I have a class that hands out a sequence of Things through a getNextThing() interface, ie.,

struct Thing { };

struct ThingFeed { Thing * getNextThing( ); };

returning null when there's no more things. I'd like to be able to feed this into the Boost range-based algorithms, something like

Since we are not in a position to offer range primitives, there is more work required than one would like. To maximize interoperability with algorithms and existing C++ code the ranges in Boost.Range are limited to being implemented on top of iterators. Therefore the getNextThing() would need to be part of an increment operator / operators upon a forward traversal iterator. This is not difficult to implement using Boost.Iterator. If you do not require this level of interoperability and you are merely using your own algorithms, then it is quite reasonable to use your own range primitives, perhaps similar in nature to the ones proposed by Andrei Alexandrescu.

boost::for_each( thingFeedProxy | filter( someCondition ), doSomething );

But it's not clear to me how or if I can represent my ThingFeed as a range. Any thoughts or advice appreciated.

To represent the example shown is tricky. Normally it is not this difficult because one implements containers to interoperate with the STL and therefore have iterators. I do agree that the best ultimate solution is to have well-specified Range Primitive Concepts and algorithms similar to those provided by Boost.Range that operate upon these primitive types. The reason you cannot do this today is simply because I'm too rubbish and slow to have done it yet. I am making a stronger effort to clear my TRAC tickets and then hopefully gain some time to release a new wave of features.

Thx, Rob

Sorry, Neil Groves

Reply

Sign in to reply online Use email software

Nathan Ridge

25 Jul 25 Jul

4:13 a.m.

...
I have a class that hands out a sequence of Things through a getNextThing() interface, ie.,

struct Thing { };

struct ThingFeed { Thing * getNextThing( ); };

returning null when there's no more things. I'd like to be able to feed this into the Boost range-based algorithms, something like

Since we are not in a position to offer range primitives, there is more work required than one would like. To maximize interoperability with algorithms and existing C++ code the ranges in Boost.Range are limited to being implemented on top of iterators. Therefore the getNextThing() would need to be part of an increment operator / operators upon a forward traversal iterator. This is not difficult to implement using Boost.Iterator.

Here's how you might do such a thing (untested): class ThingIterator : public boost::iterator_facade { public: // Public interface ThingIterator(ThingFeed& feed, Thing* cur = NULL) : m_feed(feed), m_cur(cur) {} private: // Interface to boost::iterator_facade void increment() { m_cur = m_feed.getNextThing(); } Thing& dereference() const { return *m_cur; } bool equal(const ThingIterator& other) const { return m_cur == other.m_cur; } private: // Implementation ThingFeed& m_feed; Thing* m_cur; }; class ThingRange : public boost::iterator_range<ThingIterator> { public: ThingRange(ThingFeed& feed) : boost::iterator_range<ThingIterator>( ThingIterator(feed, feed.getNextThing()), ThingIterator(feed)) {} }; ... ThingFeed feed; ... boost::for_each( ThingRange(feed) | filter( someCondition ), doSomething ); Regards, Nate

Reply

Sign in to reply online Use email software

Robert Jones

10:07 a.m.

On Wed, Jul 25, 2012 at 5:13 AM, Nathan Ridge wrote:

Here's how you might do such a thing (untested):

Hi Nathan That may be untested, but basically worked as is! All I had to do was adjust the access on equal(), increment() & dereference() and it worked perfectly. Full code attached, built with Boost 1.47 and gcc-4.6.2, many thanks. Rob. #include <iostream> #include #include #include #include struct Thing { Thing( char c ) : c( c ) { } char c; }; std::ostream & operator << ( std::ostream & ostrm, const Thing & thing ) { return ostrm << thing.c; } struct ThingFeed { ThingFeed( const char * thing_values ) : m_current_value( thing_values ) { } Thing * getNextThing( ) { return * m_current_value ? new Thing( * m_current_value ++ ) : 0; } private: const char * m_current_value; }; struct ThingIterator : public boost::iterator_facade { ThingIterator(ThingFeed& feed, Thing* cur = NULL) : m_feed(feed), m_cur(cur) {} bool equal(const ThingIterator& other) const { return m_cur == other.m_cur; } void increment() { m_cur = m_feed.getNextThing(); } Thing& dereference() const { return *m_cur; } private: ThingFeed& m_feed; Thing* m_cur; }; class ThingRange : public boost::iterator_range<ThingIterator> { public: ThingRange(ThingFeed& feed) : boost::iterator_range<ThingIterator>( ThingIterator(feed, feed.getNextThing()), ThingIterator(feed)) {} }; void printThing( const Thing & thing ) { std::cout << thing << "\n"; } bool thingFilter( const Thing & thing ) { return thing.c != 'c'; } int main( ) { ThingFeed feed( "abcd" ); boost::for_each( ThingRange(feed) | boost::adaptors::filtered( thingFilter ), printThing ); }

Reply

Sign in to reply online Use email software

Robert Jones

3 Aug 3 Aug

10:15 a.m.

Hi All, When a range is constructed from a 'getNextThing()' sort of interface, it seems quite reasonable for that interface to return references to an abstract type. However that doesn't seem to be supported by Boost.IteratorFacade. I guess this only comes up in this context, as you couldn't construct a container of abstract objects, but is this a know limitation of iterator_facade? Full source attached. Thx, Rob. #include <iostream> #include #include #include #include struct AbstractThing { virtual char get_c( ) const = 0; virtual ~AbstractThing( ) { } }; struct Thing : AbstractThing { Thing( char c ) : c( c ) { } char get_c( ) const { return c; } private: char c; }; struct ThingFeed { ThingFeed( const char * thing_values ) : m_current_value( thing_values ) { } AbstractThing * getNextThing( ) { return * m_current_value ? new Thing( * m_current_value ++ ) : 0; } private: const char * m_current_value; }; struct ThingIterator : public boost::iterator_facade { ThingIterator( ThingFeed & feed, AbstractThing * cur = NULL ) : m_feed( feed ), m_cur( cur ) {} bool equal( const ThingIterator & other ) const { return m_cur == other.m_cur; } void increment( ) { m_cur = m_feed.getNextThing( ); } AbstractThing & dereference( ) const { return * m_cur; } private: ThingFeed & m_feed; AbstractThing * m_cur; }; struct ThingRange : public boost::iterator_range<ThingIterator> { ThingRange( ThingFeed & feed ) : boost::iterator_range<ThingIterator>( ThingIterator( feed, feed.getNextThing( ) ), ThingIterator( feed ) ) {} }; void printThing( const AbstractThing & thing ) { std::cout << thing.get_c( ) << "\n"; } int main( ) { ThingFeed feed( "abcd" ); boost::for_each( ThingRange(feed), printThing ); }

~/local/gcc-4.6.2/bin/g++ -std=c++0x -I ~/local/boost_1_48_0/include -g -Werror -W -fno-strict-aliasing -fno-inline -Wall -Wno-uninitialized -Wcast-align -Wwrite-strings -Wunused -Wnon-virtual-dtor -Wextra -c -o iterate.o iterate.cpp In file included from iterate.cpp|2| 0: /home/rjones/local/boost_1_48_0/include/boost/iterator/iterator_facade.hpp: In instantiation of ‘boost::detail::postfix_increment_proxy<ThingIterator>’: /home/rjones/local/boost_1_48_0/include/boost/range/concepts.hpp|155 col 17| instantiated from ‘boost::range_detail::SinglePassIteratorConcept<Iterator>::~SinglePassIteratorConcept() [with Iterator = ThingIterator]’ /home/rjones/local/boost_1_48_0/include/boost/concept/detail/general.hpp|38

col 28| instantiated from ‘static void boost::concepts::requirement<boost::concepts::failed************ Model::************>::failed() [with Model = boost::range_detail::SinglePassIteratorConcept<ThingIterator>]’ /home/rjones/local/boost_1_48_0/include/boost/range/concepts.hpp|259 col 1| instantiated from ‘boost::SinglePassRangeConcept<const ThingRange>’ /home/rjones/local/boost_1_48_0/include/boost/concept/detail/has_constraints.hpp|42 col 5| instantiated from ‘const bool boost::concepts::not_satisfied<boost::SinglePassRangeConcept<const ThingRange> >::value’ /home/rjones/local/boost_1_48_0/include/boost/concept/detail/has_constraints.hpp|45 col 31| instantiated from ‘boost::concepts::not_satisfied<boost::SinglePassRangeConcept<const ThingRange> >’ /home/rjones/local/boost_1_48_0/include/boost/mpl/if.hpp|67 col 11| instantiated from ‘boost::mpl::if_<boost::concepts::not_satisfied<boost::SinglePassRangeConcept<const ThingRange> >, boost::concepts::constraint<boost::SinglePassRangeConcept<const ThingRange> >, boost::concepts::requirement<boost::concepts::failed************ boost::SinglePassRangeConcept<const ThingRange>::************> >’ /home/rjones/local/boost_1_48_0/include/boost/concept/detail/general.hpp|50 col 8| instantiated from ‘boost::concepts::requirement_<void (*)(boost::SinglePassRangeConcept<const ThingRange>)>’ /home/rjones/local/boost_1_48_0/include/boost/range/algorithm/for_each.hpp|91 col 1| instantiated from ‘UnaryFunction boost::range::for_each(const SinglePassRange&, UnaryFunction) [with SinglePassRange = ThingRange, UnaryFunction = void (*)(const AbstractThing&)]’ iterate.cpp|55 col 51| instantiated from here /home/rjones/local/boost_1_48_0/include/boost/iterator/iterator_facade.hpp|158 col 28| error: cannot declare field ‘boost::detail::postfix_increment_proxy<ThingIterator>::stored_value’ to be of abstract type ‘AbstractThing’ iterate.cpp|7 col 8| note: because the following virtual functions are pure within ‘AbstractThing’: iterate.cpp|8 col 18| note: virtual char AbstractThing::get_c() const

Reply

Sign in to reply online Use email software

Nathan Ridge

5:07 p.m.

When a range is constructed from a 'getNextThing()' sort of interface, it seems quite reasonable for that interface to return references to an abstract type. However that doesn't seem to be supported by Boost.IteratorFacade. I guess this only comes up in this context, as you couldn't construct a container of abstract objects, but is this a know limitation of iterator_facade?

I'm not sure whether this can be done with iterator_facade. If not, Boost.Iterator could probably use a new utility (abstract_iterator_facade?) that makes this possible. As a workaround, though, you can make ThingRange be a range of pointers instead. See code below. Regards, Nate #include <iostream> #include #include #include #include struct AbstractThing { virtual char get_c( ) const = 0; virtual ~AbstractThing( ) { } }; struct Thing : AbstractThing { Thing( char c ) : c( c ) { } char get_c( ) const { return c; } private: char c; }; struct ThingFeed { ThingFeed( const char * thing_values ) : m_current_value( thing_values ) { } AbstractThing * getNextThing( ) { return * m_current_value ? new Thing( * m_current_value ++ ) : 0; } private: const char * m_current_value; }; struct ThingIterator : public boost::iterator_facade { ThingIterator( ThingFeed & feed, AbstractThing * cur = NULL ) : m_feed( feed ), m_cur( cur ) {} bool equal( const ThingIterator & other ) const { return m_cur == other.m_cur; } void increment( ) { m_cur = m_feed.getNextThing( ); } AbstractThing * dereference( ) const { return m_cur; } private: ThingFeed & m_feed; AbstractThing * m_cur; }; struct ThingRange : public boost::iterator_range<ThingIterator> { ThingRange( ThingFeed & feed ) : boost::iterator_range<ThingIterator>( ThingIterator( feed, feed.getNextThing( ) ), ThingIterator( feed ) ) {} }; void printThing( const AbstractThing * thing ) { std::cout << thing->get_c( ) << "\n"; } int main( ) { ThingFeed feed( "abcd" ); boost::for_each( ThingRange(feed), printThing ); }

Reply

Sign in to reply online Use email software

Jeffrey Lee Hellrung, Jr.

11:51 p.m.

On Fri, Aug 3, 2012 at 3:15 AM, Robert Jones wrote:

Hi All,

When a range is constructed from a 'getNextThing()' sort of interface, it seems quite reasonable for that interface to return references to an abstract type. However that doesn't seem to be supported by Boost.IteratorFacade. I guess this only comes up in this context, as you couldn't construct a container of abstract objects, but is this a know limitation of iterator_facade?

Full source attached.

Thx, Rob.

#include <iostream> #include #include #include #include

struct AbstractThing { virtual char get_c( ) const = 0; virtual ~AbstractThing( ) { } };

struct Thing : AbstractThing { Thing( char c ) : c( c ) { } char get_c( ) const { return c; } private: char c; };

struct ThingFeed { ThingFeed( const char * thing_values ) : m_current_value( thing_values ) { } AbstractThing * getNextThing( ) { return * m_current_value ? new Thing( * m_current_value ++ ) : 0; } private: const char * m_current_value; };

struct ThingIterator : public boost::iterator_facade { ThingIterator( ThingFeed & feed, AbstractThing * cur = NULL ) : m_feed( feed ), m_cur( cur ) {}

bool equal( const ThingIterator & other ) const { return m_cur == other.m_cur; } void increment( ) { m_cur = m_feed.getNextThing( ); } AbstractThing & dereference( ) const { return * m_cur; }

private:

ThingFeed & m_feed; AbstractThing * m_cur; };

struct ThingRange : public boost::iterator_range<ThingIterator> { ThingRange( ThingFeed & feed ) : boost::iterator_range<ThingIterator>( ThingIterator( feed, feed.getNextThing( ) ), ThingIterator( feed ) ) {} };

void printThing( const AbstractThing & thing ) { std::cout << thing.get_c( ) << "\n"; }

int main( ) { ThingFeed feed( "abcd" ); boost::for_each( ThingRange(feed), printThing ); }

...
~/local/gcc-4.6.2/bin/g++ -std=c++0x -I ~/local/boost_1_48_0/include -g -Werror -W -fno-strict-aliasing -fno-inline -Wall -Wno-uninitialized -Wcast-align -Wwrite-strings -Wunused -Wnon-virtual-dtor -Wextra -c -o iterate.o iterate.cpp In file included from iterate.cpp|2| 0: /home/rjones/local/boost_1_48_0/include/boost/iterator/iterator_facade.hpp: In instantiation of ‘boost::detail::postfix_increment_proxy<ThingIterator>’: /home/rjones/local/boost_1_48_0/include/boost/range/concepts.hpp|155 col 17| instantiated from ‘boost::range_detail::SinglePassIteratorConcept<Iterator>::~SinglePassIteratorConcept() [with Iterator = ThingIterator]’ /home/rjones/local/boost_1_48_0/include/boost/concept/detail/general.hpp|38

col 28| instantiated from ‘static void boost::concepts::requirement<boost::concepts::failed************ Model::************>::failed() [with Model = boost::range_detail::SinglePassIteratorConcept<ThingIterator>]’ /home/rjones/local/boost_1_48_0/include/boost/range/concepts.hpp|259 col 1| instantiated from ‘boost::SinglePassRangeConcept<const ThingRange>’ /home/rjones/local/boost_1_48_0/include/boost/concept/detail/has_constraints.hpp|42 col 5| instantiated from ‘const bool boost::concepts::not_satisfied<boost::SinglePassRangeConcept<const ThingRange> >::value’ /home/rjones/local/boost_1_48_0/include/boost/concept/detail/has_constraints.hpp|45 col 31| instantiated from ‘boost::concepts::not_satisfied<boost::SinglePassRangeConcept<const ThingRange> >’ /home/rjones/local/boost_1_48_0/include/boost/mpl/if.hpp|67 col 11| instantiated from ‘boost::mpl::if_<boost::concepts::not_satisfied<boost::SinglePassRangeConcept<const ThingRange> >, boost::concepts::constraint<boost::SinglePassRangeConcept<const ThingRange> >, boost::concepts::requirement<boost::concepts::failed************ boost::SinglePassRangeConcept<const ThingRange>::************> >’ /home/rjones/local/boost_1_48_0/include/boost/concept/detail/general.hpp|50 col 8| instantiated from ‘boost::concepts::requirement_<void (*)(boost::SinglePassRangeConcept<const ThingRange>)>’ /home/rjones/local/boost_1_48_0/include/boost/range/algorithm/for_each.hpp|91 col 1| instantiated from ‘UnaryFunction boost::range::for_each(const SinglePassRange&, UnaryFunction) [with SinglePassRange = ThingRange, UnaryFunction = void (*)(const AbstractThing&)]’ iterate.cpp|55 col 51| instantiated from here /home/rjones/local/boost_1_48_0/include/boost/iterator/iterator_facade.hpp|158 col 28| error: cannot declare field ‘boost::detail::postfix_increment_proxy<ThingIterator>::stored_value’ to be of abstract type ‘AbstractThing’ iterate.cpp|7 col 8| note: because the following virtual functions are pure within ‘AbstractThing’: iterate.cpp|8 col 18| note: virtual char AbstractThing::get_c() const

This might work if, as the error suggests, you define your own post-increment operator in the derived class, rather than using the one provided by iterator_facade. Although, I'm not sure, it might not be possible for *(i++) to work in this case without actually holding the result of *i prior to the increment, which precludes the use of an abstract reference type. Let me know if that answers your inquiry. - Jeff

Reply

Sign in to reply online Use email software

4482

Age (days ago)

4492

Last active (days ago)

Download

6 comments

4 participants

tags

participants (4)

Jeffrey Lee Hellrung, Jr.
Nathan Ridge
Neil Groves
Robert Jones