位图排序适用于整数范围已知且密集的场景，如[0, 1000000)内去重排序；本质是用bit数组标记存在性，不支持负数、超大范围或稀疏分布。
位图排序适合什么场景
位图排序只适用于整数范围已知且密集的场景，比如对 [0, 1000000) 内的整数去重并排序。它本质不是“排序算法”，而是用内存换时间的标记法：用一个 bit 数组记录某个值是否出现过。一旦输入含负数、超大范围（如 int64_t）、或稀疏分布（比如只有 100 个数却横跨 [0, 2^32)），位图就立刻失效或爆内存。
如何用 std::vector<bool></bool> 实现基础位图
std::vector<bool></bool> 是 C++ 标准库中空间最优的位容器，但要注意它不是真正的 vector，而是特化实现，不支持 & 取地址，也不能直接用 data() 拿原始指针。实际使用时推荐封装一层：
void bitmap_sort(std::vector<int>& arr) {
if (arr.empty()) return;
int min_val = *std::min_element(arr.begin(), arr.end());
int max_val = *std::max_element(arr.begin(), arr.end());
if (min_val < 0) throw std::runtime_error("negative not supported");
size_t size = max_val + 1;
std::vector<bool> bitmap(size, false);
for (int x : arr) bitmap[x] = true;
arr.clear();
for (size_t i = 0; i < size; ++i)
if (bitmap[i]) arr.push_back(static_cast<int>(i));
}关键点：
- 必须先检查
min_val < 0，否则访问bitmap[x]会越界 - 数组大小是
max_val + 1，不是max_val - min_val + 1（除非你做偏移映射） - 不能用
bitmap.data()做位运算优化——std::vector<bool></bool>不提供裸指针
手动管理 uint32_t* 位图提升性能
当数据范围固定（比如 [0, 1000000)），且需要极致性能时，可手写位操作：
立即学习“C++免费学习笔记（深入）”；
class FixedBitmap {
uint32_t* bits_;
size_t n_words_;
public:
explicit FixedBitmap(size_t max_n) : n_words_((max_n + 31) / 32),
bits_(new uint32_t[n_words_] {}) {}
~FixedBitmap() { delete[] bits_; }
void set(size_t i) { bits_[i / 32] |= (1U << (i % 32)); }
bool test(size_t i) const { return bits_[i / 32] & (1U << (i % 32)); }
};注意：
- 位索引
i必须保证< max_n，否则bits_[i / 32]越界 -
1U << (i % 32)中的U很关键，避免左移超过int位宽引发未定义行为 - 不能用
std::bitset替代——它的大小必须编译期确定，无法适配运行时最大值
位图排序的常见误用和坑
很多人把位图当成通用排序替代品，结果栽在几个细节上：
- 输入含重复元素？位图天然去重，如果业务要求保留重复，就不能直接用——得改用计数数组（
std::vector<size_t>） - 用
std::vector<bool>初始化过大（如1e9），可能分配失败或卡死，C++ 不抛异常而是直接 abort - 32 位系统下
max_val接近INT_MAX，max_val + 1会溢出为负数，导致vector构造崩溃 - 没清空原数组就重填，残留旧值；或没 resize 就直接索引写入，触发 undefined behavior
位图排序真正省的是比较开销，代价是内存和适用范围——它不是“简单”，而是“约束极强”。用之前，先确认你的数据真的落在那个小方框里。
