How to define a C++ iterator that skips tombstones

Question

I am implementing a container that presents a map-like interface. The physicals implementation is an std::vector<std::pair<K*, T>>. A K object remembers its assigned position in the vector. It is possible for a K object to get destroyed. In that case its remembered index is used to zero out its corresponding key pointer within the vector, creating a tombstone.

I would like to expose the full traditional collection of iterators, though I think that they need only claim to be forward_iterators (see next).

I want to be able to use range-based for loop iteration to return the only non-tombstoned elements. Further, I would like the implementation of my iterators to be a single pointer (i.e. no back pointer to the container).

Since the range-based for loop is pretested I think that I can implement tombstone skipping within the inequality predicate.

bool operator != (MyInterator& cursor, MyIterator stop) {
    while (cursor != stop) {
        if (cursor->first)
            return true;
        ++cursor;
    }
    return false;
}

Is this a reasonable approach? If yes, is there a simple way for me to override the inequality operator of std::vector's iterators instead of implementing my iterators from scratch?

If this is not a reasonable approach, what would be better?

Answer 1

Is this a reasonable approach?

No. (Keep in mind that operator!= can be used outside a range-based for loop.)

• Your operator does not accept a const object as its first parameter (meaning a const vector::iterator).
• You have undefined behavior if the first parameter comes after the second (e.g. if someone tests end != cur instead of cur != end).
• You get this weird case where, given iterators a and b, it might be that *a is different than *b, but if you check if (a != b) then you find that the iterators are equal and then *a is the same as *b. This probably wrecks havoc with the multipass guarantee of forward iterators (but the situation is bizarre enough that I would want to check the standard's precise wording before passing judgement). Messing with people's expectations is inadvisable.
• There is no simple way to override the inequality operator of std::vector's iterators.

---

If this is not a reasonable approach, what would be better?

You already know what would be better. You're just shying away from it.

• Implement your own iterators from scratch. Wrapping your vector in your own class has the benefit that only the code for that class has to be aware that tombstones exist.
  • Caveat: Document that the conditions that create a tombstone also invalidate iterators to that element. (Invalid iterators are excluded from most iterator requirements, such as the multipass guarantee.)

OR

• While your implementation makes a poor operator!=, it could be a fine update or check function. There's this little-known secret that C++ has more looping structures than just range-based for loops. You could make use of one of these, for example:
  for ( cur = vec.begin(); skip_tombstones(cur, vec.end()); ++cur ) {
auto& element = *cur;
  where skip_tombstones() is basically your operator!= renamed. If not much code needs to iterate over the vector, this might be a reasonable option, even in the long term.