在 C++ 中按代理排序(或:按一个容器的内容对另一个容器进行排序)
我有一组数据,分为两个数组(我们称它们为 data
和 keys
)。也就是说,对于任何具有索引 i
的给定项目,我可以使用 data[i]
访问该项目的数据,并使用 keys 访问该项目的键[i]
。我无法更改此结构(例如,将键和数据交错到单个数组中),因为我需要将 data
数组传递给需要特定数据布局的库函数。
如何根据 keys
数组的内容对两个数组进行排序(最好使用标准库函数)?
I have a set of data which is split into two arrays (let's call them data
and keys
). That is, for any given item with an index i
, I can access the data for that item with data[i]
and the key for that item with keys[i]
. I cannot change this structure (eg, to interleave keys and data into a single array), because I need to pass the data
array to a library function which expects a certain data layout.
How can I sort both arrays (preferably using standard library functions) according to the content of the keys
array?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(8)
创建一个包含两个数组索引的对象向量。为该对象定义
operator<
以基于keys[index]
进行比较。对该向量进行排序。完成后,遍历该向量并将原始对象放入这些代理对象定义的顺序中:Create a vector of objects that contain indices to the two arrays. Define
operator<
for that object to do the comparison based onkeys[index]
. Sort that vector. When you're done, walk through that vector and put your original objects into the order defined by those proxy objects:下面是一个示例实现,它定义了一个新的迭代器类型以提供两个序列的配对视图。我试图使其符合标准且正确,但由于 C++ 标准的细节极其复杂,我几乎可以肯定我失败了。
我想说,当使用
clang++
或构建时,此代码似乎可以工作g++.
.不建议将此代码用于一般用途,因为它比其他答案更长且更难理解,并且可能会调用可怕的“未定义行为”。
但是,它确实具有恒定的时间和空间开销的优点,因为它提供了现有数据的视图,而不是实际构建临时的替代表示或排列向量。这段代码最明显的(对我来说)性能问题是在交换操作期间必须复制两个容器的各个元素。尽管进行了多次尝试,我还没有找到一种方法来成功地专门化
std::swap
,使得std::sort
或std::random_shuffle
将避免使用默认的基于临时副本的交换实现。使用 C++0x 右值参考系统(请参阅 std::move 和 Jon Purdy 的答案)可能可以解决此问题。Here is a sample implementation which defines a new iterator type to provide a paired view over two sequences. I have tried to make it standards compliant and correct, but since the C++ standard is hideously complex in its details, I am almost certain that I have failed.
I will say that this code appears to work when built with
clang++
org++
.This code is not recommended for general use, since it is longer and less understandable than the other answers, and possibly invokes the dreaded 'undefined behaviour'.
However, it does have the advantage of constant time and space overhead since it provides a view on existing data rather than actually building a temporary alternate representation or permutation vector. The most obvious (to me) performance problem with this code is that individual elements of the two containers will have to be copied during the swap operation. Despite several attempts, I have not found a way to successfully specialise
std::swap
such thatstd::sort
orstd::random_shuffle
will avoid using the default temporary-copy based swap implementation. It is possible that use of the C++0x rvalue reference system (seestd::move
and Jon Purdy's answer) could solve this.您可以使用地图:
这是输出:
You could use a map:
Here's the output:
您可以使用函子进行排序,例如:
You can use functors to do the sorting, for example:
这个问题确实引起了我的思考。我想出了一个解决方案,它利用一些 C++0x 功能来获得非常类似于 STL 的
parallel_sort
算法。为了“就地”执行排序,我必须编写一个back_remove_iterator
作为back_insert_iterator
的对应项,以允许算法读取和写入同一容器。您可以跳过这些部分,直接进入有趣的内容。我还没有对它进行任何硬核测试,但它在时间和空间上似乎都相当高效,主要是由于使用
std::move()
来防止不必要的复制。我希望这被证明是有用的,或者至少是有趣的。
This problem really got me thinking. I came up with a solution that makes use of some C++0x features to get a very STL-like
parallel_sort
algorithm. In order to perform the sort "in-place", I had to write aback_remove_iterator
as the counterpart ofback_insert_iterator
to allow the algorithm to read from and write to the same container. You can skip over those parts and go straight to the interesting stuff.I haven't put it through any hardcore testing, but it seems reasonably efficient in both time and space, principally due to the use of
std::move()
to prevent unnecessary copying.I hope this proves useful, or at least entertaining.
事实证明,Boost 包含一个迭代器,它的作用几乎与 我的其他答案是:
Boost.Iterator Zip Iterator
这似乎是最好的选择。
It turns out that Boost contains an iterator which does pretty much what the
paired_iterator
from my other answer does:Boost.Iterator Zip Iterator
This seems like the best option.
不幸的是,“标记为正确”的答案不起作用,或者至少没有困难。这是因为 boost zip 迭代器仅建模一个可读迭代器。然而,要使用 std::sort 或 boost::sort 迭代器也需要可写。有关详细信息,请参阅 https://stackoverflow.com/a/9343991。
The "marked as correct" answer unfortunately does not work or at least not without difficulties. That is due to the fact that the boost zip iterator models only a readable iterator. To use std::sort or boost::sort the iterator however also needs to be writable. See https://stackoverflow.com/a/9343991 for details.
我不知道以下利用了解
std::swap
实现细节是否是 UB 。我认为“不”。I don't know whether following exploitation of knowing of
std::swap
implementation details is UB or not. I think "no".