Default constructed random access iteratators

[Kristoffer Vinther]

Hi,

I need to store of parts of containers. The interface to the store could
look something like this (the code in this post serves as illustrations,
it is not meant to be 100% correct):

template<class RanIt>
class substreams
{
public:
void add(RanIt begin, RanIt end);
};

and used like this:

std::vector<int> vector(20);
substreams<std::vector<int>::iterator> streams;
//...
streams.add(vector.begin(), vector.begin()+5);
streams.add(vector.begin()+5, vector.begin()+10);
streams.add(vector.begin()+15, vector.end());

where I'm adding parts of a vector to the store (streams).

Now, I know add() will be called at most k times, so I would like to
implement it like this:

template<class RanIt>
class substreams
{
std:air<RanIt,RanIt>* parts_begin;
std:air<RanIt,RanIt>* parts_end;
std:air<RanIt,RanIt>* parts_last;
public:
substreams(size_t k)
: parts_begin(new std:air<RanIt,RanIt>[k]),
parts_end(parts_begin),
parts_last(parts_begin+k) { }
virtual ~substreams()
{
delete[] parts_begin;
}

void add(RanIt begin, RanIt end)
{
*parts_end++ = std::make_pair(begin, end);
}
};

Suppose I want to count the total number of elements in the container
parts added. I could do something like this:

size_t size() const
{
size_t total = 0;
for( std:air<RanIt,RanIt>* it=parts_begin;
it!=parts_last; ++it )
total += (it->second-it->first);
return total;
}

(strictly, I guess I should use typename
std::iterator_traits<RanIt>::difference_type instead of size_t). Now you
are thinking why not stop at it==parts_end? Let me just say the real
problem is not computing the size(), but something less trivial than a
for(...), so I would like to avoid involving parts_last. And that's the
problem:

Will the size() function as implemented above (using parts_last) always
work, even if add() has not been called k times (for the vector example,
size() should return 15 for all k>3)?
IIRC, the standard specifically takes care of the case where RanIt is a
pointer by requiring a default constructed pointer to be NULL, thereby
guaranteeing new std:air<RanIt,RanIt>[k] evaluates to an array of
pairs of NULL pointers, in turn guaranteeing (it->second-it->first) is
zero for the pairs between parts_end and parts_last (those not added).
Correct me if I'm wrong.

But what if RanIt is not a pointer? As far as I can see the standard
only requires random access iterators to be default constructable but
states nothing about the semantics of such an iterator, specifically
nowhere that

template<class RanIt>
size_t diff()
{
RanIt b();
RanIt e();
return e-b;
}

should always return 0, or equivalently

template<class RanIt>
bool empty()
{
RanIt b();
RanIt e();
return e == b;
}

always returning true. Have I just missed something, or should I rethink
my implementation?

Thanks for your input,
Kristoffer Vinther

 

[Ron Natalie]

But what if RanIt is not a pointer? As far as I can see the standard
only requires random access iterators to be default constructable but
states nothing about the semantics of such an iterator, specifically
nowhere that

template<class RanIt>
size_t diff()
{
RanIt b();
RanIt e();
return e-b;
}

should always return 0, or equivalently

template<class RanIt>
bool empty()
{
RanIt b();
RanIt e();
return e == b;
}

always returning true. Have I just missed something, or should I rethink
my implementation?

You haven't missed anything. While the standard requires default
construction of an iterator to be legal, the use of that default
constructed value is undefined behavior. It neither compares to
0 or NULL nor deterministicly to any other object (including other
default constructed iterators).