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