Как починить std::list.sort() для VC++6 - C/C++

Как это работает на пользовательских типах данных?
т.е. у меня есть list из своих class'ов и я хочу их отсортировать по определенному полю. Или для этого все-таки свою ф-цию писать?

Со стандартными-то все понятно

list<int> intList;
for(i = 0; i < 10; i++) {
    intList.push_front(rand()%1000);
}
intList.sort();

А вот как со своими классами поступать?

class CStudent  
{
public:
[skip]
private:
    std::string FName;        // Имя
    std::string MName;        // Отчество
    std::string LName;        // Фамилия
    DATE BirthDay;        // День рождения
    TEST *tests;        // Зачеты
    EXAMINATION *exams;    // Экзамены
};

list<CStudent> slist;
slist.push_back(bla-bla);

И вот я хочу отсортировать по ФИО.
Как?

Здравствуйте peter@work, Вы писали:

>у меня есть list из своих class'ов и я хочу их отсортировать по определенному полю. Или для этого все-таки свою ф-цию писать?

Функцию сортировки? Ни в коем разе. Тем более, что для списка сделать эффективную сортировку "снаружи" невозможно. Достаточно написать свою функцию сравнения.

>

>class CStudent
>{
>public:
>[skip]
>private:
>    std::string FName;        // Имя
>    std::string MName;        // Отчество
>    std::string LName;        // Фамилия
>    <...>

Т.к. все данные-члены класса CStudent private, предполагаем, что существуют соответствующие const public функции доступа с именами fname, mname, lname.

>И вот я хочу отсортировать по ФИО.

Допустим, что имеется в виду сортировка по фамилиям, при одинаковых фамилиях — по именам, при одинаковых фамилиях и именах — по отчествам.

struct CStudentNameIsLess
{
  // true, если l "меньше" r по выбранному критерию
  bool operator()(const CStudent& l, const CStudent& r) const
  {
     int lname_cmp = l.lname().compare(r.lname());   // сравнить фамилии
     if (lname_cmp < 0)
     {
       return true;                                  // фамилия "меньше"
     }
     else if (lname_cmp == 0) 
     {
       int fname_cmp = l.fname().compare(r.fname()); // фамилии одинаковые, сравнить имена
       if (fname_cmp < 0)
         return true;                                // имя "меньше"
       else if (fname_cmp == 0)
         return l.mname() < r.mname();               // имена одинаковые, сравнить отчества
     }
     return false;
  }
};

slist.sort(CStudentNameIsLess());

Здравствуйте Павел Кузнецов, Вы писали:

ПК>Т.к. все данные-члены класса CStudent private, предполагаем, что существуют соответствующие const public функции доступа с именами fname, mname, lname.

Это так.

>>И вот я хочу отсортировать по ФИО.

ПК>Допустим, что имеется в виду сортировка по фамилиям, при одинаковых фамилиях — по именам, при одинаковых фамилиях и именах — по отчествам.

И тут верно

ПК>[c]
ПК>struct CStudentNameIsLess

вот тут поясни, plz.

Здравствуйте peter@work, Вы писали:

ПК>>

ПК>>struct CStudentNameIsLess

peter>вот тут поясни, plz.

В std::list есть две перегруженных функции sort. Одна имеет сигнатуру `void sort()' и при сортировке использует операцию `<' для определения порядка элементов. Если для твоего класса существует "естественный" порядок и определена операция `<', никаких танцев с бубном вообще не требуется: пиши себе slist.sort(), как и для встроенных типов.

Если же операция `<' не определена или требуется отсортировать элементы в порядке, отличном от того, который задается этой операцией, то можно воспользоваться второй функцией std::list<>::sort, которая задана шаблоном `template<class Predicate> void sort(Predicate)'. Эта функция использует переданный ей объект для определения порядка элементов. К аргументу функции должна быть применима операция (). Т.е. либо класс переданного объекта должен иметь перегруженную операцию `()', либо объектом должен быть указатель на соответствующую функцию, принимающую два аргумента того же типа, что и элементы контейнера и возвращающую true, если и только если элементы находятся в "правильном" порядке (тот, что задан первым аргументом, находится "левее" второго).

Таким образом, для класса CStudent можно определить функцию:

bool student_name_is_less(const CStudent& l, const CStudent& r);

Или класс, переопределяющий операцию `()' с двумя аргументами:

struct CStudentNameIsLess
{
  bool operator()(const CStudent& l, const CStudent& r) const;
};

Для вызова функции sort c аргументом в первом случае нужно писать что-нибудь вроде:

slist.sort(student_name_is_less);

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

slist.sort(CStudentNameIsLess());

Для некоторых компиляторов второй способ является более эффективным, т.к. позволяет легче избежать косвенного вызова функции через указатель. Кроме того, второй способ позволяет реализовать более сложную функцию сравнения, требующую дополнительных аргументов, кроме const CStudent& l и const CStudent& r. Эти аргументы можно сохранить в классе CStudentNameIsLess, передав их в конструкторе временного объекта.

Здравствуйте Павел Кузнецов, Вы писали:

ПК>Здравствуйте peter@work, Вы писали:

ПК>>>

ПК>>>struct CStudentNameIsLess

peter>>вот тут поясни, plz.

ПК>В std::list есть две перегруженных функции sort. Одна имеет сигнатуру `void sort()' и при сортировке использует операцию `<' для определения порядка элементов. Если для твоего класса существует "естественный" порядок и определена операция `<', никаких танцев с бубном вообще не требуется: пиши себе slist.sort(), как и для встроенных типов.

ПК>Если же операция `<' не определена или требуется отсортировать элементы в порядке, отличном от того, который задается этой операцией, то можно воспользоваться второй функцией std::list<>::sort, которая задана шаблоном `template<class Predicate> void sort(Predicate)'.

В MSVC 6.0, к сожалению, можно только специализировать std::greater для своего класса. Предикат передать не получится (если, конечно, не править хедер руками).

Здравствуйте Аноним, Вы писали:

А>В MSVC 6.0, к сожалению, можно только специализировать std::greater для своего класса. Предикат передать не получится (если, конечно, не править хедер руками).

Я бы поправил :-) P.J. Plauger где-то в группе новостей так и рекомендовал сделать. Можно еще использовать STLport, у которой с этим все в порядке.

А>>В MSVC 6.0, к сожалению, можно только специализировать std::greater для своего класса. Предикат передать не получится (если, конечно, не править хедер руками).

ПК><...>

Кроме того, для избежания дальнейших сюрпризов при сопровождении кода, вместо специализации std::greater<> лучше определить соответствующую операцию `>' для объектов пользовательского класса.

Здравствуйте Павел Кузнецов, Вы писали:

А>>>В MSVC 6.0, к сожалению, можно только специализировать std::greater для своего класса. Предикат передать не получится (если, конечно, не править хедер руками).

Вот он меня нафиг и посылает

Где править header?

ПК>><...>

ПК>Кроме того, для избежания дальнейших сюрпризов при сопровождении кода, вместо специализации std::greater<> лучше определить соответствующую операцию `>' для объектов пользовательского класса.

Как это делается?

А>>>>В MSVC 6.0, к сожалению, можно только специализировать std::greater для своего класса. Предикат передать не получится (если, конечно, не править хедер руками).

peter>Вот он меня нафиг и посылает :no:
peter>Где править header?

Заголовок <list> (измененные/добавленные строки выделены):

    //typedef greater<_Ty> _Pr3; // эту закомментировать
    template<class _Pr3>          // эту добавить
    void merge(_Myt& _X, _Pr3 _Pr)
        {. . .}
    . . .
    template<class _Pr3>          // эту добавить
    void sort(_Pr3 _Pr)
        {. . .}

ПК>>Кроме того, для избежания дальнейших сюрпризов при сопровождении кода, вместо специализации std::greater<> лучше определить соответствующую операцию `>' для объектов пользовательского класса.

peter>Как это делается?

Просто определяешь для своего класса операции `<', `>':

class CStudent
{
  . . .
};

bool operator <(const CStudent& l, const CStudent& r)
{
  . . .
}

bool operator >(const CStudent& l, const CStudent& r)
{
  . . .
}

Кстати, если уж определять эти, то стоит определить и остальные: ==, !=, >=, <=.

Здравствуйте Павел Кузнецов, Вы писали:

ПК>Просто определяешь для своего класса операции `<', `>':

ПК>

ПК>class CStudent
ПК>{
ПК>  . . .
ПК>};

ПК>bool operator <(const CStudent& l, const CStudent& r)
ПК>{
ПК>  . . .
ПК>}

ПК>bool operator >(const CStudent& l, const CStudent& r)
ПК>{
ПК>  . . .
ПК>}

Они оформляются как friend или как члены класса?

Здравствуйте peter@work, Вы писали:

ПК>>Просто определяешь для своего класса операции `<', `>': <...>

peter>Они оформляются как friend или как члены класса?

Если нужен доступ к private части класса, то как friend:

class CStudent
{
  friend bool operator <(const CStudent& l, const CStudent& r);
  . . .
};

// два аргумента
bool operator <(const CStudent& l, const CStudent& r);
. . .

Или как члены класса:

class CStudent
{
public:
  // только "второй" аргумент, "первый" -- this
  bool operator <(const CStudent& r);
  . . .
};

Если, например, объект класса CStudent может быть неявно сконструирован из строки, то, выражение "Вася" < student1 будет допустимым в первом случае и не будет допустимым во втором.

Если же операции <, > и т.п. можно реализовать, не требуя доступа к private части класса, то предпочтительнее реализовывать их как внешние функции (не члены и не friend):

class CStudent
{
public:
  const std::string& name() const;
  . . .

private:
  std::string m_name;
  . . .
};

// два аргумента
inline bool operator <(const CStudent& l, const CStudent& r)
{
  return l.name() < r.name();
}

. . .

Здравствуйте Павел Кузнецов, Вы писали:

Сделал так:
В header'е

    bool operator< (const CStudent& r);
    bool operator> (const CStudent& r);

в .cpp

bool CStudent::operator <(const CStudent& r) {
    int lname_cmp = (*this).getLName().compare(r.getLName());   // сравнить фамилии
    
    if (lname_cmp < 0)
    {
        return true;                                  // фамилия "меньше"
        
    }
    else if (lname_cmp == 0)
    {
        int fname_cmp = (*this).getFName().compare(r.getFName()); // фамилии одинаковые, сравнить имена
        
        if (fname_cmp < 0)
            return true;                                // имя "меньше"
        
        else if (fname_cmp == 0)
            return (*this).getMName() < r.getMName();               // имена одинаковые, сравнить отчества
        
    }
    return false;
}

а потом
slist.sort();

нифига не сортирует

	От:	peter@work
	Дата:	13.10.02 11:35
	Оценка:

	От:	Павел Кузнецов
	Дата:	13.10.02 12:02
	Оценка:	3 (1)

	От:	peter@work
	Дата:	13.10.02 13:36
	Оценка:

	От:	Павел Кузнецов
	Дата:	13.10.02 14:02
	Оценка:	3 (1)

	От:	Аноним
	Дата:	13.10.02 14:07
	Оценка:	9 (1)