7

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

std::vector<Animal*> v;

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

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

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

但是如果sizeof(Dog)大于sizeof(Cat)那么在对象是类型的情况下会浪费内存Cat。

我还可以使用容器变体：

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

但我不知道在这种情况下迭代器会如何以及它们是否会引入更多开销。

“指针向量方法”是我们能做的最好的吗？

更多信息：对象的大小在 50 到 250 字节之间，容器长度在 10K 到 1M 元素之间，我必须迭代容器一百万次。

谢谢你。

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

4

2 回答 2

4

我要把我的评论变成答案。

我会说你最好的选择是将所有狗放入 a 中vector<Dog>，将所有猫放入 avector<Cat>中，然后分别迭代它们。这样您就可以使每个向量保持最佳包装。

使用一些 CRTP，您可以将其自动化，以便轻松添加更多动物而不会遇到麻烦。

一些例子：

template <typename T>
class Container{
public:
    static std::vector<T> m_elements; //static vector will contain animals

    //overloaded operator new adds the Animal to m_elements
    void* operator new(size_t){
        m_elements.push_back( T{} );
        return &m_elements[m_elements.size() - 1];
    }
};

template <typename T> std::vector<T> Container<T>::m_elements;

//some example animals
class Dog : public Container<Dog>{
public:
    std::string woof;

    Dog( char* s = "woof" ){
        woof = s;
    }
};

class Cat : public Container<Cat>{
public:
    std::string meow;

    Cat( char* s = "meow" ){
        meow = s;
    }
};

int main(){

    new Dog( "woof" );
    new Dog( "rrawoof" );
    new Cat( "meow" );
    new Cat( "meweeow" );

    //easy iteration
    for( auto dog : Dog::m_elements )
        std::cout << dog.woof << "\n";

    for( auto cat : Cat::m_elements )
        std::cout << cat.meow << "\n";

    std::cout << "end";
}

超载是否是一个好主意new是一个不同的问题，但它很适合展示。

于 2013-10-06T18:23:34.923 回答
2

对 - 在这里完全重写，而且更简单。

我同意 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太简单而无法受益 - 这个想法是对于复杂的方法来说该方法更快，可以通过预先完成一次来避免重复的运行时类型检查。

顺便说一句 - 好问题。

于 2013-10-06T19:48:30.733 回答