是否有一种 C++ 标准方法可以同时划分两个元素范围并根据第一个元素范围的划分来划分第二个元素范围？与 std::partition 一样，分区对一个元素范围进行操作，而另一范围的元素也以相同的方式进行分区。或者是否有一种有效的方法可以做到这一点，而无需复制和调整 std::partition 方法并且无需压缩两个范围？
示例:
[a, b, c, d, e] -> [a, c, e, b, d]
[f, g, h, i, j] -> [f, h, j, g, i]
最佳答案
虽然我现在没有时间详细编写代码，但我有以下想法。从我在 std::{stable_}partition 的文档中可以看到，它绝不会向客户端报告其执行的交换。因此，您无法提取该信息并将其应用于第二个范围。任何依赖于比较和手动重新排序元素的操作都可能太慢。
方法 1(更简单)
我想到了一种更简单的实现方式。上面我声明我们无法从 std::partition 中获得交换。 。嗯，我认为我们可以，但代价是使用一些额外的内存。
- 将前导 vector (一个分区基于一个分区)转换为
std::vector<std::pair<T, int>>. - 一开始，每个标签都等于 vector 中的元素位置。
- 调用
std::partition谓词仅考虑std::pair::first()(即T)。 - 之后
std::partition退出时，按如下方式对第二个 vector 重新排序:前导 vector 中的标记值是第二个 vector 中的元素索引，而前导 vector 的元素索引是新的元素位置。因此，新的排序是已知的，我们可以通过巧妙地执行交换来相应地对第二个 vector 重新排序。
此方法需要额外的内存 O(n)乘以sizeof一个int或者说 char对于短输入 vector 。但是，它很容易实现:只有一个自定义谓词和一个交换循环。
方法 2(更复杂)
基于交换从外部不可见的相同假设，我们可以得出如下解决方案:
将两个范围“粘合”在一起形成一个线性数据结构(可能通过定义代理适配器类)
启动
std::partition对此，使用自定义谓词，它将比较“压缩”DS 中的第一个元素(沿着pair::first()的行)，但由于两个数组现在通过适配器统一，因此交换将发生在两个数组中的元素根据需要移除临时 DS(“取消粘合”两个阵列)
编辑:鉴于 std::partition使用std::swap ，这种方法的关键部分是重新定义 std::swap对于您的配对元素类型(这仍然称为模板的“重载”吗？)。据我所知，这个函数可以为自定义类型重载，这证明可以使用 std::partition 构造像方法 2 中描述的算法。 ，但重新定义交换函数和比较谓词。
关于c++ - 在 C++ 中以相同的方式同时划分两个范围的元素，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35482912/