如何比std::vector更快地收集小对象？

首先，你的场景非常典型——递归解析器收集令牌，无法预知元素数量时，小对象频繁扩容导致的拷贝开销确实是核心性能瓶颈。下面从标准库、Boost工具和自定义实现三个方向给你具体方案：

一、标准库层面的快速优化 #

1. 优先启用移动语义 #

你的SmallObject包含boost::icl::discrete_interval<unsigned>，首先要确保这个类型支持移动构造/赋值（Boost.ICL的容器通常原生支持）。给SmallObject显式声明默认移动操作，让std::vector扩容时用移动代替拷贝：

struct SmallObject { 
    unsigned id; 
    boost::icl::discrete_interval<unsigned> ival;

    // 启用默认移动构造和赋值，避免深拷贝
    SmallObject(SmallObject&&) = default;
    SmallObject& operator=(SmallObject&&) = default;
};

对于带复杂成员的对象，移动操作的开销比拷贝低几个数量级，能直接缓解扩容的性能问题。

2. 用std::deque作为中间存储 #

std::deque底层是分段数组结构，每次push_back只会在当前段末尾添加元素，段满了就新建一个段，不会拷贝之前的所有元素，完美适配你只追加的场景。如果最后需要转换成std::vector，可以一次性分配足够空间后批量移动：

std::deque<SmallObject> temp;
// 批量push_back元素...

// 转换为vector，用move减少开销
std::vector<SmallObject> result;
result.reserve(temp.size());
std::move(temp.begin(), temp.end(), std::back_inserter(result));

二、Boost库的专用工具 #

1. boost::container::stable_vector #

Boost.Container的stable_vector和std::vector接口兼容，但底层用链表管理内存块，元素不会在扩容时被移动（地址始终稳定），同时避免了std::vector的扩容拷贝。如果最后需要转成std::vector，同样可以一次性移动所有元素。

2. boost::pool内存池 #

如果想直接优化内存分配逻辑，给std::vector指定boost::pool_allocator<SmallObject>，它会预分配大块内存，减少系统调用开销，同时避免频繁扩容：

#include <boost/pool/pool_alloc.hpp>

std::vector<SmallObject, boost::pool_allocator<SmallObject>> objects;

这种方式不需要修改存储逻辑，替换allocator就能获得明显性能提升。

三、自定义块链表+一次性转vector #

这就是你提到的“填满块的单链表”方案，实现简单且性能拉满：

// 定义块大小，比如每页64KB（16字节*4096=64KB），适配缓存页大小
constexpr size_t BLOCK_SIZE = 4096;

// 用链表存储满/未满的块
std::list<std::vector<SmallObject>> blocks;

// 追加元素的函数
void push_object(SmallObject obj) {
    if (blocks.empty() || blocks.back().size() == BLOCK_SIZE) {
        blocks.emplace_back(BLOCK_SIZE); // 新建预分配好空间的块
    }
    blocks.back().push_back(std::move(obj));
}

// 转换为单个vector
std::vector<SmallObject> to_vector() {
    size_t total = 0;
    for (const auto& block : blocks) {
        total += block.size();
    }
    std::vector<SmallObject> result;
    result.reserve(total);
    for (auto& block : blocks) {
        std::move(block.begin(), block.end(), std::back_inserter(result));
    }
    blocks.clear(); // 清空临时块
    return result;
}

这个方案的优势：

• 中间追加时完全没有扩容拷贝（每个块预分配了固定大小）
• 最后只做一次批量移动/拷贝，开销极小
• 块大小设为缓存页大小，能最大化缓存命中率，进一步提升性能

总结 #

如果不想自己写代码，优先用**std::deque+最后转vector**的方案，简单高效；如果需要更极致的性能，自定义块链表是最优选择；Boost的工具则适合需要保持元素地址稳定或快速替换allocator的场景。

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