Checking if an iterator is valid

Question

Is there any way to check if an iterator (whether it is from a vector, a list, a deque...) is (still) dereferenceable, i.e. has not been invalidated?

I have been using try-catch, but is there a more direct way to do this?

Example: (which doesn't work)

list<int> l;
for (i = 1; i<10; i++) {
    l.push_back(i * 10);
}

itd = l.begin();
itd++;
if (something) {
    l.erase(itd);
}

/* now, in other place.. check if it points to somewhere meaningful */
if (itd != l.end())
{
    //  blablabla
}

Answer 1

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.

Answer 2

As jdehaan said, if the iterator wasn't invalidated and points into a container, you can check by comparing it to container.end().

Note, however, that if the iterator is singular -- because it wasn't initialized or it became invalid after a mutating operation on the container (vector's iterators are invalidated when you increase the vector's capacity, for example) -- the only operation that you are allowed to perform on it is assignment. In other words, you can't check whether an iterator is singular or not.

std::vector<int>::iterator iter = vec.begin();
vec.resize(vec.capacity() + 1);
// iter is now singular, you may only perform assignment on it,
// there is no way in general to determine whether it is singular or not

Answer 3

Non-portable answer: Yes - in Visual Studio

Visual Studio's STL iterators have a "debugging" mode which do exactly this. You wouldn't want to enable this in ship builds (there is overhead) but useful in checked builds.

Read about it on VC10 here (this system can and in fact does change every release, so find the docs specific to your version).

Edit Also, I should add: debug iterators in visual studio are designed to immediately explode when you use them (instead undefined behavior); not to allow "querying" of their state.

Answer 4

Usually you test it by checking if it is different from the end(), like

if (it != container.end())
{
   // then dereference
}

Moreover using exception handling for replacing logic is bad in terms of design and performance. Your question is very good and it is definitively worth a replacement in your code. Exception handling like the names says shall only be used for rare unexpected issues.

Answer 5

Is there any way to check if a iterator (whether it is from a vector, a list, a deque...) is (still) dereferencable, i.e has not been invalidated ?

No, there isn't. Instead you need to control access to the container while your iterator exists, for example:

• Your thread should not modify the container (invalidating the iterator) while it is still using an instantiated iterator for that container

• If there's a risk that other threads might modify the container while your thread is iterating, then in order to make this scenario thread-safe your thread must acquire some kind of lock on the container (so that it prevents other threads from modifying the container while it's using an iterator)

Work-arounds like catching an exception won't work.

This is a specific instance of the more general problem, "can I test/detect whether a pointer is valid?", the answer to which is typically "no, you can't test for it: instead you have to manage all memory allocations and deletions in order to know whether any given pointer is still valid".

Answer 6

Trying and catching is not safe, you will not, or at least seldom throw if your iterator is "out of bounds".

what alemjerus say, an iterator can always be dereferenced. No matter what uglyness lies beneath. It is quite possible to iterate into other areas of memory and write to other areas that might keep other objects. I have been looking at code, watching variables change for no particular reason. That is a bug that is really hard to detect.

Also it is wise to remember that inserting and removing elements might potentially invalidate all references, pointers and iterators.

My best advice would be to keep you iterators under control, and always keep an "end" iterator at hand to be able to test if you are at the "end of the line" so to speak.

Answer 7

Is there any way to check if an iterator is dereferencable

Yes, with gcc debugging containers available as GNU extensions. For std::list you can use __gnu_debug::list instead. The following code will abort as soon as invalid iterator is attempted to be used. As debugging containers impose extra overhead they are intended only when debugging.

#include <debug/list>

int main() {
  __gnu_debug::list<int> l;
  for (int i = 1; i < 10; i++) {
    l.push_back(i * 10);
  }

  auto itd = l.begin();
  itd++;
  l.erase(itd);

  /* now, in other place.. check if itd points to somewhere meaningful */
  if (itd != l.end()) {
    //  blablabla
  }
}

$ ./a.out 
/usr/include/c++/7/debug/safe_iterator.h:552:
Error: attempt to compare a singular iterator to a past-the-end iterator.

Objects involved in the operation:
    iterator "lhs" @ 0x0x7ffda4c57fc0 {
      type = __gnu_debug::_Safe_iterator<std::_List_iterator<int>, std::__debug::list<int, std::allocator<int> > > (mutable iterator);
      state = singular;
      references sequence with type 'std::__debug::list<int, std::allocator<int> >' @ 0x0x7ffda4c57ff0
    }
    iterator "rhs" @ 0x0x7ffda4c580c0 {
      type = __gnu_debug::_Safe_iterator<std::_List_iterator<int>, std::__debug::list<int, std::allocator<int> > > (mutable iterator);
      state = past-the-end;
      references sequence with type 'std::__debug::list<int, std::allocator<int> >' @ 0x0x7ffda4c57ff0
    }
Aborted (core dumped)

Answer 8

In some of the STL containers, the current iterator becomes invalid when you erase the current value of the iterator. This happens because the erase operation changes the internal memory structure of the container and increment operator on existing iterator points to an undefined locations.

When you do the following, iterator is incementented before it is passed to erase function.

if (something) l.erase(itd++);

Answer 9

The type of the parameters of the erase function of any std container (as you have listed in your question, i.e. whether it is from a vector, a list, a deque...) is always iterator of this container only.

This function uses the first given iterator to exclude from the container the element that this iterator points at and even those that follow. Some containers erase only one element for one iterator, and some other containers erase all elements followed by one iterator (including the element pointed by this iterator) to the end of the container. If the erase function receives two iterators, then the two elements, pointed by each iterator, are erased from the container and all the rest between them are erased from the container as well, but the point is that every iterator that is passed to the erase function of any std container becomes invalid! Also:

Each iterator that was pointing at some element that has been erased from the container becomes invalid, but it doesn't pass the end of the container!

This means that an iterator that was pointing at some element that has been erased from the container cannot be compared to container.end(). This iterator is invalid, and so it is not dereferencable, i.e. you cannot use neither the * nor -> operators, it is also not incrementable, i.e. you cannot use the ++ operator, and it is also not decrementable, i.e. you cannot use the -- operator.

It is also not comparable!!! I.E. you cannot even use neither == nor != operators

Actually you cannot use any operator that is declared and defined in the std iterator. You cannot do anything with this iterator, like null pointer.

Doing something with an invalid iterator immediately stops the program and even causes the program to crash and an assertion dialog window appears. There is no way to continue program no matter what options you choose, what buttons you click. You just can terminate the program and the process by clicking the Abort button.

You don't do anything else with an invalid iterator, unless you can either set it to the begin of the container, or just ignore it.

But before you decide what to do with an iterator, first you must know if this iterator is either invalid or not, if you call the erase function of the container you are using.

I have made by myself a function that checks, tests, knows and returns true whether a given iterator is either invalid or not. You can use the memcpy function to get the state of any object, item, structure, class and etc, and of course we always use the memset function at first to either clear or empty a new buffer, structure, class or any object or item:

bool IsNull(list<int>::iterator& i) //In your example, you have used list<int>, but if your container is not list, then you have to change this parameter to the type of the container you are using, if it is either a vector or deque, and also the type of the element inside the container if necessary.
{
    byte buffer[sizeof(i)];
    memset(buffer, 0, sizeof(i));
    memcpy(buffer, &i, sizeof(i));
    return *buffer == 0; //I found that the size of any iterator is 12 bytes long. I also found that if the first byte of the iterator that I copy to the buffer is zero, then the iterator is invalid. Otherwise it is valid. I like to call invalid iterators also as "null iterators".
}

I have already tested this function before I posted it there and found that this function is working for me.

I very hope that I have fully answered your question and also helped you very much!

Answer 10

There is a way, but is ugly... you can use the std::distance function

  #include <algorithms>
  using namespace std
  auto distance_to_iter = distance(container.begin(), your_iter);
  auto distance_to_end = distance(container.begin(),container.end());
  
  bool is_your_iter_still_valid = distance_to_iter != distance_to_end;

Answer 11

Try this:

auto itd = l.begin();
//decrement the iterator
if (itd != l.end() && distance(l.begin(), itd) > 0 )
{
    advance(itd, -1);
}

advance(itd, 1);
if (itd != l.end() && distance(l.begin(), itd) > 0)
{
    advance(itd, -1);
}
//increment the iterator
itd = l.end();
if (itd != l.end() && distance( itd, l.end()) >1)
{
    advance(itd, 1);
}

advance(itd, -1);
if (itd != l.end() && distance(itd, l.end()) > 1)
{
    advance(itd, 1);
}

Answer 12

use erase with increment :

   if (something) l.erase(itd++);

so you can test the validity of the iterator.

Answer 13

if (iterator != container.end()) {
   iterator is dereferencable !
}

If your iterator doesnt equal container.end(), and is not dereferencable, youre doing something wrong.