Seite 1 von 1
Container-Klasse, die Key-Zugriff (Hash) und Index bietet?
Verfasst: 23. September 2011 13:40
von mikemc
Hallo!
Ich habe eine Liste von Objekten, in der ich sowohl nach einen Key suchen möchte, als auch direkt per Index (wegen Model/View) zugreifen möchte.
Gibt es da irgendetwas fertiges, oder muss ich mir selber eine Wrapper-Klasse schreiben?
lg Michael
Re: Container-Klasse, die Key-Zugriff (Hash) und Index biete
Verfasst: 23. September 2011 16:59
von Christian81
Wenn Du schon auf Hash kommst warum nicht einfach mal QHash anschauen?
Re: Container-Klasse, die Key-Zugriff (Hash) und Index biete
Verfasst: 23. September 2011 19:14
von upsala
Nein, da gibt es nichts, du wirst dir also einen Wrapper bauen müssen. Von wievielen Elementen reden wir eigentlich?
Re: Container-Klasse, die Key-Zugriff (Hash) und Index biete
Verfasst: 23. September 2011 19:17
von Christian81
@upsala: Dann habe ich ihn falsch verstanden. Wenn Index == Key dann geht das doch...
Re: Container-Klasse, die Key-Zugriff (Hash) und Index biete
Verfasst: 23. September 2011 19:46
von upsala
Wenn QModelIndex==key dann geht das, aber dann werden Einfüge/Löschoperationen, die nicht am Ende stattfinden sehr langsam. Dann wäre eine QList/QVector wieder effektiver, da der Index meist der Row entspricht.
Ich ging aber davon aus, daß der key nichts mit der Position im Model zu tun hat.
Re: Container-Klasse, die Key-Zugriff (Hash) und Index biete
Verfasst: 26. September 2011 15:27
von mikemc
Ja Upsala, du hast mich richtig verstanden, Key != Index.
Anzahl der Elemente: Zwischen 100 und 10000. Warum die Frage?
Re: Container-Klasse, die Key-Zugriff (Hash) und Index biete
Verfasst: 26. September 2011 16:22
von upsala
Welche solche Fragen auch manchmal bei Listen kommen, bei denen es sich nicht lohnt.
Event. wäre es noch eine Möglichkeit, eine Liste vorzuhalten die immer nach dem Key sortiert ist, dann wäre eine Suche schnell und der Index-Zugriff auch.
Re: Container-Klasse, die Key-Zugriff (Hash) und Index biete
Verfasst: 26. September 2011 17:14
von mikemc
Hm eine gute Idee, allerdings müsste ich dann nach jedem Hinzufügen eines Eintrags sortieren
Re: Container-Klasse, die Key-Zugriff (Hash) und Index biete
Verfasst: 26. September 2011 17:27
von upsala
Wenn du sortiert einfügst, dann nicht.
Re: Container-Klasse, die Key-Zugriff (Hash) und Index biete
Verfasst: 26. September 2011 18:44
von mikemc
Hast recht! Ich hab mich jetzt trotzdem mal für die Wrapper-Klasse Variante entschieden, allerdings hab ich die Sache mit den Iteratoren leider garnicht durchschaut, hier der Code, den ich bis jetzt geschrieben habe:
Code: Alles auswählen
template < class T >
class CDataList
{
public:
class const_iterator
{
public:
inline const T& operator*()
{
}
inline bool operator != ( const const_iterator& ) const
{
}
inline const_iterator& operator++()
{
}
};
const_iterator begin() const { m_List.begin(); };
const_iterator end() const { m_List.end(); };
int size() const { return m_List.size(); };
const T& at( int i ) const { return m_List.at( i ); };
void append( const T & value ) { m_List.append( value ); };
void removeAt( int i ) { m_List.removeAt( i ); };
CDataList() {};
private:
QList < T > m_List;
QHash < int, T > m_Hash;
};
#endif // DATALIST_H
Ich habe leider überhaupt keinen Plan, welcher Code in den Iteratoren-Funktionen gehört. (m_Hash ist noch garnicht berücksichtigt)
Re: Container-Klasse, die Key-Zugriff (Hash) und Index biete
Verfasst: 27. September 2011 10:27
von franzf
Kommt halt drauf an, über was du iterieren willst. Ein Iterator, der sowohl die Liste als auch die Hash berücksichtigt macht mMn. keinen Sinn.
Ein "beginHash" und "beginList" usw. wären angebrachter, dann reicht ein typedef von QHash<int,T>::const_iterator auf (z.B.) hash_const_iterator, usw.
Deine Lösung wäre mir aber zu teuer:
* Wenn du Values in deiner Struktur hast, brauchst du immer zwei Kopien (was am Ende auch zu Inkonsistenz führen kann, da über non-const-Iteratoren die Werte geändert werden können, aber eben nur für eine Struktur)
* append und removeAt sind nicht trivial, da du immer hash und list abgleichen musst (existiert der key schon in der hash? -> in der Liste nach dem Element suchen -> Element austauschen -> has.insert(); removeAt muss über ALLES Hash-Einträge iterieren, um den value von list zu suchen)
Aber irgendwie überzeugt mich dein Konzept noch nicht so recht. Deine Unsicherheit bei der Umsetzung der Iteratoren macht mich auch stutzig.
Vielleicht kannst du mal kurz erklären, was du modellierst, wieso du QHash brauchst und warum die Lösung genau so ausschauen soll wie du es jetzt anstrebst, dann finden wir vllt. eine bessere Lösung.
Re: Container-Klasse, die Key-Zugriff (Hash) und Index biete
Verfasst: 27. September 2011 13:11
von mikemc
OK ich gehe mal bissl ins Detail:
Ich habe eine QGraphicsScene mit vielen QGraphicsItems. Manche sind rein grafischer Natur, manche sind mit Daten verknüpft. Die QGraphicsItems mit Daten sind bei mir in einer QList (mit Pointer). Für Listen die über das Model/View - Kozept index-basiert zugreifen ist das ideal, allerdings alles andere als Ideal ist es, wenn ich nach einem bestimmten Key in der Liste suchen möchte. Daher der Wunsch nach einer eigenen Container-Klasse mit 2 verschiedenen Listen.
Einen Iterator brauche ich eigentlich nur desshalb, weil ich schon sehr oft 'foreach' in meinem Code habe. Iterieren brauch ich natürlich nur über eine von den beiden Listen, das genügt vollkommen.
Re: Container-Klasse, die Key-Zugriff (Hash) und Index biete
Verfasst: 28. September 2011 21:00
von upsala
Probiers mal damit:
http://www.weinzierl-stefan.de/qt/sortedlist.h
Ist aber nicht komplett getestet und noch überarbeitungswürdig.
Re: Container-Klasse, die Key-Zugriff (Hash) und Index biete
Verfasst: 3. Oktober 2011 09:47
von mikemc
Danke, vielleicht komm ich darauf noch zurück, momentan hab ich es mal mit einem typedef gelöst... ob ich damit durchkomme weiß ich noch nicht.
Code: Alles auswählen
template < class T >
class CDataList
{
public:
typedef typename QList<T>::const_iterator const_iterator;
const_iterator begin() const { return m_List.begin(); };
const_iterator end() const { return m_List.end(); };
int size() const { return m_List.size(); };
const T& at( int i ) const { return m_List.at( i ); };
void append( const T & value )
{
m_List.append( value );
m_Hash.insert( value->getKey(), value );
}
void removeAt( int i )
{
T pContainer = m_List.at( i );
if ( pContainer )
{
m_Hash.remove( pContainer->getKey() );
m_List.removeAt( i );
}
}
private:
QList < T > m_List;
QHash < int, T > m_Hash;
};