通过一次调用sort（）对两个数组进行排序？ [英] Sorting two arrays with one call to sort()?
问题描述
我有两个独立的数组A和B.比较函数只有
取决于A中的元素（键在A中），
但是swap（）函数不仅需要交换A [i]，A [j]，还要交换
B [i]，B [j];每当它交换A [i]，A [j]。
这可以使用C ++的内部sort（）来完成吗？如果没有，那么实现这一目标的最简单方法是什么？速度是
至关重要...复制/合并阵列是没有问题...
谢谢非常适合你的帮助。
-
[见 http://www.gotw.ca/resources/clcm.htm 有关的信息]
[comp.lang.c ++。moderated。第一次海报：做到这一点！ ]
" John" < we ********** @ yahoo.comwrote in message
news：11 ******************** **@g4g2000hsf.googlegro ups.com ...
>
我有两个独立的数组A和B.比较功能只有
取决于A中的元素（键在A中），
但是swap（）函数不仅需要交换A [i]，A [j]，还要
B [i]，B [j];每当它交换A [i]，A [j]。
这可以使用C ++的内部sort（）来完成吗？如果没有，那么实现这一目标的最简单方法是什么？速度是最重要的
...复制/合并数组是没有的。
问题...
为什么不是地图？ std :: map< A，B>
这不能解决你所有的问题吗？
-
[见 http://www.gotw.ca/resources/clcm.htm 获取信息关于]
[comp.lang.c ++。主持。第一次海报：做到这一点！ ]
John写道：
我有两个独立的数组A和B.只有函数
取决于A中的元素（键在A中），
但是swap（）函数不仅需要交换A [i]，A [j] ，还有
B [i]，B [j];每当它交换A [i]，A [j]。
这可以使用C ++的内部sort（）来完成吗？
我希望如此，因为STL的要点是从数据结构中分离算法
。这样的事情应该有效：
struct double_iterator {
T * const a; U * const b; size_t i;
struct ref {
T&磷; U&安培; q;
ref（T& p，U& q）：p（p），q（q）{}
};
ref operator *（）{return ref（a [i]，b [i]）; }
// ...
};
inline void operator =（ref x，ref y）{xp = yp; x.q = y.q; } $ / $
内联bool运算符<（ref x，ref y）{return x.p< y.p; }
// ...
std :: sort（double_iterator（A，B，0），double_iterator（A，B，大小））;
我认为如果你有一个像样的
编译器，这将和手动编码排序一样高效。
- 本
-
[见 http://www.gotw.ca/resources/clcm.htm 有关的信息]
[comp.lang .C ++。主持。第一次海报：做到这一点！ ]
2007年9月22日星期六，John< weekender_ny-AT-yahoo.com写道：
< blockquote class =post_quotes>
我有两个独立的数组A和B.比较函数只有
取决于A中的元素（键在A中），
但是swap（）函数不仅需要交换A [i]，A [j]，还要交换
B [i]，B [j];每当它交换A [i]，A [j]。
这可以使用C ++的内部sort（）来完成吗？如果没有，那么实现这一目标的最简单方法是什么？速度是最重要的
...复制/合并数组是没有的。
问题...
你或许可以使用boost :: zip_iterator
（ http://boost.org/libs/iterator/doc/zip_iterator.html ）
根据您的STL实施细节，因为zip_iterator的引用类型是一个代理，并且
当前的C ++标准不需要代理引用就可以运行，因此可能会遇到问题。\\ / $
但是，几个STL实现* do *使用代理引用
（下一个标准确实要求它们工作）。可能性是
，如果代码编译，它也会给出正确的结果 - 但是你应该通过测试来验证它。
HTH，
-
Dave Abrahams
提升咨询
http://www.boost-consulting.com
Astoria研讨会== http://www.astoriaseminar.com
[见 http://www.gotw.ca/resources/ clcm.htm 有关的信息]
[comp.lang.c ++。moderated。第一次海报：做到这一点！ ]
I have two separate arrays A and B. The comparison function only
depends on elements in A (keys are in A),
but the swap() function needs to swap not only A[i],A[j], but also
B[i],B[j] ; whenever it swaps A[i],A[j].
Can this be done using internal sort() of C++? If not, what is the
easiest way to accomplish this. Speed is
of paramount importance...copying/merging the arrays is out of
question...
Thanks a lot for your help.
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
"John" <we**********@yahoo.comwrote in message
news:11**********************@g4g2000hsf.googlegro ups.com...>
I have two separate arrays A and B. The comparison function only
depends on elements in A (keys are in A),
but the swap() function needs to swap not only A[i],A[j], but also
B[i],B[j] ; whenever it swaps A[i],A[j].
Can this be done using internal sort() of C++? If not, what is the
easiest way to accomplish this. Speed is
of paramount importance...copying/merging the arrays is out of
question...Why isn''t it a map? std::map<A, B>
Wouldn''t that solve all your problems?
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
John wrote:I have two separate arrays A and B. The comparison function only
depends on elements in A (keys are in A),
but the swap() function needs to swap not only A[i],A[j], but also
B[i],B[j] ; whenever it swaps A[i],A[j].
Can this be done using internal sort() of C++?I should hope so, since the main point of the STL is to decouple algorithms
from data structures. Something like this ought to work:
struct double_iterator {
T* const a; U* const b; size_t i;
struct ref {
T& p; U& q;
ref(T& p, U& q) : p(p), q(q) {}
};
ref operator*() { return ref(a[i], b[i]); }
// ...
};
inline void operator=(ref x, ref y) { x.p = y.p; x.q = y.q; }
inline bool operator<(ref x, ref y) { return x.p < y.p; }
// ...
std::sort(double_iterator(A,B,0), double_iterator(A,B,size));
I think this will be as efficient as a hand-coded sort if you have a decent
compiler.
-- Ben
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
on Sat Sep 22 2007, John <weekender_ny-AT-yahoo.comwrote:
I have two separate arrays A and B. The comparison function only
depends on elements in A (keys are in A),
but the swap() function needs to swap not only A[i],A[j], but also
B[i],B[j] ; whenever it swaps A[i],A[j].
Can this be done using internal sort() of C++? If not, what is the
easiest way to accomplish this. Speed is
of paramount importance...copying/merging the arrays is out of
question...You might be able to use boost::zip_iterator for this
(http://boost.org/libs/iterator/doc/zip_iterator.html)
Depending on details of your STL implementation, you may run into
trouble because zip_iterator''s reference type is a proxy, and the
current C++ standard does not require proxy references to work.
However, several STL implementations *do* work with proxy references
(and the next standard does require them to work). The likelihood is
that if the code compiles, it will also give correct results -- but
you should verify that by testing.
HTH,
--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com
The Astoria Seminar ==http://www.astoriaseminar.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
这篇关于通过一次调用sort（）对两个数组进行排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
