Это, вероятно, лучше всего указано в качестве примера. У меня есть два вектора/списки:
People = {Anne, Bob, Charlie, Douglas}
Ages = {23, 28, 25, 21}
Я хочу сортировать Люди по их возрасту, используя что-то вроде sort(People.begin(), People.end(), CustomComparator), но я не знаю, как написать CustomComparator для просмотра возрастов, а не для людей.
Вместо создания двух отдельных векторов/списков обычным способом справиться с этим является создание единого вектора/списка объектов, которые включают имена и возрасты:
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<, а не в отдельном классе сравнения, способом Я сделал это выше.
Как отмечали другие, вы должны рассмотреть вопрос о группировании людей и возрастов.
Если вы не можете/не хотите, вы можете создать для них "индекс" и вместо этого отсортировать этот индекс. Например:
// 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]]
Как правило, вы не ставите данные, которые хотите сохранить вместе в разных контейнерах. Создайте 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 уже реализуют операторы сравнения.
Не имеет смысла держать их в двух отдельных структурах данных: если вы переупорядочиваете 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>());
Я бы предложил объединить эти два списка в один список структур. Таким образом вы можете просто определить operator < как dirkgently said.
Ответ Джерри Коффина был полностью ясным и правильным.
У меня есть связанная проблема, которая может дать хорошее обсуждение этой теме...:)
Мне пришлось переупорядочить столбцы объекта-матрицы (например, 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), поскольку каждая строка, которая не находится на месте, будет меняться только один раз...
Удачи!:)