c++ - 如何定义跳过逻辑删除的 C++ 迭代器

Question

我正在实现一个呈现类似 map 界面的容器。物理实现是一个 std::vector<std::pair<K*, T>> . K对象会记住其在 vector 中的指定位置。 K 是可能的要销毁的对象。在这种情况下，它记住的索引用于将其在 vector 中对应的键指针置零，从而创建一个墓碑。

我想公开完整的传统迭代器集合，尽管我认为它们只需要声明为 forward_iterator s(见下)。

我希望能够使用基于范围的 for 循环迭代来返回唯一的非逻辑删除元素。此外，我希望迭代器的实现是单个指针(即没有指向容器的后向指针)。

由于基于范围的 for 循环已经过预测试，我认为我可以在不等式谓词中实现逻辑删除。

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

这是一个合理的方法吗？如果是，有没有一种简单的方法可以覆盖 std::vector 的不等式运算符？的迭代器而不是从头开始实现我的迭代器？

如果这不是一个合理的方法，什么会更好？

Answer 1

Is this a reasonable approach?

没有。 (请记住，operator!= 可以在基于范围的 for 循环之外使用。)

• 您的运算符不接受 const 对象作为其第一个参数(即 const vector::iterator)。
• 如果第一个参数出现在第二个参数之后，您就有未定义的行为(例如，如果有人测试 end != cur 而不是 cur != end)。
• 你会遇到这种奇怪的情况，给定迭代器 a 和 b，*a 可能不同于 * b，但是如果你检查 (a != b) 那么你会发现迭代器相等，然后 *a 与 相同*b。这可能会破坏前向迭代器的多次保证(但情况很奇怪，我想在通过判断之前检查标准的精确措辞)。与人们的期望打交道是不可取的。
• 没有简单的方法来覆盖 std::vector 的迭代器的不等运算符。

---

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

您已经知道什么会更好。你只是在回避它。

• 从头开始实现您自己的迭代器。将 vector 包装在您自己的类中的好处是，只有该类的代码必须知道墓碑的存在。
  • 警告:记录创建逻辑删除的条件也会使该元素的迭代器无效。 (无效的迭代器被排除在大多数迭代器要求之外，例如多遍保证。)

或

• 虽然您的实现是一个糟糕的 operator!=，但它可能是一个很好的更新或检查功能。有一个鲜为人知的 secret ，即 C++ 具有比基于范围的 for 循环更多的循环结构。您可以使用其中之一，例如:
  for ( cur = vec.begin(); skip_tombstones(cur, vec.end());++cur ) {
auto& element = *cur;
  其中 skip_tombstones() 基本上是您的 operator!= 重命名。如果不需要太多代码来迭代 vector ，这可能是一个合理的选择，即使从长远来看也是如此。