自定义分配器作为智能指针向量的替代品？

Question

这道题是关于拥有指针、使用指针、智能指针、向量和分配器的。

我对代码架构的想法有点迷茫。此外，如果这个问题已经在某处找到答案，1. 抱歉，但到目前为止我还没有找到令人满意的答案，2. 请指点一下。

我的问题如下：

我有几个 "things" 存储在一个向量中，还有几个 "consumers" "things"。所以，我的第一次尝试如下：

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;
};

这里的缺点是 "things" 之间的内存一致性丢失了。这种内存一致性是否可以通过使用自定义分配器以某种方式重新建立？我正在考虑像分配器这样的东西，它总是一次为例如 10 个元素分配内存，并且在需要时添加更多 10 个元素大小的内存块。

示例：
最初：
v = ☐☐☐☐☐☐☐☐☐☐☐☐
更多元素：
v = ☐☐☐☐☐☐☐☐☐☐☐ ☐☐☐☐☐☐☐☐☐☐☐
又一次：
v = ☐☐☐☐☐☐☐☐☐☐☐☐ ☐☐☐☐☐☐☐ ☐☐☐ ☐ ☐ ☐ ☐ ☐ ☐ ☐ ☐ ☐

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

作为替代方案，我只能考虑通过 std::shared_ptr<thing> m_thing 引用 "consumer" 中的 "thing"，而不是当前的 thing* m_thing，但这似乎是最糟糕的接近我，因为 "thing" 不应拥有 "consumer" 并且使用共享指针我将创建共享所有权。

那么，分配器方法好吗？如果是这样，怎么办？我必须自己实现分配器还是已有分配器？

Answer 1

如果您能够将 thing 视为值类型，请这样做。它简化了事情，您不需要智能指针来规避 pointer/reference 失效问题。后者可以有不同的处理方式：

如果在程序中通过 push_front 和 push_back 插入了新的 thing 实例，请使用 std::deque 而不是 std::vector。然后，没有指向此容器中元素的指针或引用失效（不过迭代器失效了——感谢@odyss-jii 指出了这一点）。如果您担心您严重依赖 std::vector 的完全连续内存布局的性能优势：创建基准和配置文件。
如果程序中在容器中间插入了新的thing个实例，可以考虑使用std::list。没有 pointers/iterators/references 在插入或移除容器元素时失效。 std::list 的迭代比 std::vector 慢得多，但在担心太多之前，请确保这是您场景中的实际问题。

Answer 2

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

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

继续按原样连续存储数据，但不要存储指向该数据的别名指针。相反，考虑一种更安全的替代方法（这是一种行之有效的方法），您可以在使用它之前根据 ID 获取指针——作为 side-note，在 multi-threaded 应用程序中，您可以锁定调整大小的尝试底层存储，而这样一个弱引用仍然存在。

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

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

或在 multi-threaded 场景中帮助同步的更高级替代方法：

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

其中 reference 会是一些 thread-safe RAII "weak pointer".

有多种实现方法。您可以使用 open-addressing 散列 table 并将 ID 用作键；如果你适当地平衡它，这会给你大约 O(1) 的访问时间。

另一种选择（best-case O(1), worst-case O(N)）是使用 "reference" 结构，具有 32 位 ID 和 32 位索引（与 64 位指针大小相同）——索引用作 sort-of 缓存。获取时，首先尝试索引，如果索引中的元素具有预期的 ID，则完成。否则，您会得到一个 "cache miss" 并对存储进行线性扫描以根据 ID 查找元素，然后将 last-known 索引值存储在您的引用中。

Answer 3

IMO 最好的方法是创建新的容器，它的行为是安全的。

优点：

更改将在单独的抽象级别上完成
对旧代码的更改将是最小的（只需将 std::vector 替换为新容器）。
这将是 "clean code" 的方式

缺点：

看起来还有更多工作要做

其他答案建议使用 std::list 来完成这项工作，但分配数量较多且随机访问速度较慢。所以 IMO 最好用几个 std::vectors.

组成自己的容器

所以它可能开始看起来或多或少像这样（最小示例）：

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 所做的事情。

Answer 4

[A shared pointer] seems like the worst approach to me, because a "thing" shall not own a "consumer" and with shared pointers I would create shared ownership.

那又怎样？可能代码少了点self-documenting，但是会解决你所有的问题。（顺便说一下，您使用 "consumer" 这个词是在混淆事情，在传统的 producer/consumer 范例中会取得所有权。）

此外，return在您当前的代码中使用原始指针已经完全不明确所有权。一般来说，如果可以的话，我会说避免使用原始指针是个好习惯（比如你不需要调用 delete。）如果你使用 [=12=，我会 return 一个参考]

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
}

自定义分配器作为智能指针向量的替代品？

Custom allocators as alternatives to vector of smart pointers?

c++

c++11

shared-ptr

unique-ptr

allocator