3

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?

Evg
  • 25,259
  • 5
  • 41
  • 83
John Yates
  • 1,027
  • 1
  • 7
  • 18
  • Make's no sense to me. What does where the iterator stops in a range based loop have to do with skipping tombstones? I think you should just implement an iterator that does skip tombstones, and then everything else just falls into place. – john Sep 10 '22 at 17:25
  • I'm not sure you need a custom iterator. If your only goal is to skip elements satisfying some property, then I think you're looking for [`filter`](https://en.cppreference.com/w/cpp/ranges/filter_view). – Silvio Mayolo Sep 10 '22 at 17:39
  • 1
    Don't adjust in the comparison operator. `operator++` is where you should move the iterator to the next non-tombstone item. And, no, you can't override parts of std::vector's iterators; you have to write your own from scratch. It's not hard to do. Each iterator can hold a `std::vector::iterator` (not your own pointer) and operate appropriately on that. – Pete Becker Sep 10 '22 at 18:10
  • @SilvioMayolo My goal is to provide a more efficient, drop-in replacement for an expensive, elaborate framework in which - rare but real - object destruction deletes elements from maps. My users expect to iterate over these map (using range-based for) and retrieve only live mapping. This idiom is widely used in our codebase. Clients would not happily accept needing to introduce `filter`, or more likely, adding their own check for a null key after debugging a `SEGV`. Bottom line: if it is not a drop-in replacement then my effort will have failed. It would likely get rejected during review. – John Yates Sep 11 '22 at 10:54
  • @PeteBecker I understand the intuitive expectation that comparison is side-effect-free while `operator++` is not. That said, I cannot see how to implement a single pointer iterator that skips tombstone within `operator++`. The skipping loop needs access to both the cursor and end iterators. Comparison is the only point where that occurs. – John Yates Sep 11 '22 at 11:03

1 Answers1

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.
JaMiT
  • 14,422
  • 4
  • 15
  • 31