Re[3]: Moya sortirovka dlya std::list - C/C++

Privet,
Kak mne sdelat' sortirovku std::list ispolzuya moyu sobstvennuyu func. sravneniya. Iskal , iskal v inete, no ponyal chto zadacha ne sovsem easy. Interesuet reshenie kak dlya vc++ tak i g++

KA>Kak mne sdelat' sortirovku std::list ispolzuya moyu sobstvennuyu func. sravneniya. Iskal , iskal v inete, no ponyal chto zadacha ne sovsem easy. Interesuet reshenie kak dlya vc++ tak i g++

Вот так:

class Obj { ... };

struct MyComparator
{
bool operator(const Obj& obj1, const Obj& obj2)
{
// return true, если после сортировки
// obj1 должен быть "слева" от obj2
}
};

int main()
{
std::list<Obj> l;
...
l.sort(MyComparator());
}

Здравствуйте Kubyshev Andrey, Вы писали:

KA>Privet,
KA>Kak mne sdelat' sortirovku std::list ispolzuya moyu sobstvennuyu func. sravneniya. Iskal , iskal v inete, no ponyal chto zadacha ne sovsem easy. Interesuet reshenie kak dlya vc++ tak i g++

определи (переопредели) для данных, которые ты хранишь в листе операцию "меньше" и алгоритм sort будет сортировать твой лист. Если непонятно, то приведи конкретный пример, на примере проще объяснить.

Здравствуйте Kubyshev Andrey, Вы писали:

KA>Privet,
KA>Kak mne sdelat' sortirovku std::list ispolzuya moyu sobstvennuyu func. sravneniya. Iskal , iskal v inete, no ponyal chto zadacha ne sovsem easy. Interesuet reshenie kak dlya vc++ tak i g++

Используй метод std::list<T>::sort(greater<T> Pred)

struct MyGreater : public binary_function<T, T, bool>
{
  bool operator()(const T& x, const T& y) const;
};

Реализуй свое сравнение в операторе () этого класса — и вперед.

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

Так в том то и дело, что это не работает. Так как вызывается operator() от класса greater, а не от твоего класса.

#include <iostream>
#include <list>
#include <algorithm>

#define for if(1) for


template<class T>
struct MyGreater : public std::greater<T>
{
  bool operator()(const T& x, const T& y) const
  {
    return x < y;
  }
};

template<class T>
struct MyGreater2 : public std::greater<T>
{
  bool operator()(const T& x, const T& y) const
  {
    return x > y;
  }
};


void main()
{
  typedef std::list<int> List;
  std::list<int> l;
  for (int i = 0; i < 10; i++)
  {
    l.push_back (i);
  }
  l.sort (MyGreater<int>());
  for (List::iterator it = l.begin(); it != l.end(); ++it)
  {
    std::cout << *it << "\n";
  }
  l.sort (MyGreater2<int>());
  for (List::iterator it = l.begin(); it != l.end(); ++it)
  {
    std::cout << *it << "\n";
  }
}

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

ПК>struct MyComparator
ПК>{
ПК> bool operator(const Obj& obj1, const Obj& obj2)
ПК> {
ПК> // return true, если после сортировки
ПК> // obj1 должен быть "слева" от obj2
ПК> }
ПК>};

ПК>int main()
ПК>{
ПК> std::list<Obj> l;
ПК> ...
ПК> l.sort(MyComparator());
ПК>}

Так в VC6.0 со стандартной STL это не работает

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

DG>Так в том то и дело, что это не работает. Так как вызывается operator() от класса greater, а не от твоего класса.

Расследовал. Действительно

STL от VC++ хочется иметь предикат типа greater<T>, и он имеет именно его.

Похоже, халявы нет, и придется юзать контейнеры с произвольным доступом...

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

DG>Так в VC6.0 со стандартной STL это не работает

Не такая уж она стандартная

Есть еще STLPort, STL от SGI...

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

К>Не такая уж она стандартная

В том смысле стандартная, что она используется после стандартной установки VC6.0

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

К>Здравствуйте DarkGray, Вы писали:

DG>>Так в том то и дело, что это не работает. Так как вызывается operator() от класса greater, а не от твоего класса.

К>Расследовал. Действительно

К>STL от VC++ хочется иметь предикат типа greater<T>, и он имеет именно его.

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

Зачем с произвольным доступом

смотрим определение

template<class _Ty>
    struct greater : binary_function<_Ty, _Ty, bool> {
    bool operator()(const _Ty& _X, const _Ty& _Y) const
        {return (_X > _Y); }
    };

просто либо делаем производный класс от нашего с переопределённым опретором >, ( если не встроенный тип )

либо класс оболочку с нужным оператором.

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

B>Здравствуйте Кодт, Вы писали:

К>>Здравствуйте DarkGray, Вы писали:

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

B>Зачем с произвольным доступом

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

B>смотрим определение

B>

B>template<class _Ty>
B>    struct greater : binary_function<_Ty, _Ty, bool> {
B>    bool operator()(const _Ty& _X, const _Ty& _Y) const
B>        {return (_X > _Y); }
B>    };
B>

B>просто либо делаем производный класс от нашего с переопределённым опретором >, ( если не встроенный тип )
B>либо класс оболочку с нужным оператором.

Ля-ля-ля! Солнышко, птички...

Хорошо, если для сортируемого типа не был определен оператор >: определяем и получаем удовольствие.
Если же был — то

template<.....> struct greater :.....
{
bool operator()(.....) {......}
};

struct MySuperPuperClass : public greater<.....>
{
bool operator()(.....) {......}
};

// так объявлен метод списка
void std::list<T>::sort(greater<T>& pred);

// вызываем
MySuperPuperClass sorter;
mylist.sort(sorter);

// компилятор первым делом приводит (greater<T>)(sorter)
// а у greater оператор-то не виртуальный!

Опаньки.

Если не верите — напишите и расставьте брекпоинты.

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

К>// так объявлен метод списка
К>void std::list<T>::sort(greater<T>& pred);

Еще хуже: void std::list<T>::sort(greater<T> pred); (без ссылки), так что, даже если бы (не дай бог) функция greater<T>::operator() была виртуальным, объект все равно срезался бы, и в любом случае была бы вызвана операция greater<T>::operator().

Vsem privet,
Vot nashel chto po etomu povodu sovetuet Igor Tandetnik, navernyaka te kto chitaet inostrannye news groups po win programmingu ne raz videli eto name.

-----
Here's the deal. list::sort without the parameter sorts using less<T>
(in other words, <) in the ascending order, smallest at the head,
largest at the tail. list::sort with the parameter is supposed to accept
any predicate and sorts in such a way that, had the predicate been
less<T>, the sorted order would be the same as with parameterless
version. In other words, if Pr(A, B) == true, A will precede B in the
sorted order.

Now, the Dinkumware STL implementation shipped with MSVC6 does not
provide a templated version of list::sort, because of inferior compiler
template support at the time the implementation was frozen. Instead, the
predicate parameter is hardcoded to be greater<T>. This way, you can
sort in ascending order (with parameterless version) or descending order
(with hardcoded parameter), but not in any other order. This "feature"
made it into MSDN documentation, hence the confusion.

Now that the compiler is better, P.J. Plauger, one of the authors of
Dinkumware STL, recommends editing <list> header. Find a line

void sort(_Pr3 _Pr)

and put "template <class _Pr3>" in front of it, so it looks like

template <class _Pr3> // added line
void sort(_Pr3 _Pr)

Do the same to merge:

template <class _Pr3> // added line
void merge(_Myt& _X, _Pr3 _Pr)

You need to change both, since sort uses merge internally. This makes
std::list C++ standard-compliant. While you are at it, consider applying
the fixes from

http://www.dinkumware.com/vc_fixes.html

--
With best wishes,
Igor Tandetnik

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

К>Здравствуйте Burkutsky, Вы писали:

B>>Здравствуйте Кодт, Вы писали:

К>>>Здравствуйте DarkGray, Вы писали:

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

B>>Зачем с произвольным доступом :???:

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

Ясен пень сушествуют, но насколь я понял из дисскусии надо именно для листа( или другого с последов. доступом )

B>>смотрим определение

B>>

B>>template<class _Ty>
B>>    struct greater : binary_function<_Ty, _Ty, bool> {
B>>    bool operator()(const _Ty& _X, const _Ty& _Y) const
B>>        {return (_X > _Y); }
B>>    };
B>>

B>>просто либо делаем производный класс от нашего с переопределённым опретором >, ( если не встроенный тип )
B>>либо класс оболочку с нужным оператором.

К>Ля-ля-ля! Солнышко, птички...

К>Хорошо, если для сортируемого типа не был определен оператор >: определяем и получаем удовольствие.
К>Если же был — то
К>

К>template<.....> struct greater :.....
К>{
К>bool operator()(.....) {......}
К>};

К>struct MySuperPuperClass : public greater<.....>
К>{
К>bool operator()(.....) {......}
К>};

К>// так объявлен метод списка
К>void std::list<T>::sort(greater<T>& pred);

К>// вызываем
К>MySuperPuperClass sorter;
К>mylist.sort(sorter);

К>// компилятор первым делом приводит (greater<T>)(sorter)
К>// а у greater оператор-то не виртуальный!
К>

К>Опаньки.

К>Если не верите — напишите и расставьте брекпоинты.

По ходу ты не понял идею, может я не понятно объяснил: не производный от структуры greater<.....>
а производный от _сортируемого типа_ с перегруженым оператором ( bool operator < ( const CMyUpType& _crVal ) const ) а не operator()(...).

то есть мы вообще _не трогаем_ greater.
в нём ( см. определение ) вызывается operator < уже _нашего_ типа который вернёт то, что мы хотим.

Вот что имелось ввиду:

template <class T>
class CMyUpTempl
{
    T m_tContent; // не производный класс а оболочка для возможности использования встроенных типов
public:
    CMyUpTempl( const T& _crVal ):
      m_tContent( _crVal )
    {
    }
    inline operator T&()
    {
        return m_tContent;
    }
    inline operator T() const
    {
        return m_tContent;
    }
    inline bool operator > ( const CMyUpTempl& _crVal ) const // именно этот оператор вызовется в greater
    {
        return m_tContent < _crVal.m_tContent;
                // return _WhatYouWantButDontForgetLogicCorrecpondingBetweenLogicOperators;
    
    }
};

После чего

list< CMyUpTempl< int > > g_myList;


...
int APIENTRY WinMain(HINSTANCE hInstance,
                     HINSTANCE hPrevInstance,
                     LPSTR     lpCmdLine,
                     int       nCmdShow)
{
    g_myList.push_back( 5 );
    g_myList.push_back( 6 );
    g_myList.push_back( 7 );

    g_myList.sort( std::greater<CMyUpTempl< int> >());

    int nVal1 = g_myList.front();
    g_myList.pop_front();
    int nVal2 = g_myList.front();
    g_myList.pop_front();
    int nVal3 = g_myList.front();
    g_myList.pop_front();

        return 0;
}

Можешь проверить всё прекрасно работает. :super:

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

АА>Вот что имелось ввиду:

А>

А>template <class T>
А>class CMyUpTempl
А>{
А>    T m_tContent; // не производный класс а оболочка для возможности использования встроенных типов
А>public:
А>    CMyUpTempl( const T& _crVal ):
А>      m_tContent( _crVal )
А>    {
А>    }
А>    inline operator T&()
А>    {
А>        return m_tContent;
А>    }
А>    inline operator T() const
А>    {
А>        return m_tContent;
А>    }
А>    inline bool operator > ( const CMyUpTempl& _crVal ) const // именно этот оператор вызовется в greater
А>    {
А>        return m_tContent < _crVal.m_tContent;
А>                // return _WhatYouWantButDontForgetLogicCorrecpondingBetweenLogicOperators;
А>    
А>    }
А>};
А>

А>После чего

А>

А>list< CMyUpTempl< int > > g_myList;


А>...
А>int APIENTRY WinMain(HINSTANCE hInstance,
А>                     HINSTANCE hPrevInstance,
А>                     LPSTR     lpCmdLine,
А>                     int       nCmdShow)
А>{
А>    g_myList.push_back( 5 );
А>    g_myList.push_back( 6 );
А>    g_myList.push_back( 7 );

А>    g_myList.sort( std::greater<CMyUpTempl< int> >());

А>    int nVal1 = g_myList.front();
А>    g_myList.pop_front();
А>    int nVal2 = g_myList.front();
А>    g_myList.pop_front();
А>    int nVal3 = g_myList.front();
А>    g_myList.pop_front();

А>        return 0;
А>}
А>

А>Можешь проверить всё прекрасно работает.

А>

Ну это же совсем другое дело!
Ставлю оценку этажом выше.

	От:	Kubyshev Andrey
	Дата:	18.04.02 10:34
	Оценка:

	От:	Павел Кузнецов
	Дата:	18.04.02 10:52
	Оценка:

От:	Odi$$ey	http://malgarr.blogspot.com/
Дата:	18.04.02 10:56
Оценка:

	От:	Кодт
	Дата:	18.04.02 11:34
	Оценка:

От:	DarkGray	http://blog.metatech.ru/post/ogni-razrabotki.aspx
Дата:	18.04.02 12:43
Оценка:

	От:	Burkutsky
	Дата:	18.04.02 14:37
	Оценка:	14 (1)