You need to enable JavaScript to run this app. C++ 按固定块索引规则重排std::vector的实现方法
优惠活动
大模型
产品
解决方案
定价
更多

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即可:

  1. 先在全区间内,将所有属于第0列的块对应的元素移到最前部
  2. 记录第一部分结束的位置,在剩余的后半区间内,将所有属于第1列的块对应的元素移到该区间的前部
  3. 以此类推处理完所有列的块
    这种方式不需要手写循环搬移元素,完全复用STL的成熟实现,代码简洁且不易出边界错误。

内容的提问来源于stack exchange,提问作者Megasa3

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.31 06:27:08