如何高效乱序构造vector<T>，确保T的构造函数仅执行N次？

背景与问题 #

需要构造一个大小为N的vector<T>，N在程序运行前可知但并非编译期常量。常规流程是先调用vector<T>::reserve(N)预分配内存，再通过push_back填充元素，但现在需要按已知索引乱序插入元素。核心诉求是：确保vector构造过程中T的构造函数恰好被调用N次，避免不必要的性能损耗。

直接用malloc分配原生数组能实现类似高效操作，但无法将原生数组内存转移给vector；更关键的是，未初始化的内存可能破坏T的类不变式，初始化安全性是必须保证的核心问题。

典型场景比如计算逆排列（用vector<size_t> perm表示映射i->perm[i]），当T的构造成本远高于size_t时，常规方法的性能问题会被放大。

补充约束：T是500字节的POD类型，必须保证vector线性迭代时的缓存性能，因此存储T*再置换的方案不可行。而STL容器因强制保证每个对象完成初始化，很难实现"仅构造每个对象一次"的目标。

可行方案 #

Peter提出的初始化后修改方案可满足需求：为T添加一个哑构造函数，先通过reserve(N)预分配内存，再调用N次emplace_back用哑构造函数创建对象，最后按任意索引完成实际初始化。示例代码如下：

struct T {
    struct DummyConstructorMarker {};
    T(DummyConstructorMarker) {}
    char data[500];
};

vector<T> makeVector(vector<size_t>& initOrder, int N, /* 其他状态参数 */) {
    vector<T> result;
    result.reserve(N);
    for (int i = 0; i < N; i++) {
        result.emplace_back(T::DummyConstructorMarker());
    }
    for (size_t index : initOrder) {
        /* 为index位置的data赋值完成初始化 */
    }
    return result;
}

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