C++中能否实现支持push_back且不失效元素的随机访问容器？

你遇到的核心矛盾是std::vector扩容时会重新分配内存导致元素指针失效，而std::list虽能保持指针有效性但不支持随机访问。以下是两种解决思路：

1. 使用现成的第三方容器：boost::stable_vector #

Boost库中的stable_vector完美契合你的需求：

• 支持push_back()和随机访问（operator[]、迭代器随机访问），接口和std::vector几乎一致
• 扩容时不会移动已有元素，只会新增内存块存储新元素，因此指向容器内元素的指针、引用、迭代器永远不会失效
• 随机访问是**O(1)**时间复杂度，不过常数开销比std::vector略高，因为需要计算元素所在的内存块位置

2. 自定义实现基于指针的容器 #

如果不想依赖Boost，可以自己封装一个基于std::vector的容器，用指针存储元素：

#include <vector>
#include <memory>

template <typename T>
class StableRandomContainer {
private:
    std::vector<std::unique_ptr<T>> _data;
public:
    // 随机访问接口
    T& operator[](size_t idx) { return *_data[idx]; }
    const T& operator[](size_t idx) const { return *_data[idx]; }

    // push_back接口
    void push_back(const T& val) {
        _data.emplace_back(std::make_unique<T>(val));
    }
    void push_back(T&& val) {
        _data.emplace_back(std::make_unique<T>(std::move(val)));
    }

    // 基础容器接口
    size_t size() const { return _data.size(); }
    bool empty() const { return _data.empty(); }
};

自定义容器的特性： #

• push_back()时，std::vector扩容只会移动存储的指针（而非元素本身），因此指向T实例的指针永远有效
• 完全支持随机访问，用法和std::vector一致
• 缺点：元素存储在堆上，有额外的内存分配开销，且缓存局部性不如原生std::vector（元素内存不连续）

注意事项 #

• 如果对性能要求极高，优先选boost::stable_vector，它的内存管理更高效，缓存友好性优于自定义指针容器
• 自定义容器中建议使用智能指针（如std::unique_ptr）避免内存泄漏，不要直接用裸指针

内容的提问来源于stack exchange，提问作者Ramster445