c++ - 可以在 C++ 模板中强制使用连续的分配边界吗？

Question

简单的例子:

template <class P> class MyT
{
    struct Item
    {
    public:
        Item() {}
        P *pData;
        Item *next;
    };
    Item *head;
public:
    ...adding etc..
    P* operator [](int index)
    {
       See question below:
    }
};

我能否以某种方式确保“项目”的分配方式使我可以按如下方式计算偏移量:(@Steve:)这里可能不太清楚；我需要的是一种无需迭代 10000 个下一个即可快速轻松地找到该项目的方法。

Item *pi = head + (sizeof(Item) * (index - 1));

A (clearer?) explanation我的意思是

Answer 1

取决于您在“添加等”中所说的“等”的意思。

如果“etc”包括“removing”，那么你有一个明显的问题，如果你删除了列表中间的东西，那么为了保持索引，你必须向下移动它之后的所有内容，这意味着更新所有next 指针。

我认为您可能过于简化了您的示例。如果您需要连续存储，请使用 vector (P 或 Item，如果您删除了 Item 中有用的内容) .如果您有连续的存储空间，那么使用 next 指针就没有任何好处，因为您可以通过将 this 加 1 在 Item 中计算它>(然后检查边界以确保您没有到达终点)。

如果您绝对需要公共(public)next 指针字段，因为它是您正在实现的某些您无法更改的接口(interface)的一部分，那么您可以在复制构造函数和 中更新它operator= for Item，接口(interface)最好禁止客户端写入。

没有办法告诉内存分配器为单独的分配分配连续的存储空间，如果这就是您的要求。那怎么行呢？如果你来分配时，“下一个”地址已经被占用了怎么办？如果分配器为其自己的控制结构强加了一些开销(几乎所有通用分配器都这样做)，那么分配一个 Item 需要的不仅仅是 sizeof(Item)字节？您可以使用 fixed-size allocator 获得您想要的行为一段时间。 ，但最终它需要一个新 block ，或者你删除了一些东西，并且关系不再成立。