W mojej grze, gdy obiekt wchodzi do czujnika, muszę dodać go do listy, a kiedy obiekt opuści czujnik, należy go usunąć z tej listy. Muszę też szybko znaleźć ten obiekt.Która struktura danych byłaby najlepsza dla tego?
Więc zasadniczo:
muszę to zrobić: szybkie dodawanie, usuwanie i szybkie szybkie znalezisko.
Jaki rodzaj struktury danych byłby najlepszy dla tego, biorąc pod uwagę, że w dowolnym momencie, struktura będzie miała około 10 obiektów.
Dzięki
Z 10 obiektów cokolwiek zrobi (std::vector, deque lub set) i nikt nie może powiedzieć, który z nich działa lepiej przed profilowaniem.
Jeśli nie wiesz, czego możesz użyć, być może przekonasz się, że std::set ma ładniejszą składnię do wyszukiwania elementów. To właśnie bym użył w tej sytuacji, ponieważ nie chciałbym pisać std::find(v.begin(), v.end(), sensor), gdzie mógłbym po prostu napisać s.find(sensor).
Nie należy jednak używać std::list jako porady ogólnej. Musisz mieć przekonujący powód, aby korzystać z list połączonych w C++ (stałe składanie w czasie to jeden, brak unieważnienia iteratora to inny). Inne struktury danych działają lepiej w przypadku większości operacji (z wyjątkiem łączenia). Tutaj nie widzę sensu używania list zamiast np.. set.
Dobre rady dotyczące list. –
Zestaw zapewnia dobrą szybkość wyszukiwania, ale wstawianie i usuwanie elementów nie jest tak szybkie, jak listy. Należy rozważyć, która operacja jest częściej wykonywana. – neodelphi
@neodelphi: Wykreślanie * gdzie * wstawianie lub usuwanie jest szybsze w zestawach niż na listach. Więc nie byłbym tak kategoryczny jak ty. Co więcej, wstawianie i usuwanie w wektorach 10 elementów może być znacznie szybsze niż na listach (ze względu na lokalizację danych). Naprawdę nie jest jasne, który kontener jest lepszy pod względem wydajności, ale mocno wierzę, że 'std :: list' jest z tyłu. Dobrym pomysłem jest zmuszanie się do używania list tylko wtedy, gdy jest to wymagane, ponieważ mają bardzo słabą ogólną wydajność. –
Szybkie dodawanie, szybkie usuwanie i szybkie wyszukiwanie, nie chcesz wiele! Biorąc pod uwagę to, co powiedziałeś, powiedziałbym listę połączoną, ale zależy to również od częstotliwości dodawania, usuwania i znajdowania. Jeśli znajdujesz się o wiele częściej niż dodajesz lub usuwasz, rzeczy się zmieniają.
Naprawdę jedynym sposobem jest wypróbowanie kilku różnych opcji i ich ustawienie.
Myślę, że lista powiązana byłaby najlepsza. Biorąc pod uwagę mały rozmiar, zmiana wskaźników nie wpłynie na wydajność.
> Potrzebuję go: szybkiego dodawania, szybkiego usuwania i szybkiego wyszukiwania. QuickStruct to sposób na przejście – unkulunkulu
Co dokładnie oznacza QuickStruct? – jahhaj
Wyimaginowana idealna struktura danych. – unkulunkulu