Check Whether Iterator Belongs to a List

Check whether iterator belongs to a list

The obvious but invalid approach

You can't simply iterate through the list, comparing each iterator value to your "candidate".

The C++03 Standard is vague about the validity of == applied to iterators from different containers (Mankarse's comment on Nawaz's answer links http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2948.html#446), some compilers (eg. VC++2005 debug mode) warn if you do so, but despite all that it may actually work reliably depending on your compiler/libraries - check its documentation if you don't care about portability.

The C++11 Standard is very explicit, you can't compare iterators to different containers:

§ 24.2.5 The domain of == for forward iterators is that of iterators over the same underlying sequence.

So, the answers to this question that rely on operator== are questionable now, and invalid in future.

An oft-valid approach

What you can do is iterate along the list, comparing the address of the elements (i.e. &*i) to the address of the object to which your other iterate points.

• Mankarse's comment cautions that this might not work as intended for objects providing their own operator&. You could work around this using std::addressof, or for C++03 boost's version

• Martin's comment mentions that you have to assume the candidate iterator that you're testing list membership for is safely dereferenceable - i.e. not equal to an end() iterator on the container from which it came. As Steve points out - that's a pretty reasonable precondition and shouldn't surprise anyone.

(This is fine for all Standard containers as stored elements never have the same address, but more generally user-defined containers could allow non-equal iterators to address the same value object (e.g. supporting cycles or a "flyweight pattern" style optimisation), in which case this approach would fail. Still, if you write such a container you're probably in a position to design for safe iterator comparison.)

Implementation:

template <class IteratorA, class IteratorB, class IteratorC>
inline bool range_contains(IteratorA from, const IteratorB& end,
                           const IteratorC& candidate)
{
    while (from != end)
        if (&*from++ == &*candidate)
            return true;
    return false;
}

Notes:

• This adopts the Standard library approach of accepting a range of iterator positions to search.
• The types of each iterator are allowed to vary, as there are portability issues, e.g. containers where begin() returns an iterator but end() returns a const_iterator.
• Iterators other than from are taken by const reference, as iterators can sometimes be non-trivial objects (i.e. too large to fit in a register, relatively expensive to copy). from is needed by value as it will be incremented through the range.

Checking if an iterator references an item in a list

if (it!=collection.end()) std::cout << "Iterator points to data" << std::endl;
else                      std::cout << "Iterator does not point to data" << std::endl;

How to find out whether iterator lies in a range?

Random access iterators are comparable. Just do it1 < it3 && it2 > it3 - if they belong to the same collection.

You get random access iterators on collections that support O(1) indexing, such as vector, deque, and array.

edit: Checking if an interator belongs to a given collection is not obviously feasible, and this should be a whole different question. See this question for more details. (tl;dr: you can't.)

check which vector an iterator belongs to

The easiest option would be to not pass these iterators by value, so when you modify minit, whichever of a, b or c was chosen also changes.

bool itLess(std::vector<int>::iterator& l, std::vector<int>::iterator& r)
{
    return *l < *r;
}

for (
    auto a = A.begin(), b = B.begin(), c = C.begin(); 
    a != A.end() && b != B.end() && c != C.end();
    )
{
    auto [minit, maxit] = std::minmax({std::ref(a), std::ref(b), std::ref(c)}, itLess);
    // use minit.get() and maxit.get()
}

See it on coliru

Finding the owner of an STL iterator

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

Checking if an iterator is valid

I assume you mean "is an iterator valid," that it hasn't been invalidated due to changes to the container (e.g., inserting/erasing to/from a vector). In that case, no, you cannot determine if an iterator is (safely) dereferencable.

---

Related Topics