8

I will ask the question first and the motivation next, and finally an illustrative code sample which compiles and executes as expected.

Question

If I can assure myself that an iterator will not get invalidated in the duration when I will be needing to use it, is it safe to hold a pointer to an iterator (e.g. a pointer to a list<int>::iterator).

Motivation

I have multiple containers and I need direct cross references from items held in one container to the corresponding items held in another container and so on. An item in one container might not always have a corresponding item in another container.

My idea thus is to store a pointer to an iterator to an element in container #2 in the element stored in container #1 and so forth. Why? Because once I have an iterator, I can not only access the element in container #2, but if needed, I can also erase the element in container #2 etc.

If there is a corresponding element in container #2, I will store a pointer to the iterator in the element in container #1. Else, this pointer will be set to NULL. Now I can quickly check that if the pointer to the iterator is NULL, there is no corresponding element in container #2, if non-NULL, I can go ahead and access it.

So, is it safe to store pointers to iterators in this fashion?

Code sample

#include <iostream>
#include <list>

using namespace std;

typedef list<int> MyContainer;
typedef MyContainer::iterator MyIterator;
typdef MyIterator * PMyIterator;

void useIter(PMyIterator pIter)
{
    if (pIter == NULL)
    {
    cout << "NULL" << endl;
    }
    else
    {
    cout << "Value: " << *(*pIter) << endl;
    }
}

int main()
{
    MyContainer myList;

    myList.push_back(1);
    myList.push_back(2);

    PMyIterator pIter = NULL;

    // Verify for NULL
    useIter(pIter);

    // Get an iterator
    MyIterator it = myList.begin();

    // Get a pointer to the iterator
    pIter = & it;

    // Use the pointer
    useIter (pIter);
}
Community
  • 1
  • 1
kman
  • 107
  • 1
  • 8
  • 2
    why not just save iterators, with `end` iterator meaning `NULL` –  Dec 20 '12 at 12:10
  • Alternatively there's Boost.Optional, which is a general purpose way to say "either a value or else a special-case with no value". Because everything is handled in one place, you don't have to think about the lifetime of the referand of your pointer. – Steve Jessop Dec 20 '12 at 12:24
  • Saving a pointer (I hope) gives me two things: 1. Light weight 2. No need to worry about end() itself getting invalidated. Now I will admit I am not certain if these concerns are valid. – kman Dec 20 '12 at 12:35
  • Thanks @SteveJessop, learned something new today. I tried Boost Optional with `optional` and it works fine. – kman Dec 21 '12 at 05:22

5 Answers5

13

Iterators are generally handled by value. For instance, begin() and end() will return an instance of type iterator (for the given iterator type), not iterator& so they return copies of a value every time.

You can of course take an address to this copy but you cannot expect that a new call to begin() or end() will return an object with the same address, and the address is only valid as long as you hold on to the iterator object yourself.

std::vector<int> x { 1, 2, 3 };

// This is fine:
auto it = x.begin();
auto* pi = &it;

// This is not (dangling pointer):
auto* pi2 = &x.begin();

It rarely makes sense to maintain pointers to iterators: iterators are already lightweight handles to data. A further indirection is usually a sign of poor design. In your example in particular the pointers make no sense. Just pass a normal iterator.

Konrad Rudolph
  • 530,221
  • 131
  • 937
  • 1,214
  • Thank you, very well explained, and understood. I cannot up-vote as I don't have the required "reputation". – kman Dec 20 '12 at 12:31
2

The problem with iterators is that there are a lot of operations on containers which invalidate them (which one depend on the container in question). When you hold an iterator to a container which belongs to another class, you never know when such an operation occurs and there is no easy way to find out that the iterator is now invalid.

Also, deleting elements directly which are in a container which belongs to another class, is a violation of the encapsulation principle. When you want to delete data of another class, you should better call a public method of that class which then deletes the data.

Philipp
  • 67,764
  • 9
  • 118
  • 153
  • What you say has no direct bearing on pointers and if it were true then iterators would generally be pretty useless – which is luckily not the case. – Konrad Rudolph Dec 20 '12 at 12:13
1

Yes, it is safe, as long as you can ensure the iterators don't get invalidated and don't go out of scope.

NPE
  • 486,780
  • 108
  • 951
  • 1,012
1

Sounds scary. The iterator is an object, if it leaves scope, your pointer is invalid. If you erase an object in container #2, all iterators may become invalid (depending on the container) and thus your pointers become useless.

Why don't you store the iterator itself? For the elements in container #1 that don't refer to anything, store container2.end(). This is fine as long as iterators are not invalidated. If they are, you need to re-generate the mapping.

Tannin
  • 488
  • 5
  • 11
  • One of my concerns is to avoid worrying about end() iterator changing or getting invalidated. I am not certain if this is a valid concern. – kman Dec 20 '12 at 12:39
  • If you're worried about that, you have to be worried about all iterators getting invalidated then you can't store them (or pointers to them). The end() iterator should be valid at least as long as all other iterators to the same container. – Tannin Dec 20 '12 at 13:14
  • You are right, and I agree. While avoiding splitting hair, I was looking for a "constant" sentinel value for end() which will always offer an unchanging target for checking, however reading about this (for instance [http://stackoverflow.com/questions/6440392/end-iterator-invalidation-rules]), it seems like in certain cases, the items being manipulated, and the end iterator could get invalidated. The manipulated items are fine, as I know what I am manipulating, however the end() seems to be be a bit of a confusion to me. – kman Dec 21 '12 at 05:28
1

Yes it is possible to work on pointers to iterators like it is to other types but in your example it is not necessary since you can simple pass the pass the original iterator as reference.

In general it is not a good idea to store iterators since the iterator may become invalid as you modify the container. Better store the containers and create iterators as you need them.

Davidiusdadi
  • 511
  • 1
  • 7
  • 14