bind2nd problem

thomassteiner

hi leute,
ich würde zur übung gerne einen eigenen kleinen quicksort schreiben:

struct some_type;
typedef some_type value_type;
typedef std::vector <value_type> container_type;
typedef container_type::iterator iterator_type;
typedef bool (* compare_type) (value_type const &, value_type const &);
bool compare (value_type const & lhs, value_type const & rhs);
void sort (iterator_type begin, iterator_type end, compare_type compare);

void sort (iterator_type begin, iterator_type end, compare_type compare) {
    if (begin != end) {
		iterator_type pivot = std::partition(begin, end, std::bind2nd(compare, *begin));
        sort (begin, pivot, compare);
		sort (std::max(begin + 1, pivot), end, compare);
    }
}

die hilfsfunktion compare:

bool compare (value_type const & lhs, value_type const & rhs) {
	return lhs.key < rhs.key;
}

anscheinend kann ich "compare" als binäre funktion nicht direkt an "partition" übergeben, da eine unäre funktion erwartet wird. daher wird bind2nd verwendet.

der compiler spuckt nun folgende fehlermeldung aus:

error C2825: '_Fn2': must be a class or namespace when followed by '::'

was mache ich falsch? warum nimmt bind2nd mein compare nicht an?
die schnittstelle von compare darf übrigens nicht verändert werden... wie bringe ich den code zum laufen?

FireFlow

Anstelle des Typedefs solltest du ein Template verwenden, das macht die Sache schonmal viel flexibler. Hab nicht weiter hingeschaun, hoffe das hilft dir mal weiter.

Gruß

Werner Salomon

thomassteiner schrieb:

iterator_type pivot = std::partition(begin, end, std::bind2nd(compare, *begin));
anscheinend kann ich "compare" als binäre funktion nicht direkt an "partition" übergeben, da eine unäre funktion erwartet wird. daher wird bind2nd verwendet.

der compiler spuckt nun folgende fehlermeldung aus:

error C2825: '_Fn2': must be a class or namespace when followed by '::'

was mache ich falsch? warum nimmt bind2nd mein compare nicht an?

Hi Thomas,

std::bind2nd erwartet lt. Standard bestimmte typedefs. Dazu werden Adapter zur Verfügung gestellt, die diese typedefs generieren. Dein Helferlein heißt hier: std::ptr_fun, der einen pointer_to_binary_function generiert.

iterator_type pivot = std::partition(begin, end, std::bind2nd( std::ptr_fun( compare ), *begin));

Dummerweise landest Du dann beim 'reference to reference'-Problem; siehe hier http://www.boost.org/libs/utility/call_traits.htm.

thomassteiner schrieb:

die schnittstelle von compare darf übrigens nicht verändert werden... wie bringe ich den code zum laufen?

am besten Du nimmst gleich boost::bind

Gruß
Werner

Am besten nimmst du gleich einen Funktor.

Ringding

Genau. Und den musst du von binary_function ableiten, damit er adaptable wird (das ist das, was bind2nd verlangt).

Werner Salomon

Ringding schrieb:

Genau. Und den musst du von binary_function ableiten, damit er adaptable wird (das ist das, was bind2nd verlangt).

Im Prinzip ja, aber doch wieder nein :xmas1: , weil so landet man ohne besondere Verenkungen wieder beim 'reference of reference'-Problem. Wenn schon Funktor, dann ein Funktor der das bind2nd mit einschließt. Etwa so:

template< typename T >
struct Comp
{
    typedef bool (*comp_type)( const T& a, const T& b );
    Comp( comp_type comp, const T& fix ) : m_comp( comp ), m_fix( fix ) {}
    bool operator()( const T& x ) const
    {
        return (*m_comp)( x, m_fix );
    }
private:
    comp_type m_comp;
    T   m_fix;
};
// Factory-Funktion
template< typename T >
Comp< T > make_comp( typename Comp< T >::comp_type comp_func, const T& fix )
{
    return Comp< T >( comp_func, fix );
}

und so in der Anwendung

//        iterator_type pivot = std::partition(begin, end, std::bind2nd(compare, *begin));
        iterator_type pivot = std::partition(begin, end, make_comp( compare, *begin ) );

.. mit boost wär' alles einfacher, hier schreibt man einfach

iterator_type pivot = std::partition(begin, end, boost::bind( compare, _1, *begin ) );

:xmas2: Werner

PS.: übrigens; die Weihnachts-Icons sind

Artchi

Da boost::bind seit längerem definitiv im TR1 des ISO C++ drin ist, kann man es bedenkenlos benutzen. Wird also eh bald bei jedem Compiler (auch VC++) mit beiligen. Nur halt unter dem Namespace std::tr1 und nicht boost::.