同类容器,其类型仅在运行时已知

Question

我有一个单一类型的集合,其类型只在运行时知道.一旦定义了类型,它就永远不会改变.我目前正在向量中存储指向对象的指针,如下所示:

std::vector<Animal*> v;

我想知道是否可以将实例存储在连续的内存中.我的目的是编写一个更加缓存友好的代码并更快地迭代容器.

我可以为每个向量的元素使用boost :: variant,例如,

std::vector<boost::variant< Cat, Dog > >

但如果sizeof(Dog)比sizeof(Cat)那时大得多,那么在对象属于类型的情况下会浪费内存Cat.

我也可以使用Variant的容器:

boost::variant< std::vector<Cat>, std::vector<Dog> >

但是我不知道在这种情况下迭代器会是多少,如果它们会引入更多的开销.

"指针矢量接近"是我们能做的最好的吗？

更多信息:对象的大小在50到250个字节之间,容器长度在10到1M之间,我必须在容器上迭代一百万次.

谢谢.

编辑:我在这里发现了一个类似的问题(也有很好的建议): 如何用C++编写缓存友好的多态代码？

Answer 1

正确 - 在这里完全重写，并且简单得多。

我同意 s3rius 的观点，你仍然应该使用 std::vector。理想情况下，如果您要存放猫，您会使用...

std::vector<Cat>

如果你要存放狗，你会想...

std::vector<Dog>

但是，您需要运行时多态性来选择要处理的情况。

一种方法是（或受其启发）策略设计模式。为这些向量的接口定义一个基类，并使用一个模板类来实现包含该向量的接口。

class Animals_IF
{
  public:
    virtual int size () const = 0;
};

template<typename T> class Animals_Vector
{
  private:
    std::vector<T> store;

  public:
    int size () const;
};

template<typename T> int Animals_Vector<T>::size () const
{
  return store.size ();
}

这里的问题是接口不能提及Cat或者Dog因为它不知道具体类型，这当然就是我选择size作为上面示例方法的原因。

一种解决方案是使用一种boost::variant可能的类型来传递值，因此每个策略/包装类都可以在使用它们之前检查它获取的值是否是正确的类型。变体中的包装/展开值可以通过（非模板）基类中的模板方法来处理。

如果所有包装和展开都变得低效，您必须确定要处理的情况，然后通过正确的策略/包装器类型（而不是基类）进行调用。为此，需要所有策略/包装器案例的 boost::variant 。这并不妨碍您也拥有指向基类的指针。事实上，将指向基类的指针和 包装boost::variant在一个类中（在需要时使用模板方法）。

class Animals_IF
{
  public:
    typedef boost::variant<Cat,Dog>  Animal;

    virtual int size () const = 0;

    template<typename T> void slow_push (const T &p)
    {
      push_ (Animal (p));
    }

  private:
    virtual void slow_push_ (const Animal &p) = 0;
};

template<typename T> class Animals_Vector
{
  public:
    int size () const;

    void fast_push (const T &p);

  private:
    std::vector<T> store;

    void slow_push_ (const Animal &p);
};

template<typename T> int Animals_Vector<T>::size () const
{
  return store.size ();
}

template<typename T> void Animals_Vector<T>::fast_push (const T &p)
{
  store.push (p);
}

template<typename T> void Animals_Vector<T>::slow_push_ (const Animal &p)
{
  const T* item = boost::get<T> (&p);

  if (T)  store.push (*item);
  //  else throw?
}

class Animals
{
  public:
    int size () const
    {
      //  null check needed?
      return ptr->size ();
    }

    template<typename T> void slow_push (const T &p)
    {
      //  null check needed?
      ptr->slow_push (p);
    }

    template<typename T> void fast_push (const T &p)
    {
      Animals_Vector<T> *lptr = boost::get<T> (&store);
      if (lptr)  lptr->fast_push (p);
      //  else throw?
    }

  private:
    Animals_IF*  ptr;
    boost::variant<Animals_Vector<Cat>,Animals_Vector<Dog>>  store;
};

如果共享接口无法真正提供任何东西（因为每个方法都需要传递值，并且作为变体包装/展开是不可接受的），那么整个策略就没有必要了。只需有一个不同 std::vector 类型的 boost::variant 即可。

另外，fast_push上面的方法不会很快，因为 apush太简单而无法受益 - 这个想法是，该方法对于复杂方法来说更快，可以通过预先完成一次来避免重复的运行时类型检查。

顺便说一句 - 好问题。