2

假设我需要存储一个相同类型的对象的集合,但是这个类型不能在编译时定义。还假设一旦定义了这种类型,它就永远不会改变。众所周知,当编译时不知道类型时,可以使用指向其基类的指针容器来存储这些对象,即

std::vector<Base*> collection;
collection.push_back( new Derived() );

这样,分配的对象不一定会并排存储在内存中,因为在每次分配中new()都会返回内存中的任意位置。此外,每个对象都嵌入了一个额外的指针 ( vptr),因为Base类当然需要是多态的。

对于这种特殊情况(类型定义一次 + 类型永不改变),上述解决方案不是最佳解决方案,因为理论上,

  1. 不必vptr为每个对象存储相同的 (sizeof() = 指针大小):它们都指向相同的vtable
  2. 可以使用连续的存储位置,因为对象的大小是在程序开始时定义的,并且永远不会改变。

问:你们知道克服这些问题的策略/容器/内存分配器/成语/技巧/其他任何东西吗?

我想我可以做这样的事情(使用经典的Shape示例):

struct Triangle_Data {
    double p1[3],p2[3],p3[3];
};

struct Circle_Data {
    double radius;
};

struct Shape {
    virtual double area() const = 0;
    virtual char* getData() = 0;
    virtual ~Shape() {}
};

struct Triangle : public Shape {
    union {
        Triangle_Data tri_data;
        char data[sizeof(Triangle_Data)];
    };
    double area() const { /*...*/ };
    char* getData() { return data; }
    Triangle(char * dat_) {
        std::copy(dat_, dat_+sizeof(Triangle_Data), this->data);
    };
};

struct Circle : public Shape {
    union {
        Circle_Data circ_data;
        char data[sizeof(Circle_Data)];
    };
    double area() const { /*...*/ };
    char* getData() { return data; }
    Circle(char * dat_) {
        std::copy(dat_, dat_+sizeof(Circle_Data), this->data);
    };
};

template<class BaseT>
struct Container {
    int n_objects;
    int sizeof_obj;
    std::vector<char> data;
    Container(...arguments here...) : ...init here... {
        data.resize( sizeof_obj * n_objects );
    }
    void push_back(Shape* obj) {
        // copy the content of obj
        for( int i=0; i<sizeof_obj; ++i)
            data.push_back(*(obj.getData() + i));
    }
    char* operator[] (int idx) {
        return data + idx*sizeof_obj;
    }
};

// usage:
int main() {
    Container<Shape> collection( ..init here.. );
    collection.push_back(new Circle());
    cout << Circle(collection[0]).area() << endl; // horrible, but does it work?
};

当然,这种方法在类型安全、对齐等方面存在很多问题。有什么建议吗?

谢谢

4

3 回答 3

3

不必存储相同的 vtable(每个对象 8 个字节?)collection.size() 次;

您根本没有存储 vtable。无论对象是否为多态,您都在存储大小相同的指针。如果集合有N对象,那么它需要N * sizeof(void*)字节。所以上面的说法是错误的。

可以使用连续的存储位置,因为它们的大小是已知的并且在定义它们的类型时彼此相等。

这还不清楚。如果您在谈论由容器维护的存储,那么是的,由容器维护的存储std::vector保证是连续的。

于 2013-04-07T15:00:26.187 回答
3

要解决问题的第 2 点,如果您知道所有对象都属于同一类型,并且您在运行时拥有此信息,您可能会考虑虚拟化容器并使用工厂创建它。只是为了给出这个想法的草图:

class ShapeContainer {
 /* Virtual base */
}; 

class CircleContainer : public ShapeContainer {
/* ... */
private:
    std::vector<Circle> impl_;
}

class ShapeContainerFactory {
 /* Factory for ShapeContainer derived objects */
};

int main() {
    ShapeContainer& collection = ShapeContainerFactory.create("Circle");
    collection.push_back( Circle() );
};

在这种情况下,您将保证连续存储的不是指向多态对象的指针或引用,而是对象本身。

于 2013-04-07T15:16:41.240 回答
1

1)没有必要存储相同的 vptr(每个对象 8 个字节?)collection.size() 次;

这不是必需的,但对象是相互独立的。

2) 可以使用连续的存储位置,因为它们的大小是已知的并且在定义它们的类型时彼此相等。

...确实,如果您可以存储具体实例,则可以将它们存储在连续的内存中。


所以,你可以做什么 ?

一种解决方案是使用多态实例,而是将数据和多态分开:

struct IShape {
    virtual ~IShape() {}
    virtual double area() const = 0;
};

struct Circle {
    float center, radius;
};

struct IShapeCircle: IShape {
    IShapeCircle(Circle const& c): circle(const_cast<Circle&>(c)) {}
    virtual double area() const { return PI * circle.radius * circle.radius; }

    Circle& circle;
};

这样,您只需在需要时创建多态实例。而对于存储,我们可以采用 Massimiliano 的解决方案。

struct IShapeVector {
    virtual ~IShapeVector() {}
    std::unique_ptr<IShape> get(size_t i) = 0;
    std::unique_ptr<IShape const> get(size_t i) const = 0;
};

struct IShapeCircleVector: IShapeVector {
    std::unique_ptr<IShape> get(size_t i) {
        return make_unique<IShapeCircle>(_circles.at(i));
    }
    std::unique_ptr<IShape const> get(size_t i) const {
        return make_unique<IShapeCircle const>(_circles.at(i));
    }

    std::vector<Circle> _circles;
};

但是,您可能会发现分配/解除分配流量比单纯的 v-ptr 更能减慢您的速度。

于 2013-04-07T17:31:22.000 回答