must iterator be bound to owner/source?

Discussion in 'C++' started by homsan toft, May 27, 2006.

  1. homsan toft

    homsan toft Guest

    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
    homsan toft, May 27, 2006
    #1
    1. Advertising

  2. On 2006-05-28 00:55, homsan toft wrote:
    > 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
    --
    "I have always wished for my computer to be as easy to use as my
    telephone; my wish has come true because I can no longer figure
    out how to use my telephone" -- Bjarne Stroustrup
    =?windows-1252?Q?Erik_Wikstr=F6m?=, May 28, 2006
    #2
    1. Advertising

  3. homsan toft

    homsan toft Guest

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

    Erik Wikström wrote:
    > On 2006-05-28 00:55, homsan toft wrote:
    >
    >> I have a deque-like container that I want to give segmented iterators.


    >> 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?


    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...)

    >> 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?


    ....

    > 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
    homsan toft, May 29, 2006
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. =?Utf-8?B?TXJNaWtl?=

    DataGrid must be Bound before Editing

    =?Utf-8?B?TXJNaWtl?=, Mar 10, 2005, in forum: ASP .Net
    Replies:
    1
    Views:
    335
    Elton Wang
    Mar 10, 2005
  2. sunil panda

    Lower bound & Upper bound

    sunil panda, Dec 25, 2003, in forum: Java
    Replies:
    9
    Views:
    7,192
    thushara wijeratna
    Oct 7, 2008
  3. Rhiner Dan
    Replies:
    1
    Views:
    731
    Mike Wahler
    Mar 27, 2005
  4. Mario Krsnic
    Replies:
    0
    Views:
    361
    Mario Krsnic
    Jun 23, 2006
  5. Phillip Vong
    Replies:
    0
    Views:
    401
    Phillip Vong
    Jul 27, 2006
Loading...

Share This Page