Struct vs STL

Question

Witam, przeglądając różne skrypty odnośnie algorytmiki oraz rozwiązywania zadań konkursowych spotkam się z dwoma sposobami implementacji struktur danych. Np graf, w niektórych pracach jest reprezentowany przez własna strukturę, i w innych przez szablony z stl'a(tablica vectorów).

Który z tych sposobów jest lepszy, szybszy i bardziej przejżysty w implementacji?

Answer 1

Nie da się tego stwierdzić bez zagłębienia w poszczególne implementacje i sam problem algorytmiczny.

Ogólnie szablony STL, są dość dobrze zoptymalizowane, ale optymalizacje robione są właśnie dla ogólnego przypadku, więc na pewno nie jest to najlepsze możliwe rozwiązanie.

Samych szablonów warto użyć jedynie przy projektowaniu, wstępnym pisaniu kodu gdzie potrzebujesz jakiego kontenera na szybko i nie obchodzi cię w tym momencie implementacja kontenera, bo np. klient oczekuje na jakieś szybkie demko realizujący jakiś algorytm i nie obchodzi go to na jakiej strukturze go zrealizujesz, tylko czy sam kod działa (to rozwiązanie ma też taką zaletę, że w razie problemów/niedziałającego kodu masz pewność że wina leży po stronie implementacji algorytmu, a nie dodatkowo samodzielnie pisanej struktury).

Później w fazie optymalizacji warto jest zastąpić strukturę dostarczoną przez standard, przez swoją własną zoptymalizowaną do konkretnego przypadku.

Answer 2

Nie da się w żaden sposób tego stwierdzić patrząc na to z góry ( na STL-a ). Każdą implementacje trzeba rostrzygnąć osobno, co nie zmienia faktu, że ludzie robiący STL-a najprawdę dobrze to zoptymalizowali. Np. Sortowanie w STL działa w czasie n * log(N) i nie ma dużej stałej bo nie spamiętuje dodatkowych rzeczy. Chodź patrząc na Seta lub Mape to również działa bardzo szybko ale żre bardzo dużo pamięci i ma dużą stałą bo spamiętuje dodatkowe rzeczy