QtAlgorithms qSort mit Templates

[AlGaN]

Hallo, ich habe ein Problem mit den Algorithmen von Qt, in der Doku ist zu qSort leider nur ein Bsp. ohne Templates angegeben, ich brauche die Sortierung aber mit Template-Parameter und dazu noch inline

Mein Code (vereinfacht):

Code: Alles auswählen

#include <QtCore>

[...]

template <class MyType> class MyClass
{
public:
  MyClass()
  {
     for (int i = 0; i < 10; ++i) {
       Node* n = new Node();
       n->f = rand() % 10;
       listOfNodes << n;
     }
  }

  ~MyClass() {
     foreach( Node* node, listOfNodes ) {
       delete node;
  }

  // interne Node-Klasse
  class Node
  {
    public:
      Node* parent;
      Node* child;
      
      float f;
      
      Node()
        : parent( 0 ), child( 0 ),
          f( 0.0f )
      { }

      MyType myType;
    };

  void sortListOfNodes() {
    if ( !listOfNodes.isEmpty() )
      qSort( listOfNodes.begin(), listOfNodes.end(), &myCompare );
  }

  void printListOfNodes() {
    cout << "listOfNodes ";
    foreach (Node* n, listOfNodes ) {
      cout << node->f << " ";
    }
    cout << endl;
  }
  
  bool myCompare( const Node& x, const Node& y) {
    return ( x.f < y.f );
  }


  
  [...]
private:
  QList< Node* > listOfNodes;
};
  

Es soll sozusagen myCompare als Zeiger auf eine selbst definierte Vergleichsfunktion LessThan-Fkt. übergeben werden, leider funktioniert das im Zusammenhang mit Templates und Inline-Funktionen nicht.
Ich habe auch schon die volle Qualifizierung des Element-Zeigers versucht:

Code: Alles auswählen

qSort( listOfNodes.begin(), listOfNodes.end(), &MyClass<MyType>::myCompare );

da spuckt VC2005 Express auch Fehler aus:

D:\projekt\work\test\qtqsorttest>nmake

Microsoft (R) Program Maintenance Utility, Version 8.00.50727.42
Copyright (C) Microsoft Corporation. Alle Rechte vorbehalten.

"C:\Programme\Microsoft Visual Studio 8\VC\BIN\nmake.exe" -f Makefile.De
bug all

Microsoft (R) Program Maintenance Utility, Version 8.00.50727.42
Copyright (C) Microsoft Corporation. Alle Rechte vorbehalten.

cl -c -nologo -Zm200 -Zc:wchar_t- -Zi -MDd -GR -EHsc -W3 -w34100 -w34189
-DUNICODE -DWIN32 -DQT_LARGEFILE_SUPPORT -DQT_DEBUG -DQT_DLL -DQT_GUI_LIB -DQT_
CORE_LIB -DQT_THREAD_SUPPORT -I"..\..\..\..\Programme\Qt\4.3.2\include\QtCore" -
I"..\..\..\..\Programme\Qt\4.3.2\include\QtCore" -I"..\..\..\..\Programme\Qt\4.3
.2\include\QtGui" -I"..\..\..\..\Programme\Qt\4.3.2\include\QtGui" -I"..\..\..\.
.\Programme\Qt\4.3.2\include" -I"." -I"d:\Programme\Qt\4.3.2\include\ActiveQt" -
I"win_moc_debug" -I"." -I"..\..\..\..\Programme\Qt\4.3.2\mkspecs\win32-msvc2005"
-Fowin_obj_debug\ @C:\DOKUME~1\lk\LOKALE~1\Temp\nm48.tmp
qtqsorttest.cpp
.\qtqsorttest.cpp(91) : warning C4100: 'argv': Unreferenzierter formaler Paramet
er
.\qtqsorttest.cpp(91) : warning C4100: 'argc': Unreferenzierter formaler Paramet
er
d:\programme\qt\4.3.2\include\qtcore\../../src/corelib/tools/qalgorithms.h(374)
: error C2064: Ausdruck ergibt keine Funktion, die 2 Argumente übernimmt
d:\programme\qt\4.3.2\include\qtcore\../../src/corelib/tools/qalgorithms
.h(199): Siehe Verweis auf die Instanziierung der gerade kompilierten Funktions-
template "void QAlgorithmsPrivate::qSortHelper<RandomAccessIterator,T,LessThan>(
RandomAccessIterator,RandomAccessIterator,const T &,LessThan)".
with
[
RandomAccessIterator=QList<MyClass<int>::Node *>::iterator,
T=MyClass<int>::Node *,
LessThan=bool (__thiscall MyClass<int>::* )(const MyClass<int>::Node
&,const MyClass<int>::Node &)
]
.\qtqsorttest.cpp(32): Siehe Verweis auf die Instanziierung der gerade k
ompilierten Funktions-template "void qSort<QList<T>::iterator,bool(__thiscall My
Class<MyType>::* )(const MyClass<MyType>::Node &,const MyClass<MyType>::Node &)>
(RandomAccessIterator,RandomAccessIterator,LessThan)".
with
[
T=MyClass<int>::Node *,
MyType=int,
RandomAccessIterator=QList<MyClass<int>::Node *>::iterator,
LessThan=bool (__thiscall MyClass<int>::* )(const MyClass<int>::Node
&,const MyClass<int>::Node &)
]
.\qtqsorttest.cpp(29): Bei der Kompilierung der Klassen-template der vo
id MyClass<MyType>::sortListOfNodes(void)-Memberfunktion
with
[
MyType=int
]
.\qtqsorttest.cpp(110): Siehe Verweis auf die Instanziierung der gerade
kompilierten Klassen-template "MyClass<MyType>".
with
[
MyType=int
]
d:\programme\qt\4.3.2\include\qtcore\../../src/corelib/tools/qalgorithms.h(379)
: error C2064: Ausdruck ergibt keine Funktion, die 2 Argumente übernimmt
d:\programme\qt\4.3.2\include\qtcore\../../src/corelib/tools/qalgorithms.h(381)
: error C2064: Ausdruck ergibt keine Funktion, die 2 Argumente übernimmt
d:\programme\qt\4.3.2\include\qtcore\../../src/corelib/tools/qalgorithms.h(389)
: error C2064: Ausdruck ergibt keine Funktion, die 2 Argumente übernimmt
d:\programme\qt\4.3.2\include\qtcore\../../src/corelib/tools/qalgorithms.h(389)
: fatal error C1903: Weiterverarbeitung nach vorherigem Fehler nicht möglich; Ko
mpilierung wird abgebrochen.
NMAKE : fatal error U1077: ""C:\Programme\Microsoft Visual Studio 8\VC\BIN\cl.EX
E"": Rückgabe-Code "0x2"
Stop.
NMAKE : fatal error U1077: ""C:\Programme\Microsoft Visual Studio 8\VC\BIN\nmake
.exe"": Rückgabe-Code "0x2"
Stop.

Nachtrag: Ok, ich hab nach einigem weiteren Suchen gelesen, dass die eigene definierte Vergleichsmethode ( myCompare in meinem Fall ) global definiert sein muss und dass im Fall von Pointern in den Containern Pointer auf Elemente übergeben werden müssen, so wie in der angefügten Funktion:

Code: Alles auswählen

[...]
// ausserhalb von MyClass<MyType>

bool myCompare( const Node* a, const Node* b ) {
  return a->f < b->f;
}

Das Problem ist, dass die Klasse Node innerhalb von MyClass<MyType> definiert ist und damit ausserhalb dieser Klasse nicht bekannt... irgendwelche Lösungsmöglichkeiten ?


Bin für jeden Tipp dankbar,
AlGaN

[DeepDiver]

Versuch mal Node* als Parameter Deiner Methode myCompare.

Viel Glück,

Tom

[AlGaN]

Hallo DeepDiver,

danke für Deine Antwort,

ja, ich hab wie gesagt, schon gelernt, dass die Parameter Pointer auf Elemente sein müssen, da ja im Container auch Pointer auf Elemente stehen, also z.B.

Code: Alles auswählen

bool myCompare(const Node* a, const Node* b)
{
  return a-f < b->f;
}

aber das löst leider noch nicht das Problem, dass sich die Klasse Node innerhalb einer Template-Klasse MyClass<MyType> befindet und deshalb von einer global definierten Vergleichsfunktion (die ja so anscheinend vom Algorithmus qSort gefordert wird), nicht sichtbar ist.

Update: Ich habe inzwischen ein anderes Design ausprobiert, mit dem es funktioniert, das aber keine verschachtelten Klassen mehr enthält:

Code: Alles auswählen

template<class MyType> class Node
{
public:
  Node* parent;
  Node* child;
    
  float f;

  Node()
    : parent( 0 ),
      child( 0 ),
      f( 0.0f ),
  { };

  MyType myType;
};


template<class MyType> class MyClass
{
  friend class Node<MyType>;
public:
  MyClass()
  {
    for (int i = 0; i < 10; i++ ) {
      Node<MyType>* n = new Node<MyType>();
      n->f = rand() % 10;
      listOfNodes << n;
    }
  }

  ~MyClass()
  {
    if ( !listOfNodes.isEmpty() ) {
      foreach (Node<MyType>* node, listOfNodes) {
	delete node;
      }
    }
  }

  void sortListOfNodes() {
    if ( listOfNodes.isEmpty() )
      return;
    qSort( listOfNodes.begin(), listOfNodes.end(), myCompare<MyType> );

  }

  void printListOfNodes() {
    cout << "listOfNodes: ";
    foreach( Node<MyType>* node, listOfNodes ) {
      cout " " << node->f << " ";
    }
    cout << "\n";
  }

private:
  QList< Node<MyType>* > listOfNodes;
};

template<class MyType> bool myCompare( const Node<MyType>* x, const Node<MyType>* y )
{
  return x->f < y->f;
}

So funktioniert es, indem die (Template-)Klasse Node<MyType> als friend von der Template-Klasse MyClass<MyType> definiert wird.
So ein Design nennt sich anscheinend bound-Freunde, da die Typ-Parameter 1:1 auch auf die befreundete (Template-)Klasse angewendet werden.
Nachteil ist eben die Sichtbarkeit der internen Verwaltungsklasse Node, aber wenigstens kompiliert es so.

Thx,
AlGaN

[Christian81]

als static in der Klasse geht es auch.

[AlGaN]

Hallo Christian,

ja, eine static-Funktion hat als globale Funktion ebenso eine von außen zugreifbare Adresse, aber meines Wissens kann ich in einer static-Funktion nicht auf die Nicht-Static-Elemente zugreifen, d.h.

Code: Alles auswählen

template class<MyData> MyClass
{
[...]

static bool myCompare(const Node* a, const Node* b)
{
  return a-f < b->f;
}

[...]
};

funktioniert nicht, da eine static-Funktion auf das public Nicht-Static-Element f keinen Zugriff hat, auch wenn es sich in einer anderen verschachtelten Klasse befindet, zum. fkt. obige Syntax nicht

[Christian81]

ich glaube wir sollten da nochmal ein C++-Buch wälzen - warum sollte das nicht gehen?