Соответствующий итератор STL для двух массивов

Question

Я хочу отсортировать два массива a и b одного и того же размера следующим образом: Array b упорядочен так же, как сортируется массив a. Пример входных данные:

a = {3, 1, 5} 
b = {2, 6, 4} 

Пример из

a = {1, 3, 5} 
b = {6, 2, 4} 

Такое, что значения Ь не имеют значение для их переупорядочений, но вместо того, чтобы следовать за переупорядочением массива.

Я хочу использовать stl :: sort для этого, и мне нужно сделать это как можно эффективнее. Поэтому я не хочу копировать все элементы в структуры или заказывать массив с индексом, который впоследствии я мог использовать для упорядочения массивов a и b. То, что, по моему мнению, было наименее затратным, должно быть RandomAccessIterator (так как сортировка требует произвольного доступа). Теперь моя проблема в том, что я действительно не так хорош в C++. Если бы кто-то мог дать мне подсказки на уровне, который мог бы понять, я был бы в восторге. Я нашел несколько решений:

Sorting two corresponding arrays, но оба предложенных решения не кажется достаточно производительными,

http://www.stanford.edu/~dgleich/notebook/2006/03/sorting_two_arrays_simultaneou.html который использует материал наддува, который я предполагаю, что перерывы в соответствии с СТЛ (также если честно, я не понимаю все там, где используется шаблон, у меня есть двойной и массив int и размер n для обоих, поэтому я не думаю, что мне нужны шаблоны), и, наконец, это

http://www.c-plusplus.de/forum/313698-full решение, где я застрял в точке, не знаю, как реализовать operator-> и operator *, поскольку я не знаю, могу ли я вернуть только одно значение (значение из массива a), т.е. если это значение используется только для c omparison или также для присвоения значений. также решение в этом потоке сравнивает значения указателя для операторов сравнения, которые я не уверен в правильности (не должны ли это значения за указателями?).

Вот что я до сих пор, если вы видите ужасную Noob ошибка пожалуйста скажи мне, где я пошло не так :)

#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», «reference» и «pointer», которые я только что скопировал здесь http://www.c-plusplus.de/forum/313698-full, какими они должны быть?

Answer 1

Если я вас правильно понял у вас есть этот случай:

[a1][a2][a3]....[an] 
[b1][b2][b3]....[bn] 

Вы хотите сортировать массив а, оба из этих массивов таким же образом, так что результат:

[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 <, которые смогут назначать элементы ваших двух массивов и сравнивать только элементы одного массива.

[UPDATE]

Хорошие новости: Я сделал рабочий пример: ideone

Answer 2

Я немного запутался ваш вопрос, но так как вы связаны с this вопрос, я полагаю, вы пытаясь решить ту же проблему, что и вы, чтобы отсортировать массив a и хотите, чтобы индексы массива b были перегруппированы так же, как и для a.

Звучит так, как будто это может быть XY Problem. Если это вообще возможно, переработайте свой код, чтобы у вас не было parallel arrays. Вместо этого поместите каждый элемент a с соответствующим элементом b в класс или std::pair, поместите те в коллекцию, такую ​​как массив или вектор, и сортируйте (возможно, перегружая операторов сравнения, если необходимо).