C++抽象类与嵌套类。派生类和嵌套类。

Question

我有一个任务，需要编写自己的容器Linked_list和Array_list。我为它们设计了一个接口：

typedef int value_type;
class Container 
{
public:
        class Iterator 
        {   
        public:
            Iterator();
            Iterator(value_type* other);
            Iterator(const Iterator& other);
            Iterator& operator=(const Iterator& other);
                    ...
        };

    Container();
    Container(const Container& other);
    ~Container();   

    virtual value_type& front() const=0;
    virtual value_type& back() const=0;
    virtual Iterator begin() const=0; // 
    ...
};

我创建了派生类 Linked_list 和 Array_list:

class Linked_list:public Container 
{
public:
    long int cur_size;
    List elem;
    static Link end_;
    class Iterator: public Container::Iterator
    {
        friend Linked_list;
        Link *p;    
    };

    Iterator begin() const; //overriding virtual function return type differs ...

...
}

我认为这完全是错的。嵌套类Linked_list::Iterator应该是一个派生类吗？如果我不能改变接口，这可行吗？

- greensher

---

你可以更改 typedef int value_type; 吗？这样你就可以通过将其更改为 template <class value_type> 并将派生类更改为模板的特定类型来使其成为一个模板。 - DjSol

你为什么认为这一切都是错的？你组织类的方式似乎很有道理。 - jogojapan

我不能改变这个。而且我必须在不使用模板的情况下完成它。对我的英语表示抱歉。 - greensher

在我看来，这似乎是正确的，但我不明白为什么你要在Linked_list::Iterator中有一个Linked_list和Link。 - Lucia Pasarin

Linked_list 中 begin 的覆盖无效，因为返回类型不同且也不能作为协变返回类型接受（需要是指针才行）。 - Bart van Ingen Schenau

你有检查过 std::forward_list 和 std::array 吗？ - user90843

Answer 1

考虑到您的设计限制，即不能使用模板，那么应该添加接口IteratorImpl。这样，您可以将class Iterator从基类class Container非虚拟化。它需要是非虚拟的，因为类似STL的迭代器应具有值语义。请参见pimpl习惯用法，了解更多详细信息！

typedef int value_type;
class Container 
{
    protected:
        class IteratorImpl
        {   
        public:
            virtual void next() = 0;
            virtual IteratorImpl* clone() const = 0;
            virtual value_type get() const = 0;
            virtual bool isEqual(const IteratorImpl& other) const = 0;
        };

    public:
        class Iterator 
        {   
        public:
            Iterator(IteratorImpl* impl) : impl(impl) {}
            ~Iterator() { delete impl; }
            Iterator(const Iterator& other) : impl(other.impl->clone()) {}
            Iterator& operator=(const Iterator& other) {
              IteratorImpl* oldImpl = impl;
              impl = other.impl->clone();
              delete oldImpl;
            }
            bool operator == (const Iterator& other) const 
            {
               return impl->isEqual(*other->impl);
            }
            Iterator& operator ++ ()
            {
                impl->next();
                return *this;
            }
            value_type& operator*() const 
            {
               return impl->get();
            }
            value_type* operator->() const
            {
               return &impl->get();
            }
        };
        Container();
        Container(const Container& other);
        ~Container();   

    virtual value_type& front() const=0;
    virtual value_type& back() const=0;
    virtual Iterator begin() const=0; // 
    ...
    };

然后在您的派生类中实现IteratorImpl：

class Linked_list:public Container 
{
protected:
    class IteratorImpl: public Container::IteratorImpl
    {
       ....
    };

public:
    Iterator begin() const { return new IteratorImpl(firstNode); }
    Iterator end() const { return new IteratorImpl(nodeAfterLastNode); }

...
};

这里的firstNode和nodeAfterLastNode只是我猜测的，使用任何你需要来实现IteratorImpl接口...

- PiotrNycz

---

虚拟 IteratorImpl* clone() const = 0; - greensher

@PiotrNycz - 我可以问一个愚蠢的问题吗：像 Linked_list::Iterator Linked_list::erase(Iterator pos) 这样的函数应该怎么处理？ - greensher

@greensher 有两种方法：1）在迭代器类中添加公共方法getImpl() - 将此实现动态转换为您的List实现 - 然后您应该能够找到要删除的节点。 - PiotrNycz

@ greensher 或者在 IteratorImpl 中添加虚拟方法 erase - 但是您需要在 IteratorImpl 特化中引用您的容器，或将此容器传递给方法 erase() - 然后在此方法中将容器 dynamic_cast 到其派生版本（List 或 Array） - PiotrNycz

@greensher 或使用双重派发模式 - 有关详细信息，请提出另一个问题（您可以将此问题作为参考），我或其他人可以在答案中为您提供更多详细信息。 - PiotrNycz

Answer 2

你应该定义一个const_value_type来表示常量value_type，并将其用于front和back虚拟方法的返回值。或者你可以放弃这些方法上的const限定符，因为在const方法上有非const引用返回类型是没有意义的。

如果没有更多关于类的细节，那么就很难判断。你也可以看一下STL的早期实现：这是一个很好的获取这些主题的见解的方法。

- didierc