On Nov 6, 6:19 am, Daniel Kr?gler<daniel.krueg...@googlemail.com>
wrote:
On 05.11.2010 10:05, David Barrett-Lennard wrote:
It seems I cannot use the iterator adapter std::reverse_iterator<> to
define the const_reverse_iterator because it assumes operator* returns
a reference to a materialised element. I'm curious to know whether
this should be regarded only as a limitation of the adapter or the
premise behind a set container that doesn't materialise its elements.
I would say that there is a very fundamental limitation, but that limitation is
due to the current iterator requirements, which don't cleanly separate traversal
and access. If we use the nomenclature from Boost,
http://www.boost.org/doc/libs/1_44_0/libs/iterator/doc/iterator_conce...
your iterators would allow for bidirectional traversal, but no lvalue access.
Most implementations are able to handle such types. I think,
it should also work for reverse_iterator, if you specialize std::iterator_traits
for your iterator such that it defines the type 'reference' to be int. At least
according to the semantics of
reverse_iterator's overload reference operator*() const it should do the Right
Thing.
I tried that and it works nicely, thanks.
Just to give you a hint, that this approach is not that unusual, you may notice
that std::istreambuf_iterator in the recent working draft does do the same thing
This same example raises another question...
Let's consider an abstract value type to be associated with what
mathematicians call an abstract algebra consisting of a set (of
values) plus pure functional operators on those elements.
As an abstract value type, consider that an IntervalList has the
constraint that the intervals are non-empty and any two intervals are
separated by a non-empty gap. This constraint implies there is a
bijection (i.e. one to one and onto mapping) between the abstract
value types for IntervalSet and IntervalList.
From a programmer's perspective this means that an IntervalSet has a
unique representation as an IntervalList so they can share the same
physical implementation and that includes operator==. The IntervalSet
is implemented in terms of IntervalList, and doesn't add any
additional state, nor does it tighten the class invariant.
Nevertheless they represent distinct abstract value types. For
example, IntervalList::size() returns the cardinality of a set of
intervals whereas IntervalSet::size() returns the cardinality of a set
of integers. Also IntervalList::const_iterator iterates over a set of
intervals, whereas IntervalSet::const_iterator iterates over a set of
integers.
Given the bijection between these abstract value types, it follows
that it's quite reasonable to be able to convert between them. This
must not involve an implicit conversion because neither abstract type
could be regarded as a subset of the other. Putting it another way,
it makes no sense to equate a set of intervals with a set of
integers. This contrasts with the example of Square value is-a
Rectangle value, and therefore supporting implicit conversion from
Square value to Rectangle value by writing a single argument
constructor on class Rectangle taking a Square value.
With reasonable assumptions on the compiler this *explicit* conversion
can be achieved with zero overhead with a reinterpret_cast between
IntervalList& and IntervalSet& at the implementation level. This
appears to be very useful (see below). But is it reasonable, and can
it be coded in a way that guarantees it will work on any conforming C+
+ compiler?
Although the standard library provides set_intersection, set_union and
set_difference which could be used directly on an IntervalSet (using
std::inserter<> to implement an output iterator), some client may want
to provide more efficient set-theoretic functions that take advantage
of the ordered half open intervals. A client can do this simply by
reinterpreting an IntervalSet& as an IntervalList& and vice versa
within the implementation. For example:
// Calculate set-theoretic intersection of x and y.
// Efficient to return by value assuming RVO
IntervalSet Intersection(const IntervalSet& x, const IntervalSet& y)
{
IntervalList result;
const IntervalList& x_ = reinterpret_cast<const IntervalList&>(x);
const IntervalList& y_ = reinterpret_cast<const IntervalList&>(y);
< Iterate through intervals in x_, y_
and insert intersections of intervals into result>
return reinterpret_cast<IntervalSet&>(result);
}
From your description it is unclear to me what you specifically mean with "The
IntervalSet is implemented in terms of IntervalList". Is the reinterpret_cast
Without further data available I would say that your example probably runs into
undefined behaviour because of the type aliasing. I don't think that it is
necessary to go this route of reinterpreting memory. You could make IntervalList
for example. "Programming of Elements" suggests a similar approach and refers to
[ comp.lang.c++.moderated. First time posters: Do this! ]