Sắp xếp hai mảng tương ứng

Question

Tôi có mã này ở đây có hai mảng. Nó sắp xếp arr [], sao cho giá trị cao nhất sẽ nằm trong chỉ mục 0. Bây giờ mảng thứ hai arr1 [] chứa chuỗi, tôi muốn mã áp dụng bất kỳ thay đổi nào được thực hiện cho arr [] to arr1 []. Vì vậy, arr [0] sẽ trả về 6, trong khi arr1 [0] sẽ trả về chuỗi "d1". Lưu ý cách "d1" có cùng chỉ mục với ? Sau khi sắp xếp tôi muốn các giá trị tương tự vẫn có các đối tác chuỗi của chúng.

Tôi làm cách nào để thực hiện việc này?

#include <iostream> 
#include <iomanip> 
#include <algorithm> 
#include <functional> 
using namespace std ; 


main(){ 
int arr[ 5 ] = { 4, 1, 3, 6, 2 }; 

string arr1[ 5 ] = { "a1", "b1", "c1", "d1", "e1" }; 

std::sort(arr, arr + 5, std::greater<int>()); 
cout << arr[0] << arr1[0] << endl; 

system("pause"); 
} 

Answer 1

Thay vì sắp xếp các mảng, hãy sắp xếp các chỉ mục. Ví dụ, bạn có

int arr[5]={4,1,3,6,2} 
string arr1[5]={"a1","b1","c1","d1","e1"}; 

và bạn thực hiện

int indices[5]={0,1,2,3,4}; 

bây giờ bạn làm một so sánh chỉ số loại trông như thế này (chỉ và ý tưởng, có thể bạn sẽ phải sửa chữa nó một chút)

class sort_indices 
{ 
    private: 
    int* mparr; 
    public: 
    sort_indices(int* parr) : mparr(parr) {} 
    bool operator()(int i, int j) const { return mparr[i]<mparr[j]; } 
} 

bây giờ bạn có thể sử dụng các loại stl

std::sort(indices, indices+5, sort_indices(arr)); 

khi bạn hoàn tất, mảng chỉ mục sẽ là arr[indices[0]] là phần tử đầu tiên. và tương tự như vậy arr1[indices[0]] là cặp tương ứng.

Đây cũng là một mẹo rất hữu ích khi bạn đang cố gắng sắp xếp một đối tượng dữ liệu lớn, bạn không cần di chuyển dữ liệu xung quanh mỗi lần hoán đổi, chỉ là các chỉ mục.

Answer 2

Bạn cần kết hợp chúng lại với nhau rồi sắp xếp cặp kết hợp và sau đó bỏ kết hợp các cặp.

int arr[ 5 ] = { ... }; 
string arr1[ 5 ] = { ... }; 
pair<int, string> pairs[ 5 ]; 

for (int i = 0; i < 5; ++i) 
    pairs[ i ] = make_pair(arr[ i ], arr1[ i ]); 

sort(pairs.begin(), pairs.end()); 

for (int i = 0; i < 5; ++i) 
{ 
    arr[ i ] = pairs[ i ].first; 
    arr1[ i ] = pairs[ i ].second; 
} 

Thật sự mặc dù, nếu arr và arr1 có liên quan sau đó họ nên được lưu trữ như pair (hoặc ít nhất là một phong tục struct) anyway. Bằng cách đó bạn không cần phải sử dụng nó như một bước trung gian.

Answer 3

Viết trình lặp của riêng bạn và sử dụng STD: sắp xếp. Nó dễ dàng được mã hóa trong ít hơn 50 dòng mà không có thư viện của bên thứ ba. Chức năng hoán đổi rất quan trọng ở đây.

#include <iostream> 
#include <iterator>  // std::iterator, std::input_iterator_tag 
#include <algorithm> 

using namespace std; 

struct Tuple; 
struct RefTuple; 
#define TUPLE_COMMON_FUNC(C, D, E, F)   \ 
    C##::C## (Tuple& t) ##D      \ 
    C##::C## (RefTuple& t) ##D     \ 
    void C##::operator = (Tuple& t) ##E  \ 
    void C##::operator = (RefTuple& t) ##E \ 
    bool C##::operator < (const Tuple& t) const ##F  \ 
    bool C##::operator < (const RefTuple& t) const ##F 
#define ASSIGN_1 : i(t.i), j(t.j), s(t.s) {} 
#define ASSIGN_2 { i = t.i; j = t.j; s = t.s; } 
#define SORT_CRITERIA \ 
    return (j < t.j) || (j == t.j && (i < t.i)); 
struct Tuple { 
    int i, j, s; 
    TUPLE_COMMON_FUNC(Tuple, ; , ; , ;) 
}; 
struct RefTuple { 
    int &i, &j, &s; 
    RefTuple(int &x, int &y, int &z): i(x), j(y), s(z) {} 
    TUPLE_COMMON_FUNC(RefTuple, ; , ; , ;) 
}; 
TUPLE_COMMON_FUNC(Tuple, ASSIGN_1, ASSIGN_2, {SORT_CRITERIA}) 
TUPLE_COMMON_FUNC(RefTuple, ASSIGN_1, ASSIGN_2, {SORT_CRITERIA}) 

void swap(RefTuple& t1, RefTuple& t2) { 
    t1.i ^= t2.i; t2.i ^= t1.i; t1.i ^= t2.i; 
    t1.j ^= t2.j; t2.j ^= t1.j; t1.j ^= t2.j; 
    t1.s ^= t2.s; t2.s ^= t1.s; t1.s ^= t2.s; 
} 

class IterTuple : public iterator<random_access_iterator_tag, Tuple> { 
    int *i, *j, *s, idx; 
public: 
    IterTuple(int* x, int*y, int* z, int l) : i(x), j(y), s(z), idx(l) {} 
    IterTuple(const IterTuple& e) : i(e.i), j(e.j), s(e.s), idx(e.idx) {} 
    RefTuple operator*() { return RefTuple(i[idx], j[idx], s[idx]); } 
    IterTuple& operator ++() { idx++; return *this; } 
    IterTuple& operator --() { idx--; return *this; } 
    IterTuple operator ++ (int) { IterTuple tmp(*this); idx++; return tmp; } 
    IterTuple operator -- (int) { IterTuple tmp(*this); idx--; return tmp; } 
    int operator - (IterTuple& rhs) { return idx - rhs.idx; } 
    IterTuple operator + (int n) { IterTuple tmp(*this); tmp.idx += n; return tmp; } 
    IterTuple operator - (int n) { IterTuple tmp(*this); tmp.idx -= n; return tmp; } 
    bool operator==(const IterTuple& rhs) {  return idx == rhs.idx; } 
    bool operator!=(const IterTuple& rhs) {  return idx != rhs.idx; } 
    bool operator<(IterTuple& rhs) {  return idx < rhs.idx; } 
}; 

int Ai[10] = {0, 0, 2, 3, 2, 4, 1, 1, 4, 2}; 
int Aj[10] = {0, 2, 3, 4, 4, 4, 0, 1, 0, 2}; 
int Ax[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 

int main() { 
    IterTuple from(Ai, Aj, Ax, 0); 
    IterTuple until(Ai, Aj, Ax, 10); 

    sort(from, until); 

    for (IterTuple it = from; it != until; it++) 
     cout << (*it).i << ' ' << (*it).j << ' ' << (*it).s << '\n'; 

    return 0; 
}