我可以禁止向量重新分配对象吗？

Question

假设我们有一个 double (values) 向量和一个包含对象的向量，这些对象存储指向 double (vars) 向量元素的指针：

class Var
{
public:
    explicit Var(double* v) : _value(v) {};
    ~Var() {};

    const double get() const { return *_value; };
    void set(const double v) { *_value = v; };

private:
    double* _value;
};


struct Vars
{
    Vars()
    {
        //values.reserve(1000'000);
    }
    vector<double> values{};
    vector<Var> vars{};

    void push(const double v)
    {
        values.push_back(v);
        vars.emplace_back(&values.back());
    }
};

（添加后的对象永远不会被删除）

众所周知，当向量重新分配对象时，所有指针都会中断。我可以预先调用 reserve()，但问题是我不知道将存储多少个对象，可能是 5 个，也可能是 500'000 个，shrink_to_fit() 无论如何都会破坏指针。

在这种情况下我可以使用双端队列，但我想知道我是否可以在调用 shrink_to_fit () 或其他方式时阻止向量重新分配内存？

Answer 1

Can i forbid vector to reallocate objects?

您可以通过不执行导致向量（可能）重新分配的操作来避免重新分配。

除了使向量成为 const 之外，没有其他方法可以阻止这些操作的执行。一种解决方案是使 vector 成为私有成员（永远不会 return 指向该成员的 non-const 的指针/引用），在这种情况下，您只需要担心您的成员函数不执行那些操作。

the problem is that I don't know how many objects will be stored, maybe 5, or maybe 500'000

如果不需要插入之间的指针，可以一次性完成所有插入（不管多少次），然后再获取指针，然后不再修改vector。

在一般情况下，以上不是一个选项，如果您需要指针保持有效，那么 vector 不是一个合适的数据结构选择。列表或双端队列的工作取决于您如何使用容器。

关于这个例子：拥有对象向量和指向这些对象的指针（包含包装器）的向量似乎毫无意义。

Answer 2

std::vector 不允许您将其缓冲区的一部分 return 保留到堆中，同时保留其余部分； std::allocator“概念”中没有 API 可以做到这一点。

std::vector保证连续存储，所以不能分块分配。

如果您不需要连续存储，请使用 std::deque 或 hand-rolled 副本（deque 留下一些 performance-critical 参数供实现选择，并且不公开能够将它们配置为 end-users；因此，如果您的双端队列不适合您的用例，您可能需要自己动手）。

std::deque 是固定大小缓冲区的动态数组，外加少量 end-management 状态。它允许使用动态大小的容器和 O(1) 随机访问进行稳定存储，容器开销只占存储量的一小部分（缩放开销是每个块一个指针，块大小比指针大很多倍在我见过的每一个实现上）。

与 vector 相比，它的缺点是存储不连续，迭代器/[] 查找有一个额外的间接指针，但它会是一个奇怪的连续存储容器，适合其余部分您的要求。

Answer 3

关键是

objects after adding are never deleted

不是将 pointers/iterators/references 存储到向量的元素，而是将指针¹ 存储到向量和索引。

class Var
{
public:
    explicit Var(std::vector<double> * vec, size_t index) 
      : vec(vec), index(index) {};

    double get() const { return vec->at(index); };
    void set(double v) { vec->at(index) = v; };

private:
    std::vector<double> * vec;
    size_t index;
};


struct Vars
{
    vector<double> values;
    vector<Var> vars;

    void push(double v)
    {
        vars.emplace_back(&values, values.size());
        values.push_back(v);
    }
};

指针而不是引用所以我们是 SemiRegular 类型（并且可以很容易地将 == 定义为 Regular）

我可以禁止向量重新分配对象吗？

Can i forbid vector to reallocate objects?

c++

pointers

vector

allocator