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 回答