Re: circular iterators
werasm wrote:
Hi all,
I recently had a problem where I found that writing an iterator adaptor
that would wrap (to the beginning) when incremented to the end, would
make my solution more efficient (instead of rotating) and copying into
a new sequence. Something like this:
CircularIter& operator++()
{ // preincrement
myIter_.operator++(); //Call underlying preincrement
if( myIter_ == mySeq_.end() )
{
myIter_ = mySeq.begin();
}
return (*this);
}
This would have allowed me to, for example, do the following (this
applies for more than one container type, but for now I'll use list).
typedef std::pair<float, float> AngleWeightPair;
typedef std::list< AngleWeightPair > AngleWeightPairLst;
Items in the list are sorted according to angle (degrees) in ascending
order. Now I would want search from a minimum angle, clockwise (so to
speak) to a maximum angle (excluding all other angles) for the position
representing the smalles weight. Something like below:
float getMinWeight( float angleIn )
{
static const float halfSearchWindow( 23.f );
//TrimToRange returns a value from 0-360 degrees
const float minAngle( TrimToRange( angleIn-halfSearchWindow ) );
ClosestMatch minAngleMatch(
for_each( angleSeq_.begin(), angleSeq_.end(),
ClosestMatch(angleSeq_, minAngle) ) );
const float maxAngle( TrimToRange( angleIn+halfSearchWindow ) );
ClosestMatch maxAngleMatch(
for_each( angleSeq_.begin(), angleSeq_.end(),
ClosestMatch(angleSeq_, maxAngle) ) );
//[1] NOTE!!!! minAngleMatch may represent 359?, and maxAngleMatch
30?.
return for_each( minAngleMatch.pos(), maxAngleMatch.pos(),
FindMinWeight() ).get();
}
The functor ClosestMatch always stores a valid iterator representing
the position which differs from the incoming angle the least.
FindMinWeight stores the value of the weight (second item) that is the
least in the range.
Now my observation:
[1] This won't work, as we don't know whether minAngleMatch.pos is in
actual fact before or after maxAngleMatch.pos - we could have known
this if we had random access iterators, but this would cause tedious
code - if min after max, copy from min to end, then from begin to
max...
If we had an iterator that was allowed to increment passed the end
(terminating upon reaching itself only - considering itself as the end
of the range), we would have breezed through this excersize. Now we
need to, in the case of using a list as container, perform rotation and
all kinds of funny exercises to solve this problem.
- Are there iterator concepts modelling this kind of iterator? I can
see some disadvantages, such as algorithms storing and incrementing a
valid bidirectional iterator, expecting the algorithm to end when it
reaches the end - therefore we would need a specialised container.
- Are there C++ containers modelling this concept (of not having an end
- circular)?
- Are they considering this kind of concept for standards to come? If
not, why not etc. :-)
I once put some effort into designing a circular list container. My
design goals were to meet the standard's applicable iterator and
container requirements, and to match the design of std::list as closely
as possible, while retaining circularity. You could iterate around the
circle as many times as you wished. It turned out to be quite feasible,
but I ran into one key issue: it had the property that begin() was
always equal to end(). The standard says that if a container is
empty,then begin()==end(). I haven't been able to find any place where
it says the converse: that if begin()==end(), then the container is
empty. Therefore, as far as the container requirements are concerned,
that's not a problem.
To be honest, I should mention that Valentin Bonnard claims that the
standard implies the converse in many different locations, but failed
to identify those locations. See
<http://groups.google.com/group/comp.std.c++/tree/browse_frm/thread/1c7a494914ced167/771d644a04c9b50c?rnum=1&hl=en&_done=%2Fgroup%2Fcomp.std.c%2B%2B%2Fbrowse_frm%2Fthread%2F1c7a494914ced167%2F56a324c579f07b13%3Flnk%3Dst%26q%3D%26rnum%3D1%26hl%3Den%26#doc_010c40a1a45b074c>
However, as a practical matter virtually every algorithm ever written
to take an iterator range assumes that [i,j) defines an empty range if
i==j. I figured out a way around that problem, by using a heavy
iterator. That iterator would contain a reference named 'parent' to the
container it came from, and a signed integer called winding_number. A
function named equal() compares two iterators based solely on what
element of the list they point at; operator==(i,j) is overloaded to
evaluate equal(i,j) && i.winding_number == j.winding_number.
Each time one of these iterators was iterated through the point where
equal(&self,parent.begin()) in the forward direction, it would
increment winding_number ; each time it was iterated past that point in
the reverse direction, it would decrement winding_number. end()
returned an iterator identical to begin(), except that if the circular
list was non-empty, end().winding_number==1, while
begin().winding_number==0.
This design violates the requirement that i==j if and only if *i and *j
refer to the same object. However, as a practical matter, that should
not be a problem so long as you never pass an iterator range to an
algorithm that winds more than one full time around the circular list.
I've never tested this design - I've never even fully implemented it;
but it should work. As I remember it, there were some tricky details
when defining splice(), though I don't remember what they were.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]