Witam,
Jakie struktury danych są zaimplementowane w bibliotece STL?
oprócz:
stosu - stack
kolejki - queue
sterty - heap
wektora;P
jakieś drzewa poza stertą są albo jeszcze inne struktury?
zajrzałem do dokumentacji ale nie wszystko się wyłapie
pozdrawiam
listy, kolejki priorytetowe, stosy, zbiory, zbiory binarne, tablice asocjacyjne
@up czym sie rozni stworzenie priority_queue od stworzenie tego poprzez make_heap? sa jakies roznice w dzialaniu?
nie znalazlem tam drzewa BST.. jest zaimplementowane?
priority_queue to po prostu kolejna warstwa abstrakcji, podobnie jak std::stack. Za stos może robić vector ale w stack możesz wykonywać jedynie operacje jak na abstrakcyjnym stosie.
dobrze ale jest jakas roznica pomiedzy stworzeniem kolejki priorytetowej
przez priority_queue
a stworzeniem sterty przez make_heap
wkoncu sterta i kolejka priorytetowa to IMO to samo
no i jak jest z tym BST?:)
Różnica może być jeszcze taka, że kolejka się rozszerza dynamicznie a jak robisz make_heap na tablicy to za bardzo urosnąć nie może. I tak główna różnica to interfejs.
A o BST to nie słyszałem. Map jest robiony na drzewach czerwono-czarnych.
Drzewo czerwono-czarne to BST.
ale drobne roznice są..
Pawel200x.5 napisał(a)
Drzewo czerwono-czarne to BST.
?
No drzewo czerwono-czarne jest drzewem BST. Po prostu. Implementuje dodatkowe metody (jest rozszerzeniem BST), które zapewniają, że jest BST zrównoważonym.