must iterator be bound to owner/source?

[homsan toft]

I have a deque-like container that I want to give segmented iterators.
The implementation uses pool allocation where iterators use indices instead of pointers.
The standard iterator type has a reference to the pool and an index.
The local_iterator type, which is used within a pool range, just needs
an index to operate.
But this means that a local iterator from one container instance
could be used as iterator to another. Does this by itself invalidate
my design?

Eg, it means operator== can only test the index, it can't detect container instance.
So it could claim that two iterators from different containers are identical.
Is this immoral? Do I have to add more data to the local_iterator to make it better behaved?

Thanks

homsan

 

[=?windows-1252?Q?Erik_Wikstr=F6m?=]

I have a deque-like container that I want to give segmented iterators.
The implementation uses pool allocation where iterators use indices instead of pointers.
The standard iterator type has a reference to the pool and an index.
The local_iterator type, which is used within a pool range, just needs
an index to operate.
But this means that a local iterator from one container instance
could be used as iterator to another. Does this by itself invalidate
my design?

Eg, it means operator== can only test the index, it can't detect container instance.
So it could claim that two iterators from different containers are identical.
Is this immoral? Do I have to add more data to the local_iterator to make it better behaved?

In my draft of the standard it says that for forward iterators the
following must hold:

— If a and b are equal, then either a and b are both dereferenceable or
else neither is dereferenceable.

— If a and b are both dereferenceable, then a == b if and only if *a and
*b are the same object.

Note that bidirectional iterators and random access iterators both
fulfill the requirements of forward iterators.

Should you not be able to add a test in your operator== so that if the
indexes are equal then you test so that *it1 == *it2?

Erik Wikström

 

[homsan toft]

I misthought about the operator== example, maybe part of the problem remains:

DequeLike a, b;
// ... fill a, b

DequeLike::iterator ia = a.begin();
DequeLike::iterator ib = b.begin();

// Use faster segemented iterator to a section of the container
while (ia != a.end() && ib != b.end()) {
DequeLike::local_iterator pa = a.local_begin(ia);
DequeLike::local_iterator pb = b.local_begin(ib);
// various operations here
ia = pa; // pa == a.local_end(ia) is true, so ia will find next segment
ib = pb; // ditto
}

// "various operations" includes programmer error
if (pa == pb)
// ...

(perhaps he meant: if (*pa == *pb) ... )

I would like the test pa==pb to be blocked by design somehow!

Is it enough that the test is always false?
I'd *want* to stop here and signal that it's a mistake.
Of course nothing in the type system could help - even if pa and pb
were iterators from different vector<int>'s, the test would be legal code.

So perhaps I can only assert in debug build, and leave the release less safe?
(Meaning the debug-build local_iterators have an extra member,
say a pointer to the owner, and assert on this in all comparisons)


(oh, now a voice is trying to command me to use the SafeSTL iterator wrappers anyway...
uuuhhg, have to look at it I guess...)

....

Should you not be able to add a test in your operator== so that if the
indexes are equal then you test so that *it1 == *it2?

Duh. Right. I confused myself trying to think about both
operator== when the object is eg an int, and of
operator< when I have a pointer to X.

Erik Wikström

Thanks for your answer!
(I use the C++0x draft standard, but it's hard to fit all pieces together)

homsan