[c++] Как я могу сортировать два вектора одинаково, с критериями, которые используют только один из векторов?


2 Answers

Сортировка на месте с использованием перестановки

Я бы использовал такую ​​перестановку, как Timothy, хотя, если ваши данные слишком велики, и вы не хотите выделять больше памяти для отсортированного вектора, вы должны сделать это на месте . Ниже приведен пример сортировки места на основе O (n) (линейной сложности) с использованием перестановки :

Хитрость заключается в том, чтобы получить перестановку и обратную перестановку, чтобы знать, куда помещать данные, перезаписанные на последнем этапе сортировки.

template <class K, class T> 
void sortByKey(K * keys, T * data, size_t size){
    std::vector<size_t> p(size,0);
    std::vector<size_t> rp(size);
    std::vector<bool> sorted(size, false);
    size_t i = 0;

    // Sort
    std::iota(p.begin(), p.end(), 0);
    std::sort(p.begin(), p.end(),
                    [&](size_t i, size_t j){ return keys[i] < keys[j]; });

    // ----------- Apply permutation in-place ---------- //

    // Get reverse permutation item>position
    for (i = 0; i < size; ++i){
        rp[p[i]] = i;
    }

    i = 0;
    K savedKey;
    T savedData;
    while ( i < size){
        size_t pos = i;
        // Save This element;
        if ( ! sorted[pos] ){
            savedKey = keys[p[pos]];
            savedData = data[p[pos]];
        }
        while ( ! sorted[pos] ){
            // Hold item to be replaced
            K heldKey  = keys[pos];
            T heldData = data[pos];
            // Save where it should go
            size_t heldPos = rp[pos];

            // Replace 
            keys[pos] = savedKey;
            data[pos] = savedData;

            // Get last item to be the pivot
            savedKey = heldKey;
            savedData = heldData;

            // Mark this item as sorted
            sorted[pos] = true;

            // Go to the held item proper location
            pos = heldPos;
        }
        ++i;
    }
}
Question

Как я могу сортировать два вектора одинаково, с критериями, которые используют только один из векторов?

Например, предположим, что у меня два вектора одинакового размера:

vector<MyObject> vectorA;
vector<int> vectorB;

Затем я сортирую vectorA используя некоторую функцию сравнения. Этот сортировка переупорядочивает vectorA . Как я могу применить одно и то же переупорядочение к vectorB ?

Один из вариантов - создать структуру:

struct ExampleStruct {
    MyObject mo;
    int i;
};

а затем отсортировать вектор, содержащий содержимое vectorA и vectorB в один вектор:

// vectorC[i] is vectorA[i] and vectorB[i] combined
vector<ExampleStruct> vectorC;

Это не похоже на идеальное решение. Существуют ли другие варианты, особенно в C ++ 11?




  1. Сделайте вектор пар из ваших отдельных векторов.
    инициализировать вектор пар
    Добавление к вектору пары

  2. Создайте собственный компаратор сортировки:
    Сортировка вектора пользовательских объектов
    http://rosettacode.org/wiki/Sort_using_a_custom_comparator#C.2B.2B

  3. Сортируйте свой вектор пар.

  4. Отделите свой вектор пар на отдельные векторы.

  5. Поместите все это в функцию.

Код:

std::vector<MyObject> vectorA;
std::vector<int> vectorB;

struct less_than_int
{
    inline bool operator() (const std::pair<MyObject,int>& a, const std::pair<MyObject,int>& b)
    {
        return (a.second < b.second);
    }
};

sortVecPair(vectorA, vectorB, less_than_int());

// make sure vectorA and vectorB are of the same size, before calling function
template <typename T, typename R, typename Compare>
sortVecPair(std::vector<T>& vecA, std::vector<R>& vecB, Compare cmp)
{

    std::vector<pair<T,R>> vecC;
    vecC.reserve(vecA.size());
    for(int i=0; i<vecA.size(); i++)
     {
        vecC.push_back(std::make_pair(vecA[i],vecB[i]);   
     }

    std::sort(vecC.begin(), vecC.end(), cmp);

    vecA.clear();
    vecB.clear();
    vecA.reserve(vecC.size());
    vecB.reserve(vecC.size());
    for(int i=0; i<vecC.size(); i++)
     {
        vecA.push_back(vecC[i].first);
        vecB.push_back(vecC[i].second);
     }
}



Я не уверен, что это работает, но я бы использовал что-то вроде этого. Например, чтобы отсортировать два вектора, я бы использовал метод сортировки пузырьков спуска и векторные пары.

Для нисходящей сортировки пузырьков, я бы создал функцию, которая требует векторную пару.

void bubbleSort(vector< pair<MyObject,int> >& a)
{
    bool swapp = true;
    while (swapp) {
        int key;
        MyObject temp_obj;
        swapp = false;
        for (size_t i = 0; i < a.size() - 1; i++) {
            if (a[i].first < a[i + 1].first) {
                temp_obj = a[i].first;
                key = a[i].second;

                a[i].first = a[i + 1].first;
                a[i + 1].first = temp_obj;

                a[i].second = a[i + 1].second;
                a[i + 1].second = key;

                swapp = true;
            }
        }
    }
}

После этого я поместил бы ваши 2 векторных значения в одну пару векторов. Если вы можете одновременно добавить значения, используйте эту функцию, а затем вызовите функцию сортировки пузырьков.

vector< pair<MyObject,int> > my_vector;

my_vector.push_back( pair<MyObject,int> (object_value,int_value));

bubbleSort(my_vector);

Если вы хотите использовать значения после добавления к вашим 2 векторам, вы можете использовать эту функцию, а затем вызвать функцию сортировки пузырьков.

vector< pair<MyObject,int> > temp_vector;

for (size_t i = 0; i < vectorA.size(); i++) {
            temp_vector.push_back(pair<MyObject,int> (vectorA[i],vectorB[i]));
        }

bubbleSort(temp_vector);

Надеюсь, это поможет. С уважением, Caner






Related



Tags

c++ c++   c++11