2

Suppose I have an abstract container-like class called RuleBook. Users of RuleBook expect to be able to forward-iterate over the RuleBook to obtain Rules.

Unlike standard containers, there will be no restrictions on the memory layout of the the concrete subclasses here. Instead, it is up to the implementers of the subclasses to comply with the forward-iteration requirement of RuleBook and satisfy this requirement based on its own data structures.

I am thinking that RuleBook should contain pure virtual begin() and end() so it would work with range-based for, but I am running into a few problems.

What should the signatures be for begin() and end()? How should BasketballRules and CompanyRules be implemented?

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

In the example below, you can assume that m_rp and m_rpp only point to one Rule each. We want to return some kind of iterator for the guts (like a Rule*). We can also assume that all subclasses of Foo will contain Rule in various data structures, which will be up to the whim of the implementor.

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

I am currently looking into custom iterators, but I'm not even sure this problem fits well with that paradigm because each subclass must effectively define the guts of the iteration.

CODE

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[] )
{
}
4

4 回答 4

2

这将很难做到正确。

begin() 和 end() 的签名应该是什么？

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

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

（如果需要，添加const重载）

BasketballRules 和 CompanyRules 应该如何执行？

小心:)

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

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

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

不。如果您的迭代器类型只是Rule*在递增迭代器时不会移动到下一个Rule，它只是指向内存中的下一个位置，它甚至可能不是一个Rule对象，从而导致未定义的行为。例如，BasketballRules如果您Rule*指向m_r并递增它，您并没有指向一个有效的Rule对象，您指向的是由m_rpie a占用的内存，Rule*并且取消引用它是未定义的行为。

此外，如果您不断增加 a ，Rule*您将永远无法达到最终nullptr值。

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

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

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

更简单的设计是为每个派生容器类型管理相同类型的实际物理容器。特定于每个派生容器的代码只包括在派生对象的内容更改时更新列表的内容。迭代器类型是直接且非多态的，例如

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;
};
于 2012-12-30T13:20:41.797 回答
1

Boost 有一些迭代器帮助模板类——crtp，需要你实现一些方法。它们的pImpl基于用户将允许您的迭代器的合规和虚拟行为。即，pImpl是一个纯虚拟抽象类，迭代器将其工作委托给它。

编写一个纯虚拟pImpl迭代器。那是beginand的返回类型end。子类使用具体pImpl实例创建迭代器的实例，为数据的存储方式自定义编写。

于 2012-12-30T12:09:34.397 回答
1

确切的签名并不重要，因为基于范围的 for 循环是根据使用的表达式定义的。如果找到begin或end成员函数，则将它们称为__range.begin()和__range.end()。签名无关紧要的一个示例是，这些成员函数可以具有任意数量和类型的参数，只要它们可以像.begin()and一样调用.end()（这意味着参数必须具有默认值）。

如果类型没有begin和end成员函数，则使用表达式begin(__range)和end(__range)。（其中使用您在 range-for-loop 中使用的表达式__range进行auto &&__range初始化）。因此，只要依赖于参数的查找有效，确切的签名就很重要。

BasketballRules 和 CompanyRules 应该如何执行？

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

这些是与 range-base-for-loops 如何工作不同的问题。您应该专门询问有关这些的其他问题。

但是如果你使用指针作为你的迭代器，那么使用nullptr作为结束迭代器是不合适的，因为递增最后一个有效指针不会给你一个空指针；它会给你一个超过范围末尾的指针。此外，如果您Rule*用作迭代器，那么您不会将实现留给容器类；容器必须维护一个连续的规则数组。

于 2012-12-30T09:07:53.413 回答
0

也许您可以尝试类似 Alex Alllain 在他的关于基于范围的 for 循环的教程中解释的方式。它还有一个示例，用于制作可通过基于范围的 for 循环迭代的数据结构

需要的东西是

  1. 一个 .begin() 和一个 .end() 方法。它们也可以是独立的。
  2. operator!= 、 ++ 和 * 重载，以便支持需要执行的迭代器操作。
于 2012-12-30T09:37:44.643 回答