С++ STL: пользовательская сортировка одного вектора на основе содержимого другого

Ответ 1

Вместо создания двух отдельных векторов/списков обычным способом справиться с этим является создание единого вектора/списка объектов, которые включают имена и возрасты:

struct person { 
    std::string name;
    int age;
};

Чтобы получить сортировку по возрасту, определите компаратор, который смотрит на возраст:

struct by_age { 
    bool operator()(person const &a, person const &b) { 
        return a.age < b.age;
    }
};

Тогда ваш вид будет выглядеть примерно так:

std::vector<person> people;
// code to put data into people goes here.

std::sort(people.begin(), people.end(), by_age());

Изменить. Что касается выбора между определением operator< для класса или использованием отдельного объекта-компаратора, как я уже говорил выше, это в основном вопрос о том, существует ли один порядок, "очевидный" для этого класса.

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

Ответ 2

Как отмечали другие, вы должны рассмотреть вопрос о группировании людей и возрастов.

Если вы не можете/не хотите, вы можете создать для них "индекс" и вместо этого отсортировать этот индекс. Например:

// Warning: Not tested
struct CompareAge : std::binary_function<size_t, size_t, bool>
{
    CompareAge(const std::vector<unsigned int>& Ages)
    : m_Ages(Ages)
    {}

    bool operator()(size_t Lhs, size_t Rhs)const
    {
        return m_Ages[Lhs] < m_Ages[Rhs];
    }

    const std::vector<unsigned int>& m_Ages;
};

std::vector<std::string> people = ...;
std::vector<unsigned int> ages = ...;

// Initialize a vector of indices
assert(people.size() == ages.size());
std::vector<size_t> pos(people.size());
for (size_t i = 0; i != pos.size(); ++i){
    pos[i] = i;
}


// Sort the indices
std::sort(pos.begin(), pos.end(), CompareAge(ages));

Теперь имя n-го человека people[pos[n]], а его возраст ages[pos[n]]

Ответ 3

Как правило, вы не ставите данные, которые хотите сохранить вместе в разных контейнерах. Создайте struct/class для Person и перегрузите operator<.

struct Person
{
    std::string name;
    int age;
}

bool operator< (const Person& a, const Person& b);

Или, если это какая-то отброшенная вещь:

typedef std::pair<int, std::string> Person;
std::vector<Person> persons;
std::sort(persons.begin(), persons.end());

std::pair уже реализуют операторы сравнения.

Ответ 4

Не имеет смысла держать их в двух отдельных структурах данных: если вы переупорядочиваете People, у вас больше нет разумного отображения на Ages.

template<class A, class B, class CA = std::less<A>, class CB = std::less<B> >
struct lessByPairSecond
    : std::binary_function<std::pair<A, B>, std::pair<A, B>, bool>
{
    bool operator()(const std::pair<A, B> &left, const std::pair<A, B> &right) {
        if (CB()(left.second, right.second)) return true;
        if (CB()(right.second, left.second)) return false;
        return CA()(left.first, right.first);
    }
};

std::vector<std::pair<std::string, int> > peopleAndAges;
peopleAndAges.push_back(std::pair<std::string, int>("Anne", 23));
peopleAndAges.push_back(std::pair<std::string, int>("Bob", 23));
peopleAndAges.push_back(std::pair<std::string, int>("Charlie", 23));
peopleAndAges.push_back(std::pair<std::string, int>("Douglas", 23));
std::sort(peopleAndAges.begin(), peopleAndAges.end(),
        lessByPairSecond<std::string, int>());

Ответ 5

Я бы предложил объединить эти два списка в один список структур. Таким образом вы можете просто определить operator < как dirkgently said.

Ответ 6

Ответ Джерри Коффина был полностью ясным и правильным.

У меня есть связанная проблема, которая может дать хорошее обсуждение этой теме...:)

Мне пришлось переупорядочить столбцы объекта-матрицы (например, TMatrix <T> ) на основе сортировки вектора (например, sequence)... TMatrix <T> не предоставляет ссылочный доступ к ним в строках (поэтому я не могу создать структуру, чтобы переупорядочить его...), но удобно предоставляет метод TMatrix <T> :: swap (row1, row2)...

Итак, код:

TMatrix<double> matrix;
vector<double> sequence;
// 
// 1st step: gets indexes of the matrix rows changes in order to sort by time
//
// note: sorter vector will have 'sorted vector elements' on 'first' and 
// 'original indexes of vector elements' on 'second'...
//
const int n = int(sequence.size());
std::vector<std::pair<T, int>> sorter(n);
for(int i = 0; i < n; i++) {
    std::pair<T, int> ae;
    ae.first = sequence[i]; 
    ae.second = i;              
    sorter[i] = ae;
}           
std::sort(sorter.begin(), sorter.end());

//
// 2nd step: swap matrix rows based on sorter information
//
for(int i = 0; i < n; i++) {
    // updates the the time vector
    sequence[i] = sorter[i].first;
    // check if the any row should swap
    const int pivot = sorter[i].second;
    if (i != pivot) {
        //
        // store the required swaps on stack
        //
        stack<std::pair<int, int>> swaps;
        int source = pivot;
        int destination = i;
        while(destination != pivot) {
            // store required swaps until final destination 
            // is equals to first source (pivot)
            std::pair<int, int> ae;
            ae.first = source;
            ae.second = destination;
            swaps.push(ae);
            // retrieves the next requiret swap
            source = destination;
            for(int j = 0; j < n; j++) {
                if (sorter[j].second == source) 
                    destination = j;
                    break;
                }
            }
        }                   
        //
        // final step: execute required swaps
        //
        while(!swaps.empty()) {
            // pop the swap entry from the stack
            std::pair<int, int> swap = swaps.top();
            destination = swap.second;                      
            swaps.pop();
            // swap matrix coluns
            matrix.swap(swap.first, destination);
            // updates the sorter
            sorter[destination].second = destination;
        }
        // updates sorter on pivot
        sorter[pivot].second = pivot;
    }
}

Я считаю, что все еще O (n log n), поскольку каждая строка, которая не находится на месте, будет меняться только один раз...

Удачи!:)