如何高效拆分不可移动类型NonMovableType的容器？

先明确核心问题：你提到的NonMovableType并非严格意义上的不可移动——编译器会为它自动生成默认移动构造/赋值函数，只是因为成员std::initializer_list<union_type>的移动与拷贝行为完全等价（仅拷贝指针和长度，不转移底层数组所有权），所以移动操作不会带来性能提升。基于这个前提，我们可以给出以下几种更优的实现方案：

1. 一次遍历完成拆分（替代两次std::copy_if） #

两次std::copy_if需要遍历原容器两次，对于大容器来说效率偏低。可以手动遍历一次，将元素直接分配到两个结果容器中：

std::vector<NonMovableType> container;
std::vector<NonMovableType> result_a, result_b;

// 预分配内存，避免多次扩容（可选但推荐）
const auto count_a = std::count_if(container.begin(), container.end(),
    [](const NonMovableType& e) { return e.data.size(); });
result_a.reserve(count_a);
result_b.reserve(container.size() - count_a);

// 单次遍历拆分
for (const auto& elem : container) {
    if (elem.data.size()) {
        result_a.push_back(elem);
    } else {
        result_b.push_back(elem);
    }
}
container.clear();

这种方式仅遍历原容器一次，比两次std::copy_if减少一半的遍历开销。

2. 原地拆分（利用std::partition） #

如果你的需求是在原容器内完成拆分（而非分到两个新容器），可以使用std::partition或std::stable_partition。虽然移动NonMovableType本质还是拷贝，但代码会更简洁：

std::vector<NonMovableType> container;

// 原地拆分：前半部分为满足条件的元素，后半部分为不满足的
auto mid = std::partition(container.begin(), container.end(),
    [](const NonMovableType& e) { return e.data.size(); });

// 将后半部分转移到result_b，前半部分保留在container中
std::vector<NonMovableType> result_b(mid, container.end());
container.erase(mid, container.end());

3. 包装为指针/智能指针（彻底避免元素拷贝） #

如果NonMovableType的拷贝成本较高，或者你希望拆分操作完全无拷贝开销，可以将元素包装为指针或智能指针存储在容器中。此时容器的移动操作仅转移指针所有权，效率极高：

// 将原容器转为智能指针容器
std::vector<std::unique_ptr<NonMovableType>> ptr_container;
ptr_container.reserve(container.size());
for (auto& elem : container) {
    ptr_container.emplace_back(std::make_unique<NonMovableType>(std::move(elem)));
}
container.clear();

// 拆分智能指针容器，无拷贝开销
std::vector<std::unique_ptr<NonMovableType>> result_a, result_b;
for (auto& ptr : ptr_container) {
    if (ptr->data.size()) {
        result_a.push_back(std::move(ptr));
    } else {
        result_b.push_back(std::move(ptr));
    }
}

缺点是需要额外的堆内存分配，且访问元素时需要解引用指针。

4. 额外优化建议 #

• 始终为结果容器调用reserve预分配内存，避免多次扩容带来的内存拷贝开销；
• 如果原容器后续不再使用，可直接用std::move转移原容器的内存空间（针对指针容器效果更明显）。

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