我想按以下方式对两个相同大小的数组 a 和 b 进行排序:数组 b 的排序方式与数组 a 的排序方式相同。输入示例:
a = {3, 1, 5}
b = {2, 6, 4}
示例
a = {1, 3, 5}
b = {6, 2, 4}
这样 b 的值与其重新排序无关,而是遵循数组 a 的重新排序。
我想使用 STL::sort 来执行此操作,并且我需要尽可能高效地执行此操作。所以我不想将所有元素复制到结构中或使用索引对数组进行排序,之后我可以使用该索引对数组 a 和 b 进行排序。我认为最小的开销应该是 RandomAccessIterator (因为排序需要随机访问)。现在我的问题是,我真的不太擅长 C++。如果有人能给我一些菜鸟可以理解的水平的提示,我会很高兴。我找到了一些解决方案:
Sorting two corresponding arrays ,但是两种提议的解决方案似乎都不够性能,
http://www.stanford.edu/~dgleich/notebook/2006/03/sorting_two_arrays_simultaneou.html它使用了 boost 的东西,我认为这打破了对 STL 的遵守(老实说,我不理解那里使用的所有模板东西,我有一个 double 和一个 int 数组以及两者的大小 n ,所以我认为我不需要模板),最后是这个
http://www.c-plusplus.de/forum/313698-full解决方案,我陷入了这样的境地:我不知道如何实现operator->和operator*,因为我不知道是否只能返回一个值(数组a中的值),即是否使用该值仅用于比较或也用于赋值。此线程中的解决方案还比较比较运算符的指针值,我不确定这是否正确(不应该是指针后面的值吗?)。
这就是我到目前为止所得到的,如果你看到可怕的菜鸟错误,请告诉我哪里错了:)
#include "DoubleArrayRAccIterator.h"
DoubleArrayRAccIterator::~DoubleArrayRAccIterator() {
// TODO Auto-generated destructor stub
}
struct doubleValue{
double* a_val;
int* b_val;
};
double::DoubleArrayRAccIterator::DoubleArrayRAccIterator(double& a_arr,int& b_arr, int size) {
a_begin = &a_arr;
b_begin = &b_arr;
a = &a_arr;
b = & b_arr;
n = size;
}
DoubleArrayRAccIterator::DoubleArrayRAccIterator() {
a = 0;
b = 0;
n = 0;
}
DoubleArrayRAccIterator::DoubleArrayRAccIterator(const DoubleArrayRAccIterator& it) {
a = it.a;
b = it.b;
n = it.n;
}
DoubleArrayRAccIterator& DoubleArrayRAccIterator::operator=(const DoubleArrayRAccIterator& it) {
a = it.a;
b = it.b;
n = it.n;
return *this;
}
DoubleArrayRAccIterator& DoubleArrayRAccIterator::operator++() {
++a;
++b;
return *this;
}
DoubleArrayRAccIterator& DoubleArrayRAccIterator::operator--() {
--a;
--b;
return *this;
}
DoubleArrayRAccIterator DoubleArrayRAccIterator::operator++(int) {
DoubleArrayRAccIterator it(*this);
++a;
++b;
return it;
}
DoubleArrayRAccIterator DoubleArrayRAccIterator::operator--(int) {
--a;
--b;
return *this;
}
DoubleArrayRAccIterator& DoubleArrayRAccIterator::operator+=(diff_type x) {
a += x;
b += x;
return *this;
}
DoubleArrayRAccIterator& DoubleArrayRAccIterator::operator-=(diff_type x) {
a += x;
b += x;
return *this;
}
DoubleArrayRAccIterator DoubleArrayRAccIterator::operator+(diff_type x) const {
a += x;
b += x;
return *this;
}
typename DoubleArrayRAccIterator DoubleArrayRAccIterator::operator-(diff_type x) const {
a -= x;
b -= x;
return *this;
}
DoubleArrayRAccIterator DoubleArrayRAccIterator::operator+(const DoubleArrayRAccIterator& it) const {
a += it.a;
b += it.b;
return *this;
}
DoubleArrayRAccIterator DoubleArrayRAccIterator::operator-(const DoubleArrayRAccIterator& it) const {
a -= it.a;
b -= it.b;
return *this;
}
DoubleArrayRAccIterator::reference DoubleArrayRAccIterator::operator*() const {
// this MUST be wrong, only return value of array a?
doubleValue result;
result.a_val=a;
result.b_val=b;
return *result;
}
DoubleArrayRAccIterator::pointer DoubleArrayRAccIterator::operator->() const {
// this MUST be wrong, only return value of array a?
doubleValue result;
result.a_val=a;
result.b_val=b;
return &result;
}
DoubleArrayRAccIterator::reference DoubleArrayRAccIterator::operator[](diff_type x) const {
// this MUST be wrong, only return value of array a?
doubleValue result;
result.a_val=a_begin+x;
result.b_val=b_begin+x;
return *result;
}
bool DoubleArrayRAccIterator::operator==(const DoubleArrayRAccIterator& it) const {
return a == it.a;
//compare indices or values here?
}
bool DoubleArrayRAccIterator::operator!=(const DoubleArrayRAccIterator& it) const {
return a != it.a;
//compare indices or values here?
}
bool DoubleArrayRAccIterator::operator<(const DoubleArrayRAccIterator& it) const {
//compare indices or values here?
}
bool DoubleArrayRAccIterator::operator>(const DoubleArrayRAccIterator& it) const {
//compare indices or values here?
}
bool DoubleArrayRAccIterator::operator<=(const DoubleArrayRAccIterator& it) const {
//compare indices or values here?
}
bool DoubleArrayRAccIterator::operator>=(const DoubleArrayRAccIterator& it) const {
//compare indices or values here?
}
DoubleArrayRAccIterator begin() {
return DoubleArrayRAccIterator(a_begin, b_begin, n);
}
DoubleArrayRAccIterator end() {
return DoubleArrayRAccIterator(a_begin + n, b_begin + n, n);
}
如果有人还没有停止阅读并且仍然有耐心,我对我刚刚从这里复制的“diff_type”、“引用”和“指针”类型感到困惑 http://www.c-plusplus.de/forum/313698-full ,它们应该是什么?
最佳答案
如果我理解正确的话,你会遇到这种情况:
[a1][a2][a3]....[an]
[b1][b2][b3]....[bn]
你想按数组a排序,这两个数组的排序方式相同,所以结果是:
[ax1][ax2][ax3]....[axn]
[bx1][bx2][bx3]....[bxn]
哪里xi
两个数组的值是相同的。
考虑这个例子:
class SIter {
public:
SIter(int* aIter, double* bIter) : aIter(aIter), bIter(bIter) {}
// we move to next position is just moving both:
SIter& operator ++() {
++aIter; ++bIter;
return *this;
}
SIter operator ++(int) {
SIter rv = *this;
++aIter; ++bIter;
return rv;
}
SIter& operator --() {
--aIter; --bIter;
return *this;
}
SIter operator --(int) {
SIter rv = *this;
--aIter; --bIter;
return rv;
}
SIter operator + (std::ptrdiff_t cc) const
{
SIter rv = *this;
rv.aIter += cc;
rv.bIter += cc;
return rv;
}
SIter operator - (std::ptrdiff_t cc) const
{
SIter rv = *this;
rv.aIter -= cc;
rv.bIter -= cc;
return rv;
}
std::ptrdiff_t operator - (SIter other) const
{
return aIter - other.aIter;
}
struct value_type {
int a; double b;
bool operator < (const value_type& other) const {
return a < other.a; // this is the place where way of sorting is defined!!!!
}
};
struct reference {
int* a;
double* b;
reference& operator = (const value_type& o)
{
*a = o.a;
*b = o.b;
return *this;
}
operator value_type() const {
value_type rv = { *a, *b };
return rv;
}
reference& operator = (const reference& other)
{
*a = *other.a;
*b = *other.b;
return *this;
}
bool operator < (const reference& other) const {
return *a < *other.a;
}
bool operator < (const value_type& other) const {
return *a < other.a;
}
};
reference operator * () {
reference rv = { aIter, bIter };
return rv;
}
bool operator == (const SIter& other) const
{
return aIter == other.aIter; // don't need to compare bIter - shall be in sync
}
bool operator != (const SIter& other) const
{
return aIter != other.aIter; // don't need to compare bIter - shall be in sync
}
bool operator < (const SIter& other) const
{
return aIter < other.aIter; // don't need to compare bIter - shall be in sync
}
// I bet you don't need pointer operator -> ()
typedef std::random_access_iterator_tag iterator_category;
typedef std::ptrdiff_t difference_type;
typedef reference pointer;
private:
int* aIter;
double* bIter;
};
然后像这样使用:
int main() {
int a[100] = {};
double b[100] = {};
SIter beginIter(a, b);
SIter endIter(a + 100, b + 100);
std::sort(beginIter, endIter);
}
我没有尝试过这个,可能它有一些缺点,但你应该朝这个方向走。您的迭代器应包含两个指向数组的指针(更一般的方式 - 指向容器的迭代器),并且您的引用类型应具有 operator =
和operator <
它将能够分配两个数组的元素并仅比较一个数组的元素。
[更新]
好消息:我做了工作示例:ideone
关于c++ - 两个数组的 STL 兼容迭代器,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16018292/