作为智能指针向量的替代方案，自定义分配器是否可行？

Question

这个问题涉及到拥有指针，使用指针，智能指针，向量和分配器。

我在代码架构方面有点迷惑。此外，如果这个问题已经有了答案，请原谅，但我到目前为止还没有找到令人满意的答案，请指点我。

我的问题是：

我在一个向量中存储了几个“东西”，同时有几个“消费者”需要这些“东西”。因此，我的第一次尝试如下：

std::vector<thing> i_am_the_owner_of_things;
thing* get_thing_for_consumer() {
    // some thing-selection logic
    return &i_am_the_owner_of_things[5]; // 5 is just an example
}

...

// somewhere else in the code:
class consumer {
    consumer() {
       m_thing = get_thing_for_consumer();
    }

    thing* m_thing;
};

在我的应用程序中，这是安全的，因为“things”在任何情况下都比“consumers”存在更长的时间。然而，在运行时可能会添加更多的“things”，这可能会成为一个问题，因为如果std::vector<thing> i_am_the_owner_of_things;重新分配内存，所有thing* m_thing指针将变为无效。

解决这种情况的方法是存储指向“things”的唯一指针，而不是直接存储“things”，即如下所示：

std::vector<std::unique_ptr<thing>> i_am_the_owner_of_things;
thing* get_thing_for_consumer() {
    // some thing-selection logic
    return i_am_the_owner_of_things[5].get(); // 5 is just an example
}

...

// somewhere else in the code:
class consumer {
    consumer() {
       m_thing = get_thing_for_consumer();
    }

    thing* m_thing;
};

这里的缺点是“事物”之间的内存一致性丢失了。是否可以通过使用自定义分配器重新建立这种内存一致性？我想到了一种类似于分配器的东西，它总是为10个元素分配内存，并在需要时添加更多的10个元素大小的内存块。

例如：
最初：
v = ☐☐☐☐☐☐☐☐☐☐
更多元素：
v = ☐☐☐☐☐☐☐☐☐☐ ☐☐☐☐☐☐☐☐☐☐
再次：
v = ☐☐☐☐☐☐☐☐☐☐ ☐☐☐☐☐☐☐☐☐☐ ☐☐☐☐☐☐☐☐☐☐

使用这样的分配器，我甚至不必使用“事物”的std::unique_ptr，因为在std::vector重新分配内存时，已经存在的元素的内存地址不会改变。

作为替代方案，我只能考虑通过std::shared_ptr<thing> m_thing来引用“消费者”中的“事物”，而不是当前的thing* m_thing，但我认为这似乎是最糟糕的方法，因为“事物”不应拥有“消费者”，使用共享指针将创建共享所有权。

那么，分配器方法是否可行？如果是这样，如何实现？我必须自己实现分配器吗，还是已经存在这样的实现？

- j00hi

---

多个消费者使用同一件东西吗？如果不是这样的话，将所有权从向量转移到消费者是否更为合适？ - Mike van Dyke

是的，多个消费者可以使用同一件物品。这就是重点，所有权不应转移给消费者。 - j00hi

@MarekR 是的，那可能是一个选项。但它永远不可能是一个完美的解决方案，因为一方面，您希望这个上限尽可能紧密。而如果在某些罕见情况下需要更多呢？ - j00hi

如果多个消费者需要访问同一个“thing”，明智的做法是使用某种指针向量。独立分配每个“thing”，并将指针传递给消费者。这些指针可以是普通指针，或者更好的是std::shared_ptr<>，因为您实际上拥有共享所有权：只要其中一个消费者仍然存在，就不能删除“thing”。 - cmaster - reinstate monica

这里的缺点是“事物”之间的内存一致性丢失。- 为什么这很重要？ - Igor G

Answer 1

如果你能把thing看作是一个值类型，请这样做。它能简化事情，你不需要使用智能指针来规避指针/引用失效的问题。后者可以有不同的解决方法：

• 如果在程序中通过push_front和push_back插入了新的thing实例，则使用std::deque而不是std::vector。这样，此容器中的元素没有被无效化(迭代器虽然无效 - 感谢@odyss-jii指出)。如果你担心过于依赖std::vector完全连续的内存布局带来的性能优势:创建基准测试并进行分析。
• 如果在程序运行期间在容器中间插入了新的thing实例，请考虑使用std::list。当插入或删除容器元素时，不会使指向容器元素的指针、迭代器或引用失效。在std::list中进行迭代比在std::vector中慢得多，但请确保在你的情况下，这是一个真正的问题，然后再过于担心它。

- lubgr

---

这些是一些值得考虑的好观点，谢谢！std::deque中的内存是如何管理的？它不也是某种链表或者它会按顺序存储内存吗？ - j00hi

它将内存存储在连续的块中。这使得它在某种程度上成为std::list和std::vector之间的混合体。请查看此线程以获取有关std::deque的更多信息。 - lubgr

@j00hi 这是一种使用块链表布局的方法。缺点是，在大多数实现中，块大小非常小且不可增长。通常可以通过宏定义来缓解这个问题，但应该是基于分析而不是猜测。 - darune

@j00hi，你可能还想查看“循环缓冲区”（不在std中）- 根据需要。 - darune

挑剔一点，但是迭代器在std::deque::push_back和std::deque::push_front上实际上是无效的，但对于实际元素的引用则不是。值得一提的是，这样有人就不会存储期望在后面插入后保持有效的迭代器了。 - odyss-jii

Answer 2

这个问题没有一个单一的正确答案，因为它很大程度上取决于确切的访问模式和所需的性能特征。

话虽如此，这是我的建议：

继续像你现在一样连续地存储数据，但不要存储指向该数据的别名指针。相反，考虑一种更安全的替代方法（这是一种经过验证的方法），在使用之前根据ID获取指针--顺便说一下，在多线程应用程序中，当这样的弱引用存在时，你可以锁定调整底层存储的尝试。

因此，你的消费者将存储一个ID，并根据需要从“存储”中获取数据的指针。这也使你控制所有的“获取”，以便你可以跟踪它们、实施安全措施等。

void consumer::foo() {
    thing *t = m_thing_store.get(m_thing_id);
    if (t) {
        // do something with t
    }
}

或者更高级的替代方案，以帮助在多线程场景下进行同步：

void consumer::foo() {
    reference<thing> t = m_thing_store.get(m_thing_id);
    if (!t.empty()) {
        // do something with t
    }
}

其中reference将是一些线程安全的RAII "弱指针"。

有多种实现方式。您可以使用开放地址哈希表并使用ID作为键；如果正确平衡，这将为您提供大约O(1)的访问时间。

另一种选择（最佳情况为O(1)，最坏情况为O(N)）是使用一个"引用"结构，带有32位ID和32位索引（因此与64位指针大小相同）--索引充当某种缓存。当您获取时，首先尝试索引，如果索引中的元素具有预期的ID，则完成。否则，您会遇到"缓存未命中"，然后您会对存储进行线性扫描，以根据ID找到元素，然后在您的引用中存储上次已知的索引值。

- odyss-jii

---

通过ID访问某个“东西”会带来一些新问题：如果另一个“东西”重复使用了给定的ID（就像在ABA问题中），如果使用者需要RAII但是“东西”在销毁时不存在，那么按ID提取方法的性能是否重要？ - Igor G

@IgorG 是的，但是这些都有不错的经过实战验证的默认值。对于ID，使用递增序列+交错增量（lock xadd）通过std::atomic。至于thing的所有权：使用此解决方案，消费者可能永远不会拥有thing，存储拥有它。因此，任何消费者都不允许假定thing将在任何时候存在，必须始终进行检查。这也是保证内存安全的原因，但您必须围绕此原则进行设计。按ID获取的性能可能非常重要。如果正确执行，例如开放地址哈希表，它将非常快速。 - odyss-jii

我喜欢这个答案（并不明白为什么它被踩了），因为它提供了一种不同但可行的解决问题的方法。这种方法难道不是像OpenGL或Vulkan这样的API在引用资源时所做的吗？我的意思是，我不知道它们如何在内部处理，但我可以想象它们会像这个答案中提出的那样处理，因为它们总是返回指向资源（如纹理或GPU缓冲区）的句柄的连续数字。这些数字也被称为资源的“名称”。 - j00hi

Answer 3

我认为最好的方法是创建一个新的容器，以安全的方式运行。

优点：

• 更改将在不同的抽象级别上完成
• 对旧代码的更改将最小化（只需用新容器替换std::vector）。
• 这将是“干净的代码”方式来做到这一点

缺点：

• 看起来可能需要做更多的工作

其他答案建议使用std::list来完成任务，但是随着分配数量的增加和随机访问速度的变慢，所以我认为最好从几个std::vector组合自己的容器。

因此，它可能看起来像这样（最小示例）：

template<typename T>
class cluster_vector
{
public:
    static const constexpr cluster_size = 16;

    cluster_vector() {
       clusters.reserve(1024);
       add_cluster();
    }

    ...

    size_t size() const {
       if (clusters.empty()) return 0;
       return (clusters.size() - 1) * cluster_size + clusters.back().size();
    }

    T& operator[](size_t index) {
        thowIfIndexToBig(index);
        return clusters[index / cluster_size][index % cluster_size];
    }

    void push_back(T&& x) {
        if_last_is_full_add_cluster();
        clusters.back().push_back(std::forward<T>(x));
    }

private:
    void thowIfIndexToBig(size_t index) const {
        if (index >= size()) {
            throw std::out_of_range("cluster_vector out of range");
        }
    }

    void add_cluster() {
       clusters.push_back({});
       clusters.back().reserve(cluster_size);
    }

    void if_last_is_full_add_cluster() {
       if (clusters.back().size() == cluster_size) {
           add_cluster();
       }
    }

private:
    std::vector<std::vector<T>> clusters;
}

通过这种方式，您将提供一个不会重新分配项目的容器。无论 T 是什么都可以。

- Marek R

---

反对票：建议“自己动手解决”（即使已有标准解决方案）。 - darune

你的意思是 std::list 吗？这不像 std::list。 - Marek R

Answer 4

“共享指针”对我来说似乎是最糟糕的方法，因为“事物”不应该拥有“消费者”，而使用共享指针会创建共享所有权。

那又怎样呢？也许代码稍微不太容易理解，但这将解决你所有的问题。（顺便说一下，你使用“消费者”这个词混淆了概念，在传统的生产者/消费者范式中，“消费者”确实会拥有所有权。）

此外，在你当前的代码中返回一个裸指针已经完全不明确所有权了。总的来说，如果可以避免使用裸指针（比如你不需要调用delete），那么避免使用裸指针是一个好习惯。如果你选择使用unique_ptr，我会返回一个引用。

std::vector<std::unique_ptr<thing>> i_am_the_owner_of_things;
thing& get_thing_for_consumer() {
    // some thing-selection logic
    return *i_am_the_owner_of_things[5]; // 5 is just an example
}

- IceGlasses

---

不，共享指针存在的目的是表达所有权。而且，正如我已经明确说明的那样，“consumer”在我的例子中不应该获得“thing”的所有权。引用Herb Sutter在他的精彩演讲回到基础！现代C++风格的基本要素中所说的话：非拥有的裸指针仍然很棒。 - j00hi

“避免使用裸指针”是一个谬论。应该避免使用裸拥有指针。这样就没有歧义了，裸指针不拥有任何东西。 - 463035818_is_not_a_number