c++ - 如何实现符合标准的迭代器/容器？

Question

假设我有一个类似容器的抽象类，名为 RuleBook。 RuleBook 的用户希望能够对 RuleBook 进行前向迭代以获得 Rule。

与标准容器不同，这里的具体子类的内存布局没有限制。相反，由子类的实现者来遵守 RuleBook 的前向迭代要求，并根据自己的数据结构满足这一要求。

我认为 RuleBook 应该包含纯虚拟 begin() 和 end() 以便它可以与 range-基于，但我遇到了一些问题。

begin() 和 end() 的签名应该是什么？ BasketballRules 和 CompanyRules 应该如何实现？

当迭代器经过最后一项时，我们如何处理结束条件？

在下面的示例中，您可以假设 m_rp 和 m_rpp 各仅指向一个规则。我们想为胆量返回某种迭代器(如 Rule*)。我们还可以假设 Foo 的所有子类都将在各种数据结构中包含 Rule，这将取决于实现者的心血来潮。

如果我使用 Rule* 作为我的迭代器并使用 null_ptr 作为我的超越端点来实现整个事情，这是否符合 STL 标准？

我目前正在研究自定义迭代器，但我什至不确定这个问题是否适合该范例，因为每个子类都必须有效地定义迭代的核心。

代码

struct RuleBook
{
  // virtual Rule* begin() = 0;
  // virtual Rule* end() = 0; 
};

struct CompanyRules :
    public RuleBook
{
    Rule m_r;
};

struct BasketballRules :
    public RuleBook
{
    // return the three Rules, one-at-a-time, in succession
    Rule   m_r;
    Rule*  m_rp;
    Rule** m_rpp;
};

int
main( int argv, char* argc[] )
{
}

Answer 1

这很难做到正确。

What should the signatures be for begin() and end()?

没有太多选择，他们几乎必须是这样的

RuleBook::iterator begin();
RuleBook::iterator end();

(如果需要，添加 const 重载)

How should BasketballRules and CompanyRules be implemented?

小心 :)

How do we deal with the end condition when the iterator goes past the last item?

您正确设计了迭代器类型，因此它可以正常工作。您需要一个可以比较相等性并且可以递增的迭代器类型。当您有一个指向容器中最后一项的迭代器并递增它时，它必须等于尾后迭代器。

If I implement the entire thing using Rule* as my iterator and null_ptr as my beyond-the-endpoint, would this be STL compliant?

没有。如果您的迭代器类型只是 Rule*，那么递增迭代器不会移动到下一个 Rule，它只是指向内存中的下一个位置，甚至可能不是Rule 对象，导致未定义的行为。例如对于 BasketballRules 如果您将 Rule* 指向 m_r 并且您递增它，则您没有指向有效的 Rule您指向被 m_rp 占用的内存的对象，即 Rule* 并且取消引用它是未定义的行为。

此外，如果您不断递增 Rule*，您将永远无法到达最后的 nullptr 值。

我对 Yakk 的回答投了赞成票，因为它是一个看似合理的实现，但很难做到正确。有很多东西需要考虑并包含在多态接口(interface)中，例如如果您使用 == 比较两个 RuleBook::iterator 对象，其中一个指向 CompanyRules 和一个指向 会发生什么BasketballRules，多态迭代器的相等性如何工作？

如果将迭代器分配给 BasketballRules 对象，将迭代器分配给 CompanyRules 对象，会发生什么情况？您需要多态类型的“深拷贝”。

您需要为每个容器派生不同的迭代器实现类型，CompanyRule 容器的迭代器类型需要了解有关 CompanyRule 类型的所有信息，等等对于每个派生容器类型。这些具体的迭代器实现类型中的每一个都需要将几乎整个迭代器接口(interface)实现为虚函数。实现起来困难表明设计有问题。

一个更简单的设计是让每个派生容器类型管理一个相同类型的实际物理容器。特定于每个派生容器的代码包括只要派生对象的内容发生变化就更新列表的内容。迭代器类型然后是直接的和非多态的，例如

struct RuleBook
{
  typedef std::vector<Rule*> list_type;
  typedef list_type::iterator iterator;

  virtual iterator begin() = 0;
  virtual iterator end() = 0;
};

struct CompanyRules :
    public RuleBook
{
    CompanyRules() : m_list{ &m_r } { }
    Rule m_r;

    iterator begin() { return m_list.begin(); }
    iterator end() { return m_list.end(); }

private:
    list_type m_list;
};

struct BasketballRules :
    public RuleBook
{
    BaseketballRules() : m_list{ &m_r, m_rp, *m_rpp } { }

    // return the three Rules, one-at-a-time, in succession
    Rule   m_r;
    Rule*  m_rp;
    Rule** m_rpp;

    iterator begin() { return m_list.begin(); }
    iterator end() { return m_list.end(); }

private:
    // N.B.
    // must update m_list[1] any time m_rp changes
    // must update m_list[2] any time the pointee of m_rpp changes (harder!)
    list_type m_list;
};