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 optimisation 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 initialised with a vector and an iterator pointing into the vector. It would be cute and convenient if I could initialise 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 there owner, then it would be impossible for them to be optimized down to a light weight pointer (which can be done with containers guaranteeing contiguous storage like vectors and such).

Answer 2

I don't believe there's an exposed method to do that. The reason being, that's not the purpose of the iterator. There is, of course, no technical reason that an iterator could not hold a pointer to its parent container. Even if it is implemented in such a way that does not require that pointer, it could still hold it.

Iterators are intended to iterate over the collection, and as such, they provide the interface necessary to do that and only that. This is good object-oriented programming principles.

May I ask what your use-case is, that you need to know the "range" of the container with an iterator?

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.

Answer 5

The STL does not allow for this.

Vecor iterators, for example, may be implemented simply as a pointer. And there is no general way to retrieve an object from a pointer pointing to some data the object has allocated.

Answer 6

As suggested earlier it is best to rewrite your code so that you don't need this behavior. It is the same as holding a coin, but you have no idea where it comes from unless you noted that down on a paper.

If you are unable to rewrite the code you could still introduce a wrapping object that contains a pointer to the container and the iterator itself. What do you need this for specifically?

Answer 7

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.