Finding the owner of an STL iterator

Question

Is there any way that I can find the container pointed to by an iterator? Specifically, I want to be able to find the std::vector pointed to by a particular std::vector::iterator so that I can check the range, without having to actually pass references to that vector around.

If (as I suspect) the answer is no, why not?

edit: thanks for a number of quick and (largely) accurate answers. Evan Teran nails it. I wasn't thinking about optimization at all, but it's obvious now.

A couple of people asked what I want to do this for. It's nothing terribly important. I have an object which is initialized with a vector and an iterator pointing into the vector. It would be cute and convenient if I could initialize the object just with an iterator because then I could convert vector::iterators directly to this object (this sounds strange but does make sense in the particular case). But it's not crucial at all.

Answer 1

I don't believe so. If iterators had to keep a reference/pointer to their owning container, then it would be impossible for them to be optimized down to a lightweight pointer (which can be done with containers guaranteeing contiguous storage like vectors and such).

Answer 2

There is no way to make that work. The reason is simple: Adding a way to the iterators to get the container to which they are pointing is

• Pointless. Iterators iterate over a collection. As other said, only that, nothing more.
• Not compatible with the iterator requirements. Remember a pointer is a random access iterator. Putting a container pointer into the iterator would be of no use for algorithms, since they intend to be generic, decoupled from specific iterator implementations. A pointer used as an iterator can't have a pointer back to the array it was taken from as a member.

You say you need it for range checking. You can provide an end iterator which points one after the last valid iterator position of a range. Check whether your current position is not at the end. That is all you need to do for range checking.

Answer 3

You cannot retrieve the container from an iterator in a general way. As an example of why, a plain pointer can be used as an iterator:

#include <algorithm>
#include <cstdio>
#include <cstring>

int
main(int argc, char *argv[])
{
        const char s[] = "Hello, world!";
        const char *begin = s;
        const char *end = s + strlen(s);

        std::for_each(begin, end, putchar);

        return 0;
}

How could you retrieve the original string from a pointer (if it isn't pointed at the beginning of the string)?

However, if you need this functionality then you could always implement your own wrapper around the iterator that stores a reference to the container.

Answer 4

In theory there's a way if the iterator in question is at least a forward iterator. You can check whether your iterator is one of the iterators in [first,last) for each candidate container. Since you're using a vector container, you have a random access iterator, you can use the less-than operator to do this check quickly.

You DO have to know all of the candidate vectors against which to check up front, and this is not a general way to get the container to which an iterator belongs.

You can, however, define an extension of random access iterators by decorating random access iterator with something containing a pointer to the creating vector. This is likely to be slightly inelegant, inefficient, and inconvenient. So see if you can rewrite code to avoid this need first.