C++ Datenstruktur um rekursiv Ordner+File-Namen abzulegen

[T_55]

Hallo,

ich suche ich eine möglichst simple Datenstruktur um von einem gegebenen Ordner alle Unterordner/Files aufzulisten.

Mit

for(const auto & entry : std::filesystem::recursive_directory_iterator(verzeichnis))

würde ich mir die Sachen holen

Idee:

struct struct_tree
{
   std::string name;
   std::set<struct_tree> data;
}

Ein Folder hätte ein wiederum gefülltes set und eine file hat kein gefülltes set so hat man schon mal den Unterschied. Alles wäre nach Namen sortiert. Mir wäre es auch lieber wenn die Folder jeweils vor den Dateien gelistet werden.
Allerdings wie kann ich wiederum diese Struktur auslesen um zB ein QTreeWidget damit zu füttern oder was anderes damit zu machen?

Ist der Ansatz ok oder gibts für den Zweck ein anderen Standart-Weg? Performance ist völlig egal am liebsten möglichst einfach.
Gruß

 

[new Account()]

Statt über die Indirektion mit "gefülltes Set => Ordner" zu gehen, kannst du auch einfach std::variant nutzen (quasi das moderne tagged union).
Das ist nicht nur schöner, sondern du vermeidest auch Probleme wie leere Ordner, welche kein gefülltes Set haben, aber trotzdem Ordner sind.

Für "Ordner vor Dateien"-Sortierung kannst du einfach einen Vektor statt ein Set benutzen und diesen mit einem benutzerdefinierten Vergleichsoperator sortieren lassen.
Kleiner Nebenefekkt: deutlich schneller

Oder du trennst Ordner und Dateien im Knoten auf zwei Member auf:
Ein Ordner hat dann eine Liste von Dateien und eine Liste von Ordnern.
Eine Datei hat gar nichts.

Letzteres ist effizienter.



QTreeWidget? keine Ahnung - QT nie wirklich genutzt

 

[Fortatus]

Vllt ist eine (unordered_)multimap das richtige:
Das Filesystem einmal reinladen, Key=Übergeordnetes Verzeichnis und Value=Dateiinhalt, Metadaten o.ä.

Dann kannst du einfach ein map.equal_range() machen und kriegst alle Elemente eines Ordners zurück. Wenn du von einem Ordner aus in alle Unterordner gehen willst, musst du halt rekursiv/iterativ auf die gefundenen Elemente jeweils aus der Value die Ordner herauslesen und erneut equal_range() aufrufen.

Beispiel:

• Ordner1
  • Ordner1_1
    • Ordner1_1_1
      • Datei1_1_1_1
    • Datei1_1_1
    • Datei1_1_2
  • Ordner1_2
  • Datei1_1
  • Datei1_2
• Ordner2

Dann sind die Key,Value-Paare: (jetzt als Beispiel z.B. als String)
</;/Ordner1>
</;/Ordner2>
</Ordner1;/Ordner1_1>
</Ordner1;/Ordner1_2>
</Ordner1;Datei1_1>
</Ordner1;Datei1_2>
</Ordner1_1;/Ordner1_1_1>
</Ordner1_1;Datei1_1_1>
</Ordner1_1;Datei1_1_2>
</Ordner1_1_1;Datei1_1_1_1>

Wenn du nur möglichst schnell einzelne Ordner mit Inhalt abrufen willst, könnte unordered_multimap am besten sein. Wenn du dann auch noch durch alle Unterverzeichnise iterieren willst, ist multimap besser. Musst du mal ausprobieren. Das ist ja eine winzige Änderung im Code, beide Container auszuprobieren.

 

[blöderidiot]

Würde nicht auch ein lineares, wachsendes Array: AllFiles *files; (o. ä.) gehen?

struct AllFiles {
  int level;   # 0 = root, 1 = usw.
  string dn;   # Directory name
  string fn;   # File name
} ;

 

[m.c.ignaz]

Wie benutzt du denn das QTreeWidget bzw. warum ueberhaupt der Zwischenschritt? Kannst du im QTreeWidget nicht die std::filesystem API direkt benutzen?

 

[kuddlmuddl]

Es gibt direkt ein QFileSystemModel
Dh man braucht keine eigene Datenstruktur dafür:
https://www.bogotobogo.com/Qt/Qt5_QTreeView_QFileSystemModel_ModelView_MVC.php

 

[T_55]

Danke für den Input, als Hobbycoder waren mit da einige Wege ehrlich gesagt zu kompliziert die sicherlich gut sind, habe es jetzt erstmal mit diesem struct Ansatz gemacht: ein Ordner kann rekursiv ein Ordner besitzen und jeder Ordner hat einfach eine Liste für die Dateien. Rekursion mit Daten ist irgendwie lustig fürs Hirn, war aber auch das erste mal
//-------------
Nochmal kurz eine andere Frage zu std::filesystem. Wenn ich das Programm per shell-skript von einem anderen Ort zB Desktop starte dann stimmt der Pfad von std::filesystem nicht. Ich bekomme dann den Pfad vom user-Verzeichnis aber nicht den korrekten Pfad. Ich kann in diesem Fall da QT Anwendung QCoreApplication::applicationDirPath() nutzen das funktioniert korrekt aber mich würde mal interessieren ob man nicht std::filesystem auch zum korrekten Verhalten bringen kann?
Gruß

 

[firespot]

Idee:

struct struct_tree
{
   std::string name;
   std::set<struct_tree> data;
}

Ein Folder hätte ein wiederum gefülltes set und eine file hat kein gefülltes set so hat man schon mal den Unterschied.

Wenn du Glück hast kompiliert das gar nicht. Falls doch, führt es zu Undefniertem Verhalten: Ein std::set darf (wie das allermeiste der Standardbibliothek) nicht mit einem incomplete type instanziiert werden. Generell sind sich incomplete types mit by-value Semantik oder der Standardbibliothek im Wege.
Für eine rekursive Datenstruktur müsstest du wohl auf pointer wechseln. Bei modernem C++ kommen da natürlich gleich std::unique_ptr oder std::shared_ptr in den Sinn, aber Achtung: Die Regeln zur Instanziierung mit incomplete types sind für diese smart-ptr zwar etwas entspannter als für den Rest der Standardbibliothek, aber abhängig von den genauen Memberfunktionen die du nutzt, ev. noch immer nicht entspannt genug:

https://howardhinnant.github.io/incomplete.html
https://stackoverflow.com/questions/9954518/stdunique-ptr-with-an-incomplete-type-wont-compile

Mit einem raw pointer - selbstverständlich ordentlich gekapselt in deiner Klasse mit geeignetem Destruktor, copy-constructor und copy-assigment operator (sowie ev. deren move-Äquivalenten), sollte es gehen. Auch in modernem C++ können raw pointer bei Bedarf genau das richtige Tool sein.
Ev. hilft auch die boost pointer container library weiter (keine Ahnung welche Bedingungen da für incomplete types gelten).

Ein ganz anderer Ansatz wäre z.B. in einer einzigen Datenstruktur die vollständigen Pfad- und Dateinamen zu speichern (alphabetisch sortiert wenn gewünscht), und dann per regex die Rekursion in die einzelnen Pfade zu abstrahieren.

 

[new Account()]

Ein std::set darf (wie das allermeiste der Standardbibliothek) nicht mit einem incomplete type instanziiert werden.

Incomplete type
The following types are incomplete types:

• the type void (possibly cv-qualified);
• incompletely-defined object types:
  • class type that has been declared (e.g. by forward declaration) but not defined;
  • array of unknown bound;
  • array of elements of incomplete type;
  • enumeration type from the point of declaration until its underlying type is determined.

Das struct ist weder void, noch ist es eine Vorwärtsdeklaration, noch ist es ein array, noch ist es ein Aufzählungstyp?

 

[firespot]

Das struct ist weder void, noch ist es eine Vorwärtsdeklaration, noch ist es ein array, noch ist es ein Aufzählungstyp?

Zum Zeitpunkt der Definition des Klassen-members vom Typ std::set<struct_tree> ist die Definition von struct_tree selbst noch nicht abgeschlossen.

Siehe auch https://www.drdobbs.com/the-standard-librarian-containers-of-inc/184403814: da kommen genau solche patterns vor. Meines Wissens nach gilt das für den aktuellen Standard weiterhin: Undefiniertes Verhalten

 

[T_55]

@firespot @new Account()
hatte es auch nicht wie in meinem ersten Hirngedanken oben gemacht, sondern wie so oft mit einem vector da mir das set genau aus solchen Gründen etwas zu umständlich war. Sortierung in Gui war dann eh über QT Funktion sortByColums().

So hab ich es jetzt:

struct struct_Folder
{
   std::string FolderName;
   std::vector<struct_Folder> ChildFolders;
   std::vector<std::string> Files;
}

in die Richtung wie hier beschrieben

Oder du trennst Ordner und Dateien im Knoten auf zwei Member auf:
Ein Ordner hat dann eine Liste von Dateien und eine Liste von Ordnern.
Eine Datei hat gar nichts.

ABER nochmal zur Frage zurück:

Nochmal kurz eine andere Frage zu std::filesystem. Wenn ich das Programm per shell-skript von einem anderen Ort zB Desktop starte dann stimmt der Pfad von std::filesystem nicht. Ich bekomme dann den Pfad vom user-Verzeichnis aber nicht den korrekten Pfad. Ich kann in diesem Fall da QT Anwendung QCoreApplication::applicationDirPath() nutzen das funktioniert korrekt aber mich würde mal interessieren ob man nicht std::filesystem auch zum korrekten Verhalten bringen kann?

 

[firespot]

@firespot @new Account()
hatte es auch nicht wie in meinem ersten Hirngedanken oben gemacht, sondern wie so oft mit einem vector da mir das set genau aus solchen Gründen etwas zu umständlich war. Sortierung in Gui war dann eh über QT Funktion sortByColums().

So hab ich es jetzt:

struct struct_Folder
{
   std::string FolderName;
   std::vector<struct_Folder> ChildFolders;
   std::vector<std::string> Files;
}

in die Richtung wie hier beschrieben

Es spielt keine Rolle ob du einen std::vector oder ein std::set oder sonstiges verwendest: Du instanzierst die mit einem incomplete type, da zum Zeitpunkt der Instanziierung dieser Typen als data-member der Klasse die Definition der Klasse selbst noch nicht abgeschlossen ist. Die Container der Standardbibliothek verbieten das. Das meiste der Standardbibliothek verbietet meines Wissens nach das Rumwerkeln mit incomplete types.

Du kannst pointer verwenden, unter der Einschränkung dass die smart-ptr der Standardbibliothek auch nur unter bestimmten Umständen mit incomplete types funktionieren (siehe meine links in post #8). Wenn du raw pointer verwendest muss selbstverständlich die ownership policy klar definiert sein. Die praktische Challenge liegt eher darin das exception-safe hinzukriegen, allen voran wenn container mit raw pointern involviert sind.
Du kannst aber auch eine Basisklasse erstellen die mit den entsprechenden virtuellen Funktionen (aber nicht die data-members selbst !) ausgerüstet ist um die benötigte Funktionaliät bereitzustellen, und dann in einer davon abgleiteten Klasse smart-prt (oder Container mit smart-ptrn) auf die Basisklasse als entsprechende data-member speichern. Die Basisklasse ist ja dann vollständig definiert und die Rekursion deiner Datenstruktur über die Basisklasse funktioniert. Achte aber darauf, dass du dann die copy-semantic (copy-constructor / copy assignment operator) korrekt implementierst (Stichwort: deep copy, bzw. eine virtuelle clone()-Funktion in der Basisklasse, da du ja eigentlich die abgeleitete Klasse kopieren willst aber nur pointer auf die Basisklasse hast).

ABER nochmal zur Frage zurück:

Ich weiß zwar nicht genau was du machen willst, aber ich vermute das hilft dir?: https://stackoverflow.com/questions...ind-out-in-which-directory-your-executable-is
std::filesystem beruht ja auf boost::filesystem, somit wirst du in boost::filesystem vielleicht noch das eine oder andere nützliche auch finden.

Zu QCoreApplication::applicationDirPath() kann ich praktisch nichts sagen. Aber laut der Doku und so manchen schnell gegoogelten posts scheint das, je nach Plattform, auch nicht immer das zu tun was man glaubte es tut ...

 

[T_55]

Du instanzierst die mit einem incomplete type, da zum Zeitpunkt der Instanziierung dieser Typen als data-member der Klasse die Definition der Klasse selbst noch nicht abgeschlossen ist.

Von der Logik ist das auf jeden Fall nachvollziehbar finde ich, aber es scheint dennoch zu funktionieren. Bei mir kompiliert das ohne Fehler (GCC) und ich konnte auch in der Anwendung kein Fehler feststellen.

 

[m.c.ignaz]

Nochmal kurz eine andere Frage zu std::filesystem. Wenn ich das Programm per shell-skript von einem anderen Ort zB Desktop starte dann stimmt der Pfad von std::filesystem nicht. Ich bekomme dann den Pfad vom user-Verzeichnis aber nicht den korrekten Pfad. Ich kann in diesem Fall da QT Anwendung QCoreApplication::applicationDirPath() nutzen das funktioniert korrekt aber mich würde mal interessieren ob man nicht std::filesystem auch zum korrekten Verhalten bringen kann?
Gruß

Wie sieht denn der Pfad aus, mit dem du den std::filesystem:: path erstellst? Ich bin nicht sicher, dass ich die Frage bzw. das Problem ganz verstehe. Klingt als wuerdest du mit einem relativen Pfad arbeiten.

 

[T_55]

Wie sieht denn der Pfad aus, mit dem du den std::filesystem:: path erstellst? Ich bin nicht sicher, dass ich die Frage bzw. das Problem ganz verstehe. Klingt als wuerdest du mit einem relativen Pfad arbeiten.

Meine Schuld, ich habe fälschlicher Weise angenommen dass std::filesystem::current_path() mir den Pfad zum Ort wo die ausführbare Datei liegt ausgeben müsste (wie QCoreApplication::applicationDirPath()).
std::filesystem ist scheinbar nicht in der Lage diesen Pfad auszugeben daher dann je nach OS die spezifischen Lösungen: https://stackoverflow.com/questions/1528298/get-path-of-executable
Oder sowas für Multi-OS https://github.com/gpakosz/whereami (ungetestet)

 

[m.c.ignaz]

Falls es ne Option ist: argv[0] in main() ist der komplette Pfad zu deiner Exexutable (inkl. Dateiname und -endung). Den könntest du dir anfangs wegspeicher und darauf .stem() (glaube ich, siehe CPPReference) benutzen.

Edit:
Es waere .parent_path()
Kleines Beispiel: Klick