iterators

This is a discussion on iterators within the C++ Programming forums, part of the General Programming Boards category; iterators of which containers are "invariant" to what they point to upon insertion/deletion? so far i found out that: vector<>::iterator ...

  1. #1
    Registered User
    Join Date
    Aug 2001
    Posts
    244

    iterators

    iterators of which containers are "invariant" to what they point to upon insertion/deletion?

    so far i found out that:
    vector<>::iterator always points to the same entry in the vector.
    thus if you have an iterator pointing to vector.begin(); and insert a new element to the beginning of the vector, the iterator will point to the new element
    reason: vector is a linear piece of memory (array), and the iterator always points to the same location in that array. thus insertion requires shifting elements to the right.

    list:
    if you have an iterator pointing to list.begin() and you insert a new element to the beginning, the iterator will still point to the old element
    reason: list is a linked list. iterator points to some element in the list, and linked list elements' location in memory doesnt change as long as it exists (thus the location of the data is invariant upon indel (insertion/deletion)

    what about map and set?
    i know they use red/black tree structures for organizing their data.
    but if i have an iterator to some element and keep indeling elements, does this iterator still point to the correct entry?

    of course im not talking about erasing some iterator and useing it after that. of course that causes undefined behaviour.
    signature under construction

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,344
    Actually, in all cases, if the iterator has not been invalidated, then it will point to the old element. In the case of the vector, insertion invalidates all iterators, so you cannot count on the iterator pointing to any location. What you should do is focus on which container methods invalidate iterators and which do not. If the method has not invalidated the iterator, then it is pointing at the old element.

  3. #3
    Registered User
    Join Date
    Jan 2005
    Posts
    7,344
    My above response was not fully correct. According to the standard, calling insert on a vector only invalidates iterators if the vector requires a reallocation (the new size is greater than the old capacity). So if you reserve enough space prior to calling insert, your iterator will not be invalidated. I did not find any indication of whether the iterator must point to the original element or the element that exists at that location after the insert.

    It makes sense to allow the implementers to leave the iterator pointing to the same location in the underlying array, since vector iterators are often implemented as a pointer or something similar. This would cause the behavior you saw, so your reasoning was correct.

    So in response to your actual question about map and set, I believe that it does continue to point to the original entry, but I cannot find a guarantee for that in the standard.

    Sorry for the confusion.

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >i know they use red/black tree structures for organizing their data.
    A red-black tree is one possible implementation, but it doesn't have to be done that way, and assuming so could cause you problems.

    >does this iterator still point to the correct entry?
    Yes.

    >but I cannot find a guarantee for that in the standard.
    Section 23.1.2, Associative Containers, paragraph 8:
    The insert members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to the erased elements.
    My best code is written with the delete key.

  5. #5
    Registered User
    Join Date
    Jan 2005
    Posts
    7,344
    > Section 23.1.2, Associative Containers, paragraph 8
    I actually saw that, however I don't think the definition of "valid" means that the iterator must point to the same element. There is a similar guarantee of "validity" for vectors, but the iterator does not point at the same element after the insert, it points at the same location.

    I am guessing/hoping this will be clarified in the next standard if it hasn't been already.

  6. #6
    Registered User
    Join Date
    Aug 2001
    Posts
    244
    well i did a test run with map of inserting a random number of entries, then randomly pick an iterator to some entry, and keep erasing and inserting new elements.
    after that the randomly picked iterator still pointed to the same element.
    (of course i made sure that iterator wasent erased)
    i guess the reason is, that a tree structure is used, so each node in the tree has its own memory location (like the linked list), thus erasing elements doesnt cause other iterators to point to something else.
    signature under construction

  7. #7
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >I don't think the definition of "valid" means that the iterator must point to the same element
    Correct, the validity of an iterator, taking into account the vague description in the standard, basically means that the iterator refers to an element in a valid range. But in this case, I think it's safe to assume that "valid" also means that the iterator refers to the same place that it referred to before the operation.

    Granted, it's a non-portable assumption, but I have trouble imagining a situation where a conforming implementation of the associative containers would fail to do the expected thing.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. vector of strings with iterators.
    By Mario F. in forum C++ Programming
    Replies: 6
    Last Post: 05-31-2006, 01:12 PM
  2. Using reverse iterators in algorithms
    By 0rion in forum C++ Programming
    Replies: 1
    Last Post: 02-27-2006, 03:19 AM
  3. Writing Iterators...
    By DeepBlackMagic in forum C++ Programming
    Replies: 6
    Last Post: 05-29-2003, 10:31 PM
  4. accessing vector elements: iterators are faster?
    By Captain Penguin in forum C++ Programming
    Replies: 1
    Last Post: 11-28-2002, 02:27 PM
  5. Generic Progpammimg Iterators
    By rip1968 in forum C++ Programming
    Replies: 7
    Last Post: 08-06-2002, 11:20 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21