C++ 按固定块索引规则重排std::vector的实现方法
实现方案
首先明确重排的核心逻辑:
- 每3个连续元素组成一个不可拆分的基础块,所有块按顺序对应到描述的2列网格布局
- 最终输出顺序为:先按原有先后顺序排列网格左列的所有完整块,再按原有先后顺序排列网格右列的所有完整块,块内元素顺序完全不变
- 整个过程等价于:把所有位置标记为「属于左列块」的元素整体移到向量前部,同时完全保留这部分元素、以及后部元素的原有相对顺序
关键选型说明
- 普通
std::partition不满足要求:它是不稳定分割,只会把满足条件的元素移到前部,不会保证同组元素的原有相对顺序,容易打乱块的排列顺序 std::sort不满足要求:排序算法本身不保留相等元素的原有相对顺序,即便自定义比较器判断块的列归属,也可能打乱同列块的先后次序- 匹配度最高的STL算法是
std::stable_partition:它的行为完全契合需求——将满足分割条件的元素全部移到区间前部,且前部满足条件的元素、后部不满足条件的元素,均保持原有的相对顺序
具体代码实现
首先定义两个可配置参数,适配不同块大小、不同列数的场景:
// 每个基础块包含的元素个数,对应需求里每3个索引为一组 constexpr size_t BLOCK_SIZE = 3; // 整体布局的列数,对应需求里2列的网格结构 constexpr size_t COLUMN_COUNT = 2;
直接对目标向量调用稳定分割算法,lambda谓词仅需判断当前位置的元素是否属于需要前置的左列块:
// vec为待重排的std::vector实例 std::stable_partition(vec.begin(), vec.end(), [&](const auto& elem) { // 通过元素地址计算当前元素在向量中的索引(vector元素连续存储为C++标准保证的行为) const size_t idx = &elem - vec.data(); // 计算当前元素所属的基础块编号 const size_t block_id = idx / BLOCK_SIZE; // 判断当前块是否属于需要前置的第0列组 return block_id % COLUMN_COUNT == 0; });
正确性验证
用给出的18长度向量场景做校验:
- 分割后前置部分的索引顺序为:0、1、2、6、7、8、12、13、14,对应元素值
3,0,2,1,2,2,2,3,0 - 分割后后置部分的索引顺序为:3、4、5、9、10、11、15、16、17,对应元素值
3,2,0,4,5,3,0,2,1 - 拼接后得到的完整向量和给出的预期排序结果完全一致。
扩展适配
如果后续需要支持大于2列的网格布局,只需要逐段调用std::stable_partition即可:
- 先在全区间内,将所有属于第0列的块对应的元素移到最前部
- 记录第一部分结束的位置,在剩余的后半区间内,将所有属于第1列的块对应的元素移到该区间的前部
- 以此类推处理完所有列的块
这种方式不需要手写循环搬移元素,完全复用STL的成熟实现,代码简洁且不易出边界错误。
内容的提问来源于stack exchange,提问作者Megasa3
相关产品推荐
相关产品推荐

