Intereting Posts

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

Это, вероятно, лучше всего указано в качестве примера. У меня есть два вектора / списки:

People = {Anne, Bob, Charlie, Douglas} Ages = {23, 28, 25, 21} 

Я хочу сортировать Люди по их возрасту, используя что-то вроде sort(People.begin(), People.end(), CustomComparator) , но я не знаю, как написать CustomComparator чтобы посмотреть на Ages, а не на People.

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

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

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

 std::sort(people.begin(), people.end(), [](auto const &a, auto const &b) { return a.age < b.age; }); 

В более раннем C ++ (pre C ++ 11, поэтому без lambda-выражений) вы можете определить сравнение как членную перегрузку operator< или else как объект-функция (объект, который перегружает operator() ) для сравнения:

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

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

 std::vector people; // code to put data into people goes here. std::sort(people.begin(), people.end(), by_age()); 

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

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

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

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

 // Warning: Not tested struct CompareAge : std::binary_function { CompareAge(const std::vector& Ages) : m_Ages(Ages) {} bool operator()(size_t Lhs, size_t Rhs)const { return m_Ages[Lhs] < m_Ages[Rhs]; } const std::vector& m_Ages; }; std::vector people = ...; std::vector ages = ...; // Initialize a vector of indices assert(people.size() == ages.size()); std::vector 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]]

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

 struct Person { std::string name; int age; } bool operator< (const Person& a, const Person& b); 

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

 typedef std::pair Person; std::vector persons; std::sort(persons.begin(), persons.end()); 

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

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

 template, class CB = std::less > struct lessByPairSecond : std::binary_function, std::pair, bool> { bool operator()(const std::pair &left, const std::pair &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 > peopleAndAges; peopleAndAges.push_back(std::pair("Anne", 23)); peopleAndAges.push_back(std::pair("Bob", 23)); peopleAndAges.push_back(std::pair("Charlie", 23)); peopleAndAges.push_back(std::pair("Douglas", 23)); std::sort(peopleAndAges.begin(), peopleAndAges.end(), lessByPairSecond()); 

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

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

Просто есть связанная с этим проблема, которая может дать хорошее обсуждение этой теме … 🙂

Мне пришлось переупорядочить столбцы матричного объекта (скажем, TMatrix ) на основе сортировки вектора (скажем, последовательности ) … Класс TMatrix не предоставляет ссылочный доступ к его строкам (таким образом, я не может создать структуру, чтобы изменить порядок …), но удобно предоставляет метод TMatrix :: swap (row1, row2)

Так вот код:

 TMatrix matrix; vector 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> sorter(n); for(int i = 0; i < n; i++) { std::pair 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> swaps; int source = pivot; int destination = i; while(destination != pivot) { // store required swaps until final destination // is equals to first source (pivot) std::pair 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 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), поскольку каждая строка, которая не на месте, будет меняться только один раз …

Повеселись! 🙂