16

玩弄过这个我怀疑这是不可能的,但我想我会问专家。我有以下 C++ 代码:

I类接口
{
    虚拟 void SomeMethod() = 0;
};

类对象
{
    IInterface* GetInterface() { ... }
};

类容器
{
私人的:
    结构项目
    {
        对象* pObject;
        [... 其他成员 ...]
    };
    std::list<项目> m_items;
};

我想将这些方法添加到容器中:

    MagicIterator<IInterface*> Begin();
    MagicIterator<IInterface*> End();

为了调用者可以写:

容器 c = [...]
for (MagicIterator<IInterface*> i = c.Begin(); i != c.End(); i++)
{
    IInterface* pItf = *i;
    [...]
}

所以本质上我想提供一个类,它似乎在迭代 IInterface 指针的某些集合(不允许 Begin() 和 End() 的调用者看到),但实际上是在迭代指向其他指针的集合可以转换为 IInterface 指针的对象(专用于 Container 类)。

几个关键点:

  • MagicIterator是要在外面定义的Container
  • Container::Item必须保持私密。
  • MagicIterator必须迭代IInterface指针,尽管事实上Container持有一个std::list<Container::Item>. Container::Item包含一个Object*, 并且Object可以用来获取IInterface*.
  • MagicIterator必须可与多个类似于 Container 的类重用,但可能在内部具有不同的列表实现,其中包含不同的对象 ( std::vector<SomeOtherItem>, mylist<YetAnotherItem>),并且IInterface*每次都以不同的方式获得。
  • MagicIterator不应该包含特定于容器的代码,尽管它可以委托给这样做的类,前提是这种委托没有硬编码到内部的特定容器MagicIterator(例如,编译器会以某种方式自动解析)。
  • 该解决方案必须在 Visual C++ 下编译,而不使用其他库(例如 boost),这需要其作者的许可协议。
  • 此外,迭代可能不会分配任何堆内存(因此没有new()malloc()在任何阶段),并且没有memcpy().

感谢您的宝贵时间,即使您只是在阅读;这个真的一直困扰着我!

更新:虽然我得到了一些非常有趣的答案,但还没有一个满足上述所有要求。值得注意的是,棘手的领域是 i) 以某种方式将 MagicIterator 与 Container 分离(默认模板参数不会削减它),以及 ii) 避免堆分配;但我真的在寻求涵盖所有上述项目符号的解决方案。

4

7 回答 7

15

我认为您在这里有两个不同的问题:

首先,创建一个迭代器,它将IInterface*从您的list<Container::Item>. 这很容易做到boost::iterator_adaptor

class cont_iter
  : public boost::iterator_adaptor<
        cont_iter                       // Derived
      , std::list<Container::Item>::iterator // Base
      , IInterface*                     // Value
      , boost::forward_traversal_tag    // CategoryOrTraversal
      , IInterface*                     // Reference :)
    >
{
 public:
    cont_iter()
      : cont_iter::iterator_adaptor_() {}

    explicit cont_iter(const cont_iter::iterator_adaptor_::base_type& p)
      : cont_iter::iterator_adaptor_(p) {}

 private:
    friend class boost::iterator_core_access;
    IInterface* dereference() { return this->base()->pObject->GetInterface(); }
};

您可以将此类型创建为 inner inContainer并从其begin()end()方法返回 in。

其次,您需要 runtime-polymorphic MagicIterator。这正是这样any_iterator做的。MagicIterator<IInterface*>is just ,any_iterator<IInterface*, boost::forward_traversal_tag, IInterface*>并且cont_iter可以分配给它。

于 2009-01-23T09:38:43.957 回答
4

创建一个抽象IteratorImplementation类:

template<typename T>
class IteratorImplementation
{
    public:
        virtual ~IteratorImplementation() = 0;

        virtual T &operator*() = 0;
        virtual const T &operator*() const = 0;

        virtual Iterator<T> &operator++() = 0;
        virtual Iterator<T> &operator--() = 0;
};

还有一个Iterator围绕它的类:

template<typename T>
class Iterator
{
    public:
        Iterator(IteratorImplementation<T> * = 0);
        ~Iterator();

        T &operator*();
        const T &operator*() const;

        Iterator<T> &operator++();
        Iterator<T> &operator--();

    private:
        IteratorImplementation<T> *i;
}

Iterator::Iterator(IteratorImplementation<T> *impl) :
    i(impl)
{
}

Iterator::~Iterator()
{
    delete i;
}

T &Iterator::operator*()
{
    if(!impl)
    {
        // Throw exception if you please.
        return;
    }

    return (*impl)();
}

// etc.

(您可以在IteratorImplementation“内部”创建一个类Iterator以保持整洁。)

在您的类中,返回一个具有自定义子类的Container实例:IteratorIteratorImplementationctor

class ObjectContainer
{
    public:
        void insert(Object *o);
        // ...

        Iterator<Object *> begin();
        Iterator<Object *> end();

    private:
        class CustomIteratorImplementation :
            public IteratorImplementation<Object *>
        {
            public:
                // Re-implement stuff here.
        }
};

Iterator<Object *> ObjectContainer::begin()
{
    CustomIteratorImplementation *impl = new CustomIteratorImplementation();  // Wish we had C++0x's "var" here.  ;P

    return Iterator<Object *>(impl);
}
于 2009-01-22T22:00:25.460 回答
4

听起来不太复杂。您可以在外部定义迭代器。您还可以使用 typedef。我认为这样的东西会适合。请注意,如果 MagicIterator不是免费模板,而是 Item 的成员,可能会在 Container 中进行类型定义,这样会更简洁。就像现在一样,其中有一个循环引用,这使得编写一些丑陋的解决方法代码变得很有必要。

namespace detail {
    template<typename T, typename U>
    struct constify;

    template<typename T, typename U>
    struct constify<T*, U*> {
        typedef T * type;
    };

    template<typename T, typename U>
    struct constify<T*, U const*> {
        typedef T const * type;
    };
}

template<typename DstType, 
         typename Container,
         typename InputIterator>
struct MagicIterator;

class Container
{
private:
    struct Item
    {
        Object* pObject;
    };

    std::list<Item> m_items;

public:

    // required by every Container for the iterator
    typedef std::list<Item> iterator;
    typedef std::list<Item> const_iterator;

    // convenience declarations
    typedef MagicIterator< IInterface*, Container, iterator > 
        item_iterator;
    typedef MagicIterator< IInterface*, Container, const_iterator > 
        const_item_iterator;

    item_iterator Begin();
    item_iterator End();
};

template<typename DstType, 
         typename Container = Container,
         typename InputIterator = typename Container::iterator>
struct MagicIterator : 
    // pick either const T or T, depending on whether it's a const_iterator.
    std::iterator<std::input_iterator_tag, 
                  typename detail::constify<
                           DstType, 
                           typename InputIterator::value_type*>::type> {
    typedef std::iterator<std::input_iterator_tag, 
                 typename detail::constify<
                          DstType, 
                          typename InputIterator::value_type*>::type> base;
    MagicIterator():wrapped() { }
    explicit MagicIterator(InputIterator const& it):wrapped(it) { }
    MagicIterator(MagicIterator const& that):wrapped(that.wrapped) { }

    typename base::value_type operator*() {
        return (*wrapped).pObject->GetInterface();
    }

    MagicIterator& operator++() {
        ++wrapped;
        return *this;
    }

    MagicIterator operator++(int) {
        MagicIterator it(*this);
        wrapped++;
        return it;
    }

    bool operator==(MagicIterator const& it) const {
        return it.wrapped == wrapped;
    }

    bool operator!=(MagicIterator const& it) const {
        return !(*this == it);
    }

    InputIterator wrapped;
};

// now that the iterator adepter is defined, we can define Begin and End
inline Container::item_iterator Container::Begin() {
    return item_iterator(m_items.begin());
}

inline Container::item_iterator Container::End() {
    return item_iterator(m_items.end());
}

现在,开始使用它:

for(MagicIterator<IInterface*> it = c.Begin(); it != c.End(); ++it) {
    // ...
}

您还可以使用 boost 提供的迭代器 mixin,其工作方式类似于 boost::function_output_iterator 的输入版本。它调用您的迭代器operator(),然后返回适当的值,按照我们operator*的原则执行上述操作。你在random/detail/iterator_mixin.hpp. 这可能会导致更少的代码。但它也需要我们绞尽脑汁来确保朋友的东西,因为 Item 是私有的,并且迭代器没有在 Item 中定义。无论如何,祝你好运:)

于 2009-01-22T22:19:22.767 回答
2

它实际上取决于, 因为和Container的返回值是实现定义的。c.Begin()c.End()

如果Container已知可能的 s列表,则MagicIterator可以使用包装类。

template<typename T>
class MagicIterator
{
    public:
        MagicIterator(std::vector<T>::const_iterator i)
        {
            vector_const_iterator = i;
        }

        // Reimplement similarly for more types.
        MagicIterator(std::vector<T>::iterator i);
        MagicIterator(std::list<T>::const_iterator i);
        MagicIterator(std::list<T>::iterator i);

        // Reimplement operators here...

    private:
        std::vector<T>::const_iterator vector_const_iterator;
        std::vector<T>::iterator       vector_iterator;
        std::list<T>::const_iterator   list_const_iterator;
        std::list<T>::iterator         list_iterator;
};

简单的方法是使用接受Container's 类型的模板:

// C++0x
template<typename T>
class Iterator :
    public T::iterator
{
    using T::iterator::iterator;
};

for(Iterator<Container> i = c.begin(); i != c.end(); ++i)
{
    // ...
}

更多信息在这里。

于 2009-01-22T21:36:21.200 回答
1

我看不出你为什么不能完全按照你的规定来实现它……我错过了什么吗?

为了澄清,您需要在 Container 类上放置某种访问器方法。它们可以是私有的,您可以将 MagicIterator 声明为朋友,如果您认为这是封装它的最佳方式,但我会直接公开它们。这些访问器方法将使用 Container 内的普通 STL 迭代器并执行到 IInterface 的转换。因此,迭代实际上将使用 Container 的访问器方法完成,而 MagicIterator 将只是一种代理对象,以使其更容易。为了使其可重入,您可以让 MagicIterator 传入某种 ID 以在 Container 中查找 STL 迭代器,或者实际上可以让它作为void *.

于 2009-01-22T21:25:35.717 回答
0

我现在找到了一个更适合我最初目的的解决方案。不过我还是不喜欢:)

该解决方案涉及在 IInterface* 上对 MagicIterator 进行模板化,并使用指向迭代器的 void*、所述迭代器的字节大小以及指向在所述 void* 上执行标准迭代函数(例如递增、递减、取消引用等。 MagicIterator 假定将给定的迭代器 memcpy 到内部缓冲区是安全的,并通过将自己的缓冲区作为 void* 传递给提供的函数来实现其自己的成员,就好像它是原始迭代器一样。

然后容器必须实现静态迭代函数,将提供的 void* 转换回 std::list::iterator。Container::begin() 和 Container::end() 只需构造一个 std::list::iterator,将指向它的指针连同其迭代函数表一起传递给 MagicIterator,然后返回 MagicIterator。

这有点恶心,打破了我关于“no memcpy()”的原始规则,并对所讨论的迭代器的内部进行了假设。但它避免了堆分配,保持 Collection 的内部(包括 Item)私有,使 MagicIterator 完全独立于相关集合和 IInterface*,并且理论上允许 MagicIterators 与任何集合一起工作(前提是它的迭代器可以安全地 memcopy()' d)。

于 2009-01-24T17:53:10.200 回答
0

访问者可能是一个更简单(因此更容易维护)的解决方案。

于 2009-12-27T08:16:10.687 回答