Solved

How to define predicate function to sort stl list

Posted on 2000-02-17
27
3,795 Views
Last Modified: 2013-12-14
I can't seem to get the syntax right for the predicate function that I want to use to sort a list.  My example code that I thought should work is as follows:

#pragma warning (disable:4786)
#include <list>
#include <string>
using namespace std;

// function object to compare two strings
class bar {
    bool operator()(const char *arg1, const char* arg2) const
    { return strcmp(arg1, arg2) < 0; }
};
void
ListTest()
{
    list<const char*> l1;
    // sort with my own predicate function object (doesn't work)
    l1.sort(bar());
}

The error message is as follows:

-------------------Configuration: stltests - Win32 Debug--------------------
Compiling...
listtest.cpp
c:\users\race\test\stltests\listtest.cpp(15) : error C2664: 'void __thiscall std::list<char const *,class std::allocator<char const *> >::sort(struct std::greater<char const *>)' : cannot convert parameter 1 from 'class bar' to 'struct std::greater<char const *>'
        No constructor could take the source type, or constructor overload resolution was ambiguous
Error executing cl.exe.

I thought that I just had to pass a function object that defined operator() but that doesn't seem to be the case.  I've tried deriving my function from binary_function<const char*, consts char*, bool> but I still get the message that 'class bar' can't be converted to 'struct std::greater<char const*>.

How can I define 'class bar' so that it will be acceptable to the sort() routine that is specific to the list<const char*>?


listtest.obj - 1 error(s), 0 warning(s)
0
Comment
Question by:emitchell
  • 12
  • 9
  • 5
  • +1
27 Comments
 
LVL 3

Accepted Solution

by:
LucHoltkamp earned 100 total points
ID: 2534364
Answer follows...
0
 
LVL 7

Expert Comment

by:KangaRoo
ID: 2534413
I'm waiting...
0
 
LVL 3

Expert Comment

by:LucHoltkamp
ID: 2534420
According to the STL reference guide sort should accept a Compare function-object such as the one you defined (except that the operator() should be public):

class bar
{
public: // note, the operator must be public
   bool operator()(const char *arg1, const char* arg2) const
   { return strcmp(arg1, arg2) < 0; }
};

void ListTest()
{
   list<const char*> l1;
   // sort with my own predicate function object (doesn't work)
   l1.sort(bar());
}

However in VC6 this doesn't work. Checking the code of STL supplied with VC6, it turns out that sort isn't defined as a member template (as it should be, and VC6 supports it) but that sort wants a parameter greater<_Ty>.
So in VC6 you can use the sort function in list ONLY with greater, so the last line must be:

  l1.sort(greater<const char*> l1;

One idea would be to derive you're function object bar from greater, but unfortunatly, the operator() of greater is not virtual, so this will not work.

Yet another idea would be to use the non-member sort:

  sort(l1.begin(), l1.end(), bar());

however this won't work because sort want random-access iterators...

Solution? Well... it looks like this is a serious bug in the VC6 STL implementation... you will have to write you're own sort, or switch to vector or deque...

Hope this helps you enough,
Luc

0
 
LVL 3

Expert Comment

by:LucHoltkamp
ID: 2534424
Oh I mistyped something...

l1.sort(greater<const char*> l1

must of course be

l1.sort(greater<const char*>());
0
 
LVL 7

Expert Comment

by:KangaRoo
ID: 2534425
Unfotunately you can not do what you intend to. list<>::sort will always sort according to the standard (member) comparision operators (operator < according to the books, but your implementation seems to be using operator > )

The only way out ( I see) is to wrap your const char * objects in a little class which defines it's own operator < and operator >
0
 
LVL 7

Expert Comment

by:KangaRoo
ID: 2534443
I see, must be a rather recent addition, it's present in 1997 doc, but not in 1995...
I admit, the sort member which takes a compare as argument would make sense to me. But it would require support for template member functions, which is rather weakly supported with VC, or so I've been told.

The non-member STL sort algorithms all require random access iterators, which are not supported by list's
0
 
LVL 3

Expert Comment

by:LucHoltkamp
ID: 2534573
VC supports template member functions, nothing weak on that... So I judge this to be a bug! The reference sais that

template <class Compare>
list::sort(Compare c)

is only present in compilers that support template members (what again VC6 does), however microsoft choose a third option: defining sort(greater<_Ty>&) which is quite useless... typical microsoft I would say...
I start to believe that they do these non-ansi things on perpose, to make it harder to switch to another compiler...

I agree with kangaroo that wrapping you're strings in a class and provide the operator< and use the list::sort() member (without parameters) is an option, but I think it's ugly, because you fixate you're comparison function into the class.

There may be another option that is even uglier, and that is to write a template specialisation on greater<const char*>...

The best way to go is switching to vector or dequeue and use the global sort algorithm.

Luc
0
 
LVL 22

Expert Comment

by:nietod
ID: 2534636
>> VC supports template member functions,
>> nothing weak on that
Officially, VC 6 does not support template member functions.  They do say that simple cases will compile and work but more complex cases may not behave correctl and that it is not a bug as template member functions are not supported.  So use them at your own risk.  (I was just doing reasearch on this last week.)
0
 
LVL 7

Expert Comment

by:KangaRoo
ID: 2534679
0
 
LVL 3

Expert Comment

by:LucHoltkamp
ID: 2534840
Hmm, I did not do any investigation on it, I just used it. But I read the questions, I used simple cases until now, and that works.... but I'll be more carefull :-)
But I can imagine that a specialisation on a template member is too much asked.
Any way, they should have either used a template member, or leave the sort with parameter out altogether.... the 'solution' they choose is confusing..
Luc
0
 
LVL 7

Expert Comment

by:KangaRoo
ID: 2534962
It leaves the possibilty of creating a specialization of greater<> open... Though that seems a bit fragile
0
 

Author Comment

by:emitchell
ID: 2538115
It looks like I have a problem.  I need the list in order to insert in the mddle!

I need operator<() to sort one way and I wanted to supply my own predicate function to sort the list a second way.

Because of the Microsoft insistence on greater<> as the predicate function, does anyone know how this can be specialized to my binary function acting on my class stored in the list?

The objects are not really strings.  I just used that for ease of coming up with a simple example.

0
 
LVL 7

Expert Comment

by:KangaRoo
ID: 2541704
I suppose you could create a specialization for greater<const char*>, something like

template<> class greater<const char*>
{
    public: bool operator()(const char* p1, const char* p2) const  {/*Your implementation*/}
};
0
Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

 

Author Comment

by:emitchell
ID: 2541792
I tried the specialization as follows:

#pragma warning (disable:4786)
#include <list>
#include <string>
using namespace std;

template<> class greater<const char*> {
     public: bool operator()(const char* p1
      , const  char* p2) const
    {/*Your implementation*/}
};
void
ListTest()
{
    list<const char*> l1;
    // sort with my own predicate function object     // (doesn't work)
    l1.sort(greater);
}

and VC6.0 produces the following somewhat incomprehensible message:

Compiling...
listtest.cpp
c:\users\race\test\stltests\listtest.cpp(6) : error C2934: 'greater<char const *>' : template-class-id redefined as a nested 'class' of '<Unknown>'
c:\users\race\test\stltests\listtest.cpp(14) : error C2275: 'greater' : illegal use of this type as an expression
        c:\program files\microsoft visual studio\vc98\include\functional(81) : see declaration of 'greater'
Error executing cl.exe.

Is the another way that Microsoft deviates from the standard?
0
 
LVL 7

Expert Comment

by:KangaRoo
ID: 2541854
>> c:\users\race\test\stltests\listtest.cpp(6) : error C2934: 'greater<char const *>' :
       template-class-id redefined as a nested 'class' of '<Unknown>'

Apparently VC does template specialization differently? You may have to check the documentation on the syntax for template partial specialization with VC.
The syntax for partial specialization I gave does works with gcc 2.8 and 2.95. Will test with Borland shortly (sorry, I don't have VC).

>> c:\users\race\test\stltests\listtest.cpp(14) : error C2275: 'greater' : ...
Indeed you can not do it like that. list::sort() can take an object, not  a template-name. I Suppose you could just:
   l1.sort();

BTW, make sure the specialization for greater<const char *> is visible before the list<> is specialized!
0
 
LVL 3

Expert Comment

by:LucHoltkamp
ID: 2542517
No... the syntax is ok, it should be:

template <>
struct greater<char*>
{
   bool operator()(const char*, const char*) const;
};

I tested it, and it indeed doesn't work. However if I replace greater with a class of my own it DOES work:

template <class T>
struct my_greater : public binary_function<T, T, bool>
{
   bool operator()(const T&, const T&) const;
};

template <>
struct my_greater<char*>
{
   bool operator()(const char*, const char*) const;
};

previous declaration is accepted by the compiler, just to show that the syntax is ok.... so what goes wrong? I don't know....
I guess it it's nice to ask this as a question here, to see if the other experts have an idea: why can't I specialize on greater ?

Luc
0
 
LVL 7

Expert Comment

by:KangaRoo
ID: 2542873
Mhmm, maybe it should be placed in namespace std?

namespace std {
  template<> class greater<const char*>
  {
     public: bool operator()(const char* p1, const char* p2) const  {/*Your implementation*/}
  };
};

0
 

Author Comment

by:emitchell
ID: 2544666
The use of namespace std {...} magicially makes the compiler message go away for the definition of the template<> greater<const char*>{...}

I can't pass this to the sort routine however as shown below:

namespace std {
template<> struct greater<const char*> {
    public: bool operator()(const char* p1, const char* p2) const  {/*Your implementation*/}
};
};
void
ListTest()
{
    list<const char*> l1;
    // sort with my own predicate function object (doesn't work)
    l1.sort(greater<const char*>);
}

produces the following error message:

listtest.cpp
c:\users\race\test\stltests\listtest.cpp(17) : error C2275: 'greater<char const *>' : illegal use of this type as an expression
        c:\users\race\test\stltests\listtest.cpp(7) : see declaration of 'greater<char const *>'
Error executing cl.exe.

I tried passing l1.sort(greater) without the template parameter greater<const char *> but with the same message!


I looked at the definition of class list { ... } which I believe was produced by Dinkumware (P.L.Plauger) for Microsoft.  Sort for lists with no argument uses operator<(...) via the merge routine.  This is the code for ordering inside merge(...):

void merge(_Myt& _X)
{if (&_X != this)
    {iterator _F1 = begin(), _L1 = end();
    iterator _F2 = _X.begin(), _L2 = _X.end();
    while (_F1 != _L1 && _F2 != _L2)
    if (*_F2 < *_F1)
        {iterator _Mid2 = _F2;
        _Splice(_F1, _X, _F2, ++_Mid2);
        _F2 = _Mid2; }
    else
    ++_F1;
    if (_F2 != _L2)
        _Splice(_L1, _X, _F2, _L2);
    _Size += _X._Size;
    _X._Size = 0; }}

where the key to the ordering is in the *_F2<*_F1.
I was able to define operator<(...) for the object inside the list and this works fine.

When one gives a predicate function object this is used as follows (in the merge(...) routine for ordering).  The predicate funtion is typedef'ed to greater<_Ty> and it is this that it seems impossible to substitute for.  This is the definition of the merger(...) function in the stl library <list>.

typedef greater<_Ty> _Pr3;
void merge(_Myt& _X, _Pr3 _Pr)
{if (&_X != this)
    {iterator _F1 = begin(), _L1 = end();
    iterator _F2 = _X.begin(), _L2 = _X.end();
    while (_F1 != _L1 && _F2 != _L2)
        if (_Pr(*_F2, *_F1))
            {iterator _Mid2 = _F2;
            _Splice(_F1, _X, _F2, ++_Mid2);
            _F2 = _Mid2; }
        else
            ++_F1;
        if (_F2 != _L2)
            _Splice(_L1, _X, _F2, _L2);
        _Size += _X._Size;
        _X._Size = 0; }}

Here the ordering is done by _Pr(*_F2,*_F1).

0
 
LVL 7

Expert Comment

by:KangaRoo
ID: 2545162
>>     l1.sort(greater<const char*>);
I suppose this should be
    l1.sort(greater<const char*>());
to create a temporary object.
0
 
LVL 3

Expert Comment

by:LucHoltkamp
ID: 2545335
Strange that it must be in namespace std....

It should be:

list.sort(greater<const char*>());

You pass an instance, not a type.

Luc
0
 
LVL 7

Expert Comment

by:KangaRoo
ID: 2545450
The unspecialized temlate lives in namespace std, so it makes some sense. Should check with the languge specs but reading that can be such an ordeal :(
0
 
LVL 3

Expert Comment

by:LucHoltkamp
ID: 2545463
Yes, I know, that's why I hoped you would check it out, because I think this is hard to find in the draft :-)

Luc
0
 
LVL 7

Expert Comment

by:KangaRoo
ID: 2545548
Would it be ok if I try to find that later? I'm trying to install NT, multiboot :(
0
 
LVL 3

Expert Comment

by:LucHoltkamp
ID: 2545562
Fine with me.. and success :-)
0
 

Author Comment

by:emitchell
ID: 2548936
I should have known that it needs a function object.

With the

l1.sort(greater<const char*>());

fixed, the  whole thing now compiles with VC6.

I have to file a bug report with Microsoft though it's debatable whether they will take any notice!

Great job folks.  Thanks for all the feedback.
0
 
LVL 7

Expert Comment

by:KangaRoo
ID: 2549734
You are welcome.

BTW, NT multi-boot failed :( the stupid OS has to boot from the primary partition of the first HD. Guess we'll have to use ghost...

Have a nice day.
0
 

Author Comment

by:emitchell
ID: 2825669
To complete the story on this question, I was able to get a response from Microsoft as follows (Case ID SRX000503600141). It involves editing the MFC source file for the <list> include file:

I am able to replicate the problem with the source code you send to me. The current STL list::sort function has some limitation.

In the current implementation of list::sort the template:
template<class Pred>
void sort(Pred pr);
is replaced by:
void sort(greater<T> pr);

This would cause the predicate function operator to never be called. It will
always use the base class.

The only way to get rid of this problem is to change the implementation of
sort function in list file.

The implementation should be:

template<typename _Pr3>
void merge(_Myt& _X, _Pr3 _Pr)

template<typename _Pr3>
void sort(_Pr3 _Pr)

Changing the std::greater::operator() to virtual is not going to help
because the list::sort takes the argument by value not by reference.


As second communication was as follows:

Instead of changing the implementation of the <list> header file, you can also override the struct greater because it is also implemented as a template in the file <functional>.

The code to override the struct greater is as:

template<> struct std::greater<CFinishInfo*>
 : public binary_function<CFinishInfo*, CFinishInfo*, bool> {
    bool operator()(const CFinishInfo* &x, const CFinishInfo* &y) const
     { return x->m_i < y->m_i; }
};



0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

How to install Selenium IDE and loops for quick automated testing. Get Selenium IDE from http://seleniumhq.org (http://seleniumhq.org) Go to that link and select download selenium in the right hand columnThat will then direct you to their downlo…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
The viewer will learn how to use and create keystrokes in Netbeans IDE 8.0 for Windows.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

743 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now