c++ - 在 STL 中使用 void* 作为固定宽度的记录

Question

我有一个包含 N 条记录的连续缓冲区，每条记录 W 字节宽。 两者 N 和 W 在编译时都是未知的。 N*M 是 500mb 的订单。我想在标准 STL 算法中使用它，例如 sort() 或 nth_element()。我手头有一个比较器。是否有任何已经实现的方法来做到这一点？

到目前为止，我想到了两种方法:

1) 使用一个额外的 vector ，用索引 0...N 填充，对其排序(使用自定义比较器)而不是数据，使其类似于排序顺序的数据记录，然后根据该 vector 移动数据记录。缺点:额外的内存，固定数据记录顺序的额外困难，这有点不平凡。

2) 创建一些自定义迭代器(它知道 W)，它将返回一些类似于记录的临时“虚拟”类实例，并为该类重载 swap() 以便它交换内存块。缺点:有些棘手，有些脆弱(需要遵循一些 STL 内部规则，例如知道将使用 swap())。

Answer 1

您的第二个选择——编写自定义迭代器——是一种可行的方法并且效果很好。

您不需要依赖正在使用的 swap:您只需要重载迭代器被取消引用时返回的代理对象的赋值运算符。

(请注意，在 C++11 中，“交换”元素的算法和函数需要使用通过 ADL 找到的 swap 函数。不过，重载赋值运算符仍然更可取，尤其是如果你只是移动字节数组。)

我不知道一般的实现方式，但作为起点，您可以看看 stride_iterator来 self 的一个图书馆(靠近文件底部)。它包装一个字节数组并覆盖算术运算符以一次将迭代器移动 N 个字节，其中 N 仅在运行时已知。