Witam! Mam następujący problem:
potrzebuje struktury danych, w ktorej:
Chodzi mi o to abym mógł utworzyc listę obiektów, szukał obiektu o pewnej wartosci, zwracał jego kolejność a następnie usuwal go. czynność ta powtarzam n razy dla n elementow. chciałbym uzyskać złożoność rzędu n. wie ktoś jak to zrobić?
Nie da się. Gdyby się dało, to bym o czymś takim wiedział :D
Poza tym to powinno polecieć do Algorytmów, a nie do C++.
Edit:
Zakładając, że chodzi ci o listę łączoną, a nie coś typu ArrayList.
Edit2:
Z drugiej strony ArrayList to taki Vector, więc myślę, że nie chodziło o ArrayList :P
Rzędu n raczej nie osiągniesz, ale może się udać to zoptymalizować używając mieszaniny listy i wektora. Konkretniej to listę wektorów - dostęp zdecydowanie szybszy od zwykłej listy, ale znowu jest strata na dodawaniu i usuwaniu elementów. Szybko się dodaje na początek i na koniec, ale w środku niestety już nie jest tak kolorowo. Dużo zależy od tego jakiej wielkości będą te wektory.
Mnie się wydaje że najbliżej byłby jakiś LinkedHashSet, ale nie wiem czy jakieś c++owe frameworki takie coś udostępniają.
Można użyć jakiegoś drzewa, np. B+tree (http://en.wikipedia.org/wiki/B%2B_tree), przykładowa implementacja: http://www.python.org/dev/peps/pep-3128/.
Drzewo b+ jest fajnym rozwiązaniem jednak dziala ono poprawnie dla uporządkowanych danych a ja mam ciąg o dużej liczbie obiektów powtarzających się(niestety nie cyklicznie) między którymi różnica nie jest duża(max 60).
Jeśli dobrze zrozumialem to hash table to nic innego jak tablica wskaźników na obiekty. Przyspieszyłoby to program(niestety i tak nie do złożoności n) gdyby obiekty były duże a moje obiekty są bardzo małe(1 bajt)
Macie może jakieś inne pomysly o możliwie małej złożoności. Mi przychodzi jedynie aby przy stworzyć takie "punkty kontrolne" odległości w których przy każdej operacji aktualizowana byłaby odleglosc tego obiektu od początku a pobierając odleglosc od jakiegoś obiektu nie będącego takim punktem cofamy się do najblizszego punktu kontrolnego. tylko że to niestety jest złożoność n^2
Śmiedzi mi o jakimś zadaniem z OI. Konkretnie: Litery. Dobra rada - nie szukaj liniówki.
Też mi coś tak śmierdziało, ale tak czytam i myślę do czego może być potrzebna taka struktura danych... Nigdy bym nie wpadł na takie rozwiązanie :P
Możesz całkiem porządnie przyspieszyć Vector, używając memcpy. Dostaniesz mnie więcej to, o co Ci chodzi.
A jeśli memcpy będzie zbyt wolne możesz podzielić zbiór na kilka wektorów. Tu diabeł tkwi w słowie "kilka", trzeba użyć sprytnego algorytmu który będzie wszystko odpowiednio ważył/rozdzielał aby otrzymać optymalne rezultaty.
a moglbym prosic o jakis przyklad: link albo kod?
W Literach wystarczy drzewo + tablica najzwyklejszych list jednokierunkowych. Nie trzeba wektorów, kolejek, stosów i żadnego tego typu zabaw. Niedawno wkleiłem rozwiązanie w którymś temacie na tym forum.
Coś pomiędzy:
typedef std::shared_ptr<MyClass> MyClassGuard;
typedef std::unordered_map<int, MyClassGuard> map;