Как сортировать объекты?

Question

Я создал класс, создал под ним класс объектов и заполнил их данными. Теперь я хочу отсортировать весь массив по определенному члену этого класса, как мне это сделать с помощью функции stable_sort ()?

Редактировать: Хорошо, у меня есть это прямо сейчас,

class sortContiner 
{
public:
    double position;
    int key;
    double offsetXposition;
    double offsetYposition;
    int origXposition;
    int origYposition;
};

Я объявил массив следующим образом:

sortContiner * sortList = new sortContiner [length];

Теперь я хочу отсортировать его по члену sortList .position с помощью stable_sort () следующим образом:

stable_sort(sortList, sortList + length, ????);

Как должна выглядеть функция сравнения?

Answer 1

Вам нужны итераторы в вашем массиве и некоторые критерии сортировки. Начнем с итераторов:

Вам потребуется начальный итератор и конечный итератор. Начальный итератор должен указывать на первый элемент, конечный итератор должен указывать за последним элементом. Указатели являются идеальными итераторами. Массив неявно преобразуется в указатель на его первый элемент, поэтому у вас есть начальный итератор. Добавьте к нему количество элементов в массиве, и вы получите конечный итератор. Количество элементов в массиве может быть получено путем деления размера (количества байтов) массива на размер одного элемента. Собираем все вместе:

foo array[10];
const std::size_t array_size = sizeof(array)/sizeof(array[0]);
const int* array_begin = array; // implicit conversion
const int* array_end = begin + array_size;

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

bool operator<(const foo& lhs, const foo& rhs)
{
  // compares using foo's bar
  return lhs.get_bar() < rhs.get_bar();
}

Теперь вы можете отсортировать ваш массив:

std::stable_sort( array_begin, array_end );

Если критерий сортировки не такой постоянный (скажем, иногда вы хотите сортировать на основе данных foo bar, иногда на основе его данных wrgly), вы можете передать различные критерии сортировки алгоритм сортировки в качестве необязательного третьего параметра. Критерии сортировки должны быть функциональными. Это могут быть функции или функциональные объекты. Последние обеспечивают встраивание, поэтому они обычно лучше. Вот как:

bool compare_by_bar(const food& lhs, const foo& rhs)
{
  return lhs.get_bar() < rhs.get_bar();
}

struct wrgly_comparator {
  bool operator()(const food& lhs, const foo& rhs) const
  {
    return lhs.get_wrgly() < rhs.get_wrgly();
  }
};

Вот как вы их используете:

std::stable_sort( array_begin, array_end, compare_by_bar );
wrgly_comparator wc;
std::stable_sort( array_begin, array_end, wc );

Вы также можете создать компаратор на лету:

std::stable_sort( array_begin, array_end, wrgly_comparator() );

Редактировать : Вот еще несколько советов, основанных на вашем расширенном вопросе:

sortContainer * sortList = new sortContiner [length]; создаст динамический массив в куче . В C ++ нет сборки мусора, и вы несете ответственность за очистку кучи после себя (в этом случае, вызывая delete[] sortList;). Общеизвестно, что это трудно сделать новичкам и подвержено ошибкам даже опытным программистам. Очень вероятно, что вам нужен автоматический массив: sortContainer sortList[length]; в стеке.

Идентификатор sortContainer говорит мне, что это контейнер. Тем не менее, это тип предметов, которые должны быть помещены в контейнер. Будьте более осторожны, выбирая идентификаторы. Правильное именование имеет большое значение для удобочитаемого и поддерживаемого кода.

Answer 2

Вы можете поместить объекты в контейнер (скажем, std :: vector), написать функтор и использовать его в stable_sort.

class Functor
{
    public:
        bool operator() (const Data& info1, const Data& info2)
        {
            return info1.AnyMemberOfData>info2.AnyMemberOfData;
        }
};

std::stable_sort(aVector.begin(), aVector.end(),functor);

Редактировать : Использование массивов (как предложено @sbi и @ wrang-wrang):

Data anArray[10];
//Fill anArray
std::stable_sort(anArray, anArray + 10,functor);

ИЛИ напишите operator < для своего класса и звоните прямо stable_sort

Answer 3

Вот декларация stable_sort():

template <class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last, 
                 StrictWeakOrdering comp);

Вы должны использовать вторую перегрузку и предоставить собственный функтор сравнения. Нечто подобное:

class obj; // your type
struct obj_cmp
{
  bool operator()( const obj& lhs, const obj& rhs ) const
  {
     return lhs.member_ < rhs.member_;
  } 
};

Это также может быть бесплатная функция - все, к чему вы можете применить () , например:

bool obj_cmp_func( const obj& lhs, const obj& rhs )
{
  return lhs.member_ < rhs.member_;
} 

Тогда ваше утверждение сортировки будет:

obj array[X]; // X is a compile-time constant
// populate array
std::stable_sort( array, array + X, obj_cmp());
// or with the function
std::stable_sort( array, array + X, obj_cmp_func );

Обратите внимание, что объекты вашего типа должны свободно копироваться. Смотрите здесь для деталей.

Answer 4

Я вижу, что уже есть пара решений, но так как я уже напечатал свое, я все равно хочу опубликовать его. Это небольшое рабочее решение, чтобы дать вам представление:

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdlib> 
using namespace std;    //i know :-/


//A very useless class
class myClass{          
private:
  int value;
public:
  myClass(int val){value = val;}
  int getValue(){return value;}
};

//a function which defines how to compare my objects
bool myComparsion (myClass m ,myClass n)
{
    return (m.getValue()<n.getValue());
}

int main(){

  vector<myClass> myvector;
  vector<myClass>::iterator it;

  //Filling up the vector with my objects which are initialized with random numbers
  for (int n=0;n<10;++n)
    myvector.push_back(*(new myClass(rand()%100)));

  //looking at my vector 
  cout<<"Before:";
  for (it=myvector.begin(); it!=myvector.end(); ++it)
    cout<< " "<<it->getValue();
  cout << endl;     

  //sorting the vector and looking again      
  stable_sort (myvector.begin(), myvector.end(), myComparsion);    //this is where the magic happens
  cout<<"After:";
  for (it=myvector.begin(); it!=myvector.end(); ++it)
    cout << " " << it->getValue();
  cout << endl;

  //...

  }

Вывод должен быть примерно таким

Before: 83 86 77 15 93 35 86 92 49 21
After: 15 21 35 49 77 83 86 86 92 93

Answer 5

Как дополнение к другим ответам: предикат может быть создан на лету с помощью boost (или tr1) bind . Например, для сортировки по ключевому элементу:

std::stable_sort(sortList, sortList + length,
  boost::bind(&sortContiner::key, _1) < boost::bind(&sortContiner::key, _2)
);

Answer 6

Вы должны написать свой собственный предикат и передать его стандартному алгоритму.

Answer 7

Вы можете что-то вроде этого: Код не требует пояснений:

class A
{
public:
    A() : m_a(0), m_b(0)
    {
    }
    void setA(int n)
    {
        m_a = n;
    }
    void setB(int n)
    {
        m_b = n;
    }

    int getA() const
    {
        return m_a;
    }


    int getB() const
    {
        return m_b;
    }


private:
    int m_a;
    int m_b;
};

bool compareA(const A& first, const A& second)
{
    return first.getA() < second.getA();
}

bool compareB(const A& first, const A& second)
{
    return first.getB() < second.getB();
}


int _tmain(int argc, _TCHAR* argv[])
{
    A a[10];
    for(int i = 10; i >= 0; --i)
    {
        a[i].setA(i);
        a[i].setB(i);
    }

    //Sort on variable m_a
    std::stable_sort(a, a + 10, compareA);

    //Sort on variable m_b
    std::stable_sort(a, a + 10, compareB);
}