通过一次调用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屋!