Re: Containers that don't materialise the elements
On 05.11.2010 10:05, David Barrett-Lennard wrote:
Let class IntervalList represent an ordered sequence of non-empty,
mutually exclusive half open intervals expressed in integer
I would like to use this to implement a class IntervalSet that can
typically be used in place of a std::set<int>, and it certain
applications may offer better performance. Since an IntervalSet
doesn't materialise the actual elements of the set one could expect
problems similar to the vector<bool> specialisation which doesn't meet
the requirements of a standard library container.
std::set<T> doesn't support iterators that allow the elements to be
modified. Therefore I thought it should be reasonable to write a
const_iterator and const_reverse_iterator for IntervalSet where
operator* returns an int by value, and operator-> isn't defined. Is
Yes, it looks very reasonable to me. Given an iterator value 'it', the expression
is defined, if and only if the expression
would be a valid expression. The latter requirement does already exist in the
current C++03 standard for input iterators.
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,
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. For C++0x, iterators won't have the ideal separation, but the Library
does support non-reference types for the result of
operator* of some iterators - currently this is only guaranteed to be true for
input iterators, though. In this case, the type of *it must be convertible to
the value type, which is satisfied for your type (even though it is actually
more than an input iterator).
There is currently work in progress that will give a "normative encouragement"
to implementations that vector<bool> iterators work like random-access iterators
in the library, see
I consider it as one of the main targets of the next revision of the Standard
Library to introduce a better separation between traversal and access for the
iterator requirements. I hope, this can be realized as soon as possible.
HTH & Greetings from Bremen,
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]