any boost library for referring a portion of the container ?
Hi, I am having a few containers whose some portion I want to refer to another class (sometime I need to refer to a continuous portion, while sometime need a non-continuous portion) . At present I have written all of these myself. But wondering if a few portion can be substituted by some boost library. Just to make the concept clear, I am elaborating the structure and why it is done in that way. In the program it takes the user handwriting (as entered using digital pen etc) and analysis them. as user writes, I register points (x,y coord) and put them in an deque (in actual case I am using boost::circular_buffer_space_optimized ). Now, a second deque (or other container) stores another structure Trace, which has 2 index pointing start & end of that continuous writing until pen up occurs. These have to be 2 index rather than iterator, as iterator may get (and usually gets ) invalidated while more points are added in the point deque. Thus Trace refers deque<Point> Now from the trace structure I return the points for the trace (boost::sub_range ) using the 2 index and the deque (i.e from deque<Point> get iterator, add index as offset , make sub_range and return). Now these are the continues portions , referred by 2 index. Next, some such things can be even not continuous. In that case I store all index to which it points (in a vector ) and return a sub_range kind of structure (named index_range ) which takes these index and a container, and iterates over it jumping by those specific offsets. Example can be a Character class which refers some of those traces , not necessarily continuous (like user writes a dot much later than the i , thus Character i contains index of the vertical stroke of the i & dot ) Similarly more hierarchy are constructed, like Trace => Page, and Character => Word => Line => Paragraph => Page etc. Most of them contains 2 index and with the help of the container returns a boost sub_range , while some contains a vector of index (size_t) and returns index_range (created by me) . So far I found it is the ONLY way to create a level of hierarchy/ view from different set of dynamic data. (The other can be storing everything as a pointer in the container, and creating by new, in that case no problem arises as the objects are not movable, but in C++ it is quite bad solution) A Graphical representation is like, =============== deque<Point> ===================== <=remove old data => add new data | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | =============== deque<Trace> ==================== | 1 | 2 | =============== deque<Page> ===================== These are for continuous data (i.e 2 index struct & boost::sub_range ) ================ deque<Trace> ==================== |1,3,4| 2 | 5,6 | 7,9 | 8 | ... ================== deque<Character> =============== | 1,2,4, 5 | 3 | .... ================== deque<Word> ===================== | 1 | 2 | 3 | .... (assuming past a line user doesn't correct word, they can be made a pair of index ! ) ================== deque<Line> ===================== .... ================== deque<Paragraph> ================ etc... My question , 1) had anyone faced these kind of design , where a class referrers a portion of STL container ? and multiple view from same set of data exists (otherwise I could had Trace contains the points , instead of having index of the portion, if Trace is the only view for the points ) 2) Any boost library / other library is there to help these kind of design ? I had posted a same kind of topic in C++ newsgroup also, but it seems their people are more concerned with answering C++ standard based question . I think, boost may be the better news group to ask this question, as boosters work in a broader area. Thanks to all, esp to those who share their thought on it ... abir -- Abir Basak, Member IEEE B. Tech, IIT Kharagpur email: abir@abirbasak.com homepage: www.abirbasak.com
abir basak wrote:
Hi, I am having a few containers whose some portion I want to refer to another class (sometime I need to refer to a continuous portion, while sometime need a non-continuous portion) . At present I have written all of these myself. But wondering if a few portion can be substituted by some boost library.
Just to make the concept clear, I am elaborating the structure and why it is done in that way. In the program it takes the user handwriting (as entered using digital pen etc) and analysis them. as user writes, I register points (x,y coord) and put them in an deque (in actual case I am using boost::circular_buffer_space_optimized ).
Now, a second deque (or other container) stores another structure Trace, which has 2 index pointing start & end of that continuous writing until pen up occurs. These have to be 2 index rather than iterator, as iterator may get (and usually gets ) invalidated while more points are added in the point deque. Thus Trace refers deque<Point> Now from the trace structure I return the points for the trace (boost::sub_range ) using the 2 index and the deque (i.e from deque<Point> get iterator, add index as offset , make sub_range and return). Now these are the continues portions , referred by 2 index. Next, some such things can be even not continuous. In that case I store all index to which it points (in a vector ) and return a sub_range kind of structure (named index_range ) which takes these index and a container, and iterates over it jumping by those specific offsets.
Example can be a Character class which refers some of those traces , not necessarily continuous (like user writes a dot much later than the i , thus Character i contains index of the vertical stroke of the i & dot )
Similarly more hierarchy are constructed, like Trace => Page, and Character => Word => Line => Paragraph => Page etc.
Most of them contains 2 index and with the help of the container returns a boost sub_range , while some contains a vector of index (size_t) and returns index_range (created by me) .
So far I found it is the ONLY way to create a level of hierarchy/ view from different set of dynamic data. (The other can be storing everything as a pointer in the container, and creating by new, in that case no problem arises as the objects are not movable, but in C++ it is quite bad solution)
A Graphical representation is like, =============== deque<Point> ===================== <=remove old data => add new data | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | =============== deque<Trace> ==================== | 1 | 2 | =============== deque<Page> =====================
These are for continuous data (i.e 2 index struct & boost::sub_range )
================ deque<Trace> ==================== |1,3,4| 2 | 5,6 | 7,9 | 8 | ... ================== deque<Character> =============== | 1,2,4, 5 | 3 | .... ================== deque<Word> ===================== | 1 | 2 | 3 | .... (assuming past a line user doesn't correct word, they can be made a pair of index ! ) ================== deque<Line> ===================== .... ================== deque<Paragraph> ================ etc...
My question , 1) had anyone faced these kind of design , where a class referrers a portion of STL container ? and multiple view from same set of data exists (otherwise I could had Trace contains the points , instead of having index of the portion, if Trace is the only view for the points )
2) Any boost library / other library is there to help these kind of design ?
I had posted a same kind of topic in C++ newsgroup also, but it seems their people are more concerned with answering C++ standard based question . I think, boost may be the better news group to ask this question, as boosters work in a broader area.
Thanks to all, esp to those who share their thought on it ... abir
Though I can't understand exactly what you mean because of my poor english, I guess the solution is polymorphic range, which is the 'iterator_range' of 'any_iterator'? Assume 'make_xxx' returns 'iterator_range' of 'xxx_iterator'. deque<any_range> traces; traces.push_back(make_counting(1, 5)); // continuous (light-weight) traces.push_back(an_index_range); // non-continuous (needs its own storage) Draw( make_permutation(points, traces[0]) ); Draw( make_permutation(points, traces[1]) ); If my guess is right, I'll specify urls of 'any_iterator' implementations. Regards, -- Shunsuke Sogame
shunsuke wrote:
abir basak wrote:
Hi, I am having a few containers whose some portion I want to refer to another class (sometime I need to refer to a continuous portion, while sometime need a non-continuous portion) . At present I have written all of these myself. But wondering if a few portion can be substituted by some boost library.
Just to make the concept clear, I am elaborating the structure and why it is done in that way. In the program it takes the user handwriting (as entered using digital pen etc) and analysis them. as user writes, I register points (x,y coord) and put them in an deque (in actual case I am using boost::circular_buffer_space_optimized ).
Now, a second deque (or other container) stores another structure Trace, which has 2 index pointing start & end of that continuous writing until pen up occurs. These have to be 2 index rather than iterator, as iterator may get (and usually gets ) invalidated while more points are added in the point deque. Thus Trace refers deque<Point> Now from the trace structure I return the points for the trace (boost::sub_range ) using the 2 index and the deque (i.e from deque<Point> get iterator, add index as offset , make sub_range and return). Now these are the continues portions , referred by 2 index. Next, some such things can be even not continuous. In that case I store all index to which it points (in a vector ) and return a sub_range kind of structure (named index_range ) which takes these index and a container, and iterates over it jumping by those specific offsets.
Example can be a Character class which refers some of those traces , not necessarily continuous (like user writes a dot much later than the i , thus Character i contains index of the vertical stroke of the i & dot )
Similarly more hierarchy are constructed, like Trace => Page, and Character => Word => Line => Paragraph => Page etc.
Most of them contains 2 index and with the help of the container returns a boost sub_range , while some contains a vector of index (size_t) and returns index_range (created by me) .
So far I found it is the ONLY way to create a level of hierarchy/ view from different set of dynamic data. (The other can be storing everything as a pointer in the container, and creating by new, in that case no problem arises as the objects are not movable, but in C++ it is quite bad solution)
A Graphical representation is like, =============== deque<Point> ===================== <=remove old data => add new data | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | =============== deque<Trace> ==================== | 1 | 2 | =============== deque<Page> =====================
These are for continuous data (i.e 2 index struct & boost::sub_range )
================ deque<Trace> ==================== |1,3,4| 2 | 5,6 | 7,9 | 8 | ... ================== deque<Character> =============== | 1,2,4, 5 | 3 | .... ================== deque<Word> ===================== | 1 | 2 | 3 | .... (assuming past a line user doesn't correct word, they can be made a pair of index ! ) ================== deque<Line> ===================== .... ================== deque<Paragraph> ================ etc...
My question , 1) had anyone faced these kind of design , where a class referrers a portion of STL container ? and multiple view from same set of data exists (otherwise I could had Trace contains the points , instead of having index of the portion, if Trace is the only view for the points )
2) Any boost library / other library is there to help these kind of design ?
I had posted a same kind of topic in C++ newsgroup also, but it seems their people are more concerned with answering C++ standard based question . I think, boost may be the better news group to ask this question, as boosters work in a broader area.
Thanks to all, esp to those who share their thought on it ... abir
Though I can't understand exactly what you mean because of my poor english, I guess the solution is polymorphic range, which is the 'iterator_range' of 'any_iterator'?
Assume 'make_xxx' returns 'iterator_range' of 'xxx_iterator'.
deque<any_range> traces; traces.push_back(make_counting(1, 5)); // continuous (light-weight) traces.push_back(an_index_range); // non-continuous (needs its own storage)
Draw( make_permutation(points, traces[0]) ); Draw( make_permutation(points, traces[1]) );
If my guess is right, I'll specify urls of 'any_iterator' implementations.
Regards,
It is better if I try to post some code to show what I exactly trying to do. ( I am trying to capture digital pen input and create a hierarchical structure from it ) ///This is a range (2 point index, which can create 2 iterators with the ///help of the container, I am using boost::sub_range for that ) typedef std::pair<std::size_t,std::size_t> range_t; ///This is a multi index range allows iterate over a few specific index ///on a container , used with my index_range and container. (for ///simplicity now it uses vector, it can be any container ) typedef std::vector<size_t> index_t; ///The index range. iterates over the specific position on the container ///a simplified version to show the concept. It has const correctness ///and all other functions that sub_range has. It takes container & ///index vector unlike iterators in boost::sub_range. template<typename C> class index_range{ public: typedef C container_type; typedef typename C::iterator iterator; typedef typename C::reference reference; typedef typename C::pointer pointer; typedef typename C::size_type size_type; private: index_t index_; C& c_; size_type pos_; public: index_range(C& c,index_t index) : c_(c),index_(index) , pos_(0){} size_type size()const { return index_.size();} reference operator[](size_type pos) { return c_[ index_[pos] ] }; reference front() { return c_[index_[0] ] ;} reference back() { return c_[index_[size()-1]] ; } reference operator++(){ return c_[index_ [ pos_ ++] ] ; } }; ///The point comes as user input through digital pen struct point{ int x; int y; point(int _x,int _y) : x(_x),y(_y){} }; typedef std::deque<point> point_buffer; typedef boost::sub_range<point_buffer> point_range; ///The buffer of points. point_buffer points; ///trace a continuous user writing, until pen up. points a portion ///of point_buffer struct trace{ range_t range; point_range get_points() { return boost::make_iterator_range(points.begin()+range.first,points.begin()+range.second); } }; typedef std::deque<trace> trace_buffer; typedef boost::sub_range<trace_buffer> trace_range; typedef index_range<trace_buffer> trace_index_range; ///buffer for traces. trace_buffer traces; ///a page contains a set of traces. struct page{ range_t range; trace_range get_traces(){ return boost::make_iterator_range(traces.begin()+range.first,traces.begin()+range.second); } }; ///a word contains a few discrete traces, may not be continuous to ///represent by 2 index. But 2 word may not contain same trace. i.e ///common way of writing, but 2 or more character may contain same trace //(like cursive writing) struct word{ index_t index; trace_index_range get_traces(){ return index_range<trace_buffer>(traces,index); } }; A few additional things do happen, like each container keeps track of how many elements had been removed, to translate properly from index to iterator. So there are 3 library I am searching, 1) Index -> iterator , and iterator -> index conversion (I know that 2 famous facts in STL that iterator doesn't know container and their position, but that is only applicable for pointers . There is no harm to know this facts from iterator. and thus some library can do to-from conversion between iterator & index position , or better sub_range & pair<index_t,index_t> any library ? 2) a library like index_range, which hops over a container (random access preferably ) adding an user specified offset to the iterator position 3) an utility which allows to refer a portion (or some portions ) of a container to be stored ( i.e store by index & return by iterator ) inside another class , using the above two library .... and sorry for being late, I was out of station for last 2 days ... any help or suggestion is appreciated ... -- Abir Basak, Member IEEE B. Tech, IIT Kharagpur email: abir@abirbasak.com homepage: www.abirbasak.com
abir basak wrote:
It is better if I try to post some code to show what I exactly trying to do. ( I am trying to capture digital pen input and create a hierarchical structure from it ) ///This is a range (2 point index, which can create 2 iterators with the ///help of the container, I am using boost::sub_range for that ) typedef std::pair<std::size_t,std::size_t> range_t;
///This is a multi index range allows iterate over a few specific index ///on a container , used with my index_range and container. (for ///simplicity now it uses vector, it can be any container ) typedef std::vector<size_t> index_t;
///The index range. iterates over the specific position on the container ///a simplified version to show the concept. It has const correctness ///and all other functions that sub_range has. It takes container & ///index vector unlike iterators in boost::sub_range. template<typename C> class index_range{ public: typedef C container_type; typedef typename C::iterator iterator; typedef typename C::reference reference; typedef typename C::pointer pointer; typedef typename C::size_type size_type; private: index_t index_; C& c_; size_type pos_; public: index_range(C& c,index_t index) : c_(c),index_(index) , pos_(0){} size_type size()const { return index_.size();} reference operator[](size_type pos) { return c_[ index_[pos] ] }; reference front() { return c_[index_[0] ] ;} reference back() { return c_[index_[size()-1]] ; } reference operator++(){ return c_[index_ [ pos_ ++] ] ; } }; ///The point comes as user input through digital pen struct point{ int x; int y; point(int _x,int _y) : x(_x),y(_y){} }; typedef std::deque<point> point_buffer; typedef boost::sub_range<point_buffer> point_range;
///The buffer of points. point_buffer points;
///trace a continuous user writing, until pen up. points a portion ///of point_buffer struct trace{ range_t range; point_range get_points() { return boost::make_iterator_range(points.begin()+range.first,points.begin()+range.second); } };
typedef std::deque<trace> trace_buffer; typedef boost::sub_range<trace_buffer> trace_range; typedef index_range<trace_buffer> trace_index_range; ///buffer for traces. trace_buffer traces;
///a page contains a set of traces. struct page{ range_t range; trace_range get_traces(){ return boost::make_iterator_range(traces.begin()+range.first,traces.begin()+range.second); } };
///a word contains a few discrete traces, may not be continuous to ///represent by 2 index. But 2 word may not contain same trace. i.e ///common way of writing, but 2 or more character may contain same trace //(like cursive writing) struct word{ index_t index; trace_index_range get_traces(){ return index_range<trace_buffer>(traces,index); } }; A few additional things do happen, like each container keeps track of how many elements had been removed, to translate properly from index to iterator.
So there are 3 library I am searching, 1) Index -> iterator , and iterator -> index conversion (I know that 2 famous facts in STL that iterator doesn't know container and their position, but that is only applicable for pointers . There is no harm to know this facts from iterator. and thus some library can do to-from conversion between iterator & index position , or better sub_range & pair<index_t,index_t> any library ?
Boost has 'counting_iterator'. http://www.boost.org/libs/iterator/doc/counting_iterator.html You can call 'counting_iterator::base()' if you want the 'index'.
2) a library like index_range, which hops over a container (random access preferably ) adding an user specified offset to the iterator position
Boost has 'permutation_iterator'. http://www.boost.org/libs/iterator/doc/permutation_iterator.html Unfortunately, 'boost::permutation_iterator' cannot work with 'boost::counting_iterator', hence requires a patch something like this.. http://tinyurl.com/35qkzw
3) an utility which allows to refer a portion (or some portions ) of a container to be stored ( i.e store by index & return by iterator ) inside another class , using the above two library ....
If you take the portions represented by different types into a single deque, Dr.Becker's 'any_iterator' is a candidate. http://thbecker.net/free_software_utilities/type_erasure_for_cpp_iterators/s... Well, you have to make a range by using these iterators, because Boost doesn't have the range wrappers yet. It would be something like this.. http://tinyurl.com/38474e Finally, I've written everything noted above. :-) http://tinyurl.com/2o2mnv Regards, -- Shunsuke Sogame
shunsuke wrote:
So there are 3 library I am searching, 1) Index -> iterator , and iterator -> index conversion (I know that 2 famous facts in STL that iterator doesn't know container and their position, but that is only applicable for pointers . There is no harm to know this facts from iterator. and thus some library can do to-from conversion between iterator & index position , or better sub_range & pair<index_t,index_t> any library ?
Boost has 'counting_iterator'. http://www.boost.org/libs/iterator/doc/counting_iterator.html You can call 'counting_iterator::base()' if you want the 'index'.
2) a library like index_range, which hops over a container (random access preferably ) adding an user specified offset to the iterator position
Boost has 'permutation_iterator'. http://www.boost.org/libs/iterator/doc/permutation_iterator.html Unfortunately, 'boost::permutation_iterator' cannot work with 'boost::counting_iterator', hence requires a patch something like this.. http://tinyurl.com/35qkzw This one fits my need, thus I will replace my code by
3) an utility which allows to refer a portion (or some portions ) of a container to be stored ( i.e store by index & return by iterator ) inside another class , using the above two library ....
If you take the portions represented by different types into a single deque, Dr.Becker's 'any_iterator' is a candidate. http://thbecker.net/free_software_utilities/type_erasure_for_cpp_iterators/s... At present I don't need a polymorphic or heterogeneous iterator. I am looking at it. And also looking at some iterator adapter (or range ) which can be stored inside a class or another container. i.e it will perform all of
Here I am not getting the "index" from counting_iterator. std::vector<int> v; v+= 1,2,3,4,5,6,7,8,9,10; std::for_each(v.begin(),v.end(),std::cout<<_1<<" "); counting_iterator<std::vector<int>::iterator > it_b = make_counting_iterator(v.begin()+3); std::cout<<*it_b.base(); /// This prints the element at that pos i.e 4, not the position, i.e 3 . How to get the index back from iterator ? permutation_iterator. the operations using index & a reference to the container internally. Thus it needs to know the container & the position in the container. can any_iterator or some other be stored (or boost::sub_range of those iterator adapter) inside a class , or I need to store index and construct iterator with the help of container.
Well, you have to make a range by using these iterators, because Boost doesn't have the range wrappers yet. It would be something like this.. http://tinyurl.com/38474e
This is ok. I will be happy to use it.
Finally, I've written everything noted above. :-) http://tinyurl.com/2o2mnv
Still looking at them. Will get an idea within a day.
Regards,
Thanks for specifying the links, and sorry for disturbing. abir -- Abir Basak, Member IEEE B. Tech, IIT Kharagpur email: abir@abirbasak.com homepage: www.abirbasak.com
abir basak wrote:
shunsuke wrote:
So there are 3 library I am searching, 1) Index -> iterator , and iterator -> index conversion (I know that 2 famous facts in STL that iterator doesn't know container and their position, but that is only applicable for pointers . There is no harm to know this facts from iterator. and thus some library can do to-from conversion between iterator & index position , or better sub_range & pair<index_t,index_t> any library ? Boost has 'counting_iterator'. http://www.boost.org/libs/iterator/doc/counting_iterator.html You can call 'counting_iterator::base()' if you want the 'index'.
Here I am not getting the "index" from counting_iterator. std::vector<int> v; v+= 1,2,3,4,5,6,7,8,9,10; std::for_each(v.begin(),v.end(),std::cout<<_1<<" "); counting_iterator<std::vector<int>::iterator > it_b = make_counting_iterator(v.begin()+3); std::cout<<*it_b.base(); /// This prints the element at that pos i.e 4, not the position, i.e 3 . How to get the index back from iterator ?
Boost doens't have such iterator, AFAIK. You maybe need to write one from scratch, holding 'v.begin()' or something.
3) an utility which allows to refer a portion (or some portions ) of a container to be stored ( i.e store by index & return by iterator ) inside another class , using the above two library .... If you take the portions represented by different types into a single deque, Dr.Becker's 'any_iterator' is a candidate. http://thbecker.net/free_software_utilities/type_erasure_for_cpp_iterators/s... At present I don't need a polymorphic or heterogeneous iterator. I am looking at it.
You try to use an iterator through the "index". That is a polymorphism. :-)
And also looking at some iterator adapter (or range ) which can be stored inside a class or another container. i.e it will perform all of the operations using index & a reference to the container internally. Thus it needs to know the container & the position in the container. can any_iterator or some other be stored (or boost::sub_range of those iterator adapter) inside a class , or I need to store index and construct iterator with the help of container.
After all, the index seems to behave as the type erasure. 'any_iterator' is the most generic one to do it. (You may recall a battle of switch vs virtual.) On the other hand, it is difficult to implement 'any_iterator'. An iterator tracking its own index can be a reasonable solution. Regards, -- Shunsuke Sogame
participants (2)
-
abir basak -
shunsuke