Czy istnieje kontener STL dla danych modelu hierarchicznego?

Question

Dla warstwy modelu niezależny od platformy, mam danych hierarchicznych (ciągi, faktycznie), które wyglądają tak:

• Pozycja A
  • podpunkt
  • podpunkt B
  • podpunkt C
    • SubSubItem A
    • SubSubItem B
  • podpunkt D
• Pozycja B
• Pozycja C

Teraz, w obrębie każdego "poziom" (punkt, podpunkt, SubSubItem, itd.) Elementy muszą być posortowane alfabetycznie.

Wydaje się, że prostym rozwiązaniem byłoby stworzenie prostej klasy z posortowaną std :: Vector lub std :: MultiMap do śledzenia jej dzieci i wskaźnika do rodzica. (i jeden element główny). Będę potrzebował na ogół iterować przez dzieci każdego przedmiotu w kierunku do przodu.

Po zakończeniu budowy/sortowania nie trzeba dodawać ani usuwać elementów. Ogólnie mała liczba przedmiotów (setki).

Ta funkcja służy do modelowania danych podkładu kontrolki w stylu konspektu.

Toczenie prostej klasy byłoby łatwe, ale jest to taki powszechny wzorzec - czy nie ma już gotowego kontenera STL z takim zachowaniem?

Answer 1

Nic w samej STL, ale może okazać się to przydatne:

tree.hh: an STL-like C++ tree class

Jego API następujące kontenery STL dokładnie i powinna zrobić to, czego szukasz.

Wierzę, że their example jest dokładnie tym, o co pytasz (drzewo z łańcuchami), w rzeczywistości.

Answer 2

Nie. Nie chcę być nieostrożny, ale taka jest odpowiedź; patrz np. Josuttis lub standard. Będziesz musiał utworzyć klasę, która będzie wskazywać rodzic/dziecko zgodnie z sugerowanymi przez ciebie liniami i użyć wektora lub innego standardowego pojemnika z tymi.

Answer 3

Odpowiedź na pytanie brzmi: nie, w drzewie STL nie ma drzewa. Wzorce, które zasugerowałeś, są w porządku. Zobacz także this question.

Answer 4

Proste rozwiązanie:

Twoje klucze są std::vector<GUID>, gdzie GUID jest jakiś rodzaj (może GUID lub wskaźnik, lub ciąg znaków), który jednoznacznie identyfikuje każdy element. Dzieci elementu mają po prostu te elementy "prefiks".

Dopóki twoje GUID można sortować za pomocą operator<, sortowanie leksykograficzne na std::vector spowoduje, że elementy będą wyglądać w żądanej kolejności.

Może to być Twój kontener lub std::vector< std::pair< GUID, Value > >, który sortujesz ręcznie przez .first.

Jeśli typ GUID może mieć „ostatni element”, można znaleźć każde dziecko {x,y,z} poprzez znalezienie lower_bound o {x,y,z} i upper_bound z {x,y,z,last_guid}. Nadanie jej "ostatniego elementu" jest zaletą polegającą na nieużywaniu gołego wskaźnika.