Wyszukiwanie elementu w zbiorze na podstawie różnych kluczy

Witajcie!

Zastanawiałem się ostatnio nad takim problemem:
Mam strukturę różnych elementów, przykładowo:

struct dataContainer
{
	unsigned int ID;
	string name, shortName;
	char favouriteLetter;
	double latitude_DD, longitude_DD;
	unsigned long long int numberOfLostPants;
}

Załóżmy, że chcę móc szybko wyszukiwać elementy z danym ID. Nic prostszego. Lecz jak szybko wyszukiwać po ID, szybko wyszukiwać po favouriteLetter, szybko wyszukiwać po numberOfLostPants? Za szybko rozumiem szybciej niż log(n).

Na razie zastanawiałem się nad wykorzystaniem tablic mieszających, będących tablicami vectorów zawierających wskaźniki do elementów tablicy, po jednej dla każdej zmiennej i aktualizowaniu odpowiednich przy zmianie danych, np:

W tablicy mieszającej ID znajduję element z danym ID. W elemencie zmieniam numberOfLostPants, najpierw wyszukując w tablicy mieszającej po numberOfLostPants obecny element, usuwając wskaźnik do niego w tej tablicy, zmieniając wartość numberOfLostPants i dodając go z powrotem do tablicy mieszającej po numberOfLostPants. Myślałem także o trzymaniu wskaźników do wskaźników na element w tablicach mieszających, aby nie musieć ich wyszukiwać, tylko uzyskiwać bezpośredni dostęp przy usuwaniu.

Wydaje mi się to szybkim rozwiązaniem, jednak jest dosyć skomplikowane i zastanawiałem się, czy nie znacie lepszych rozwiązań?

Drugi, bardziej skomplikowany problem, to gdy mamy znaleźć nie elementy z dokładną wartością (np. ID=1024), a wszystkie elementy z przedziału (np. latitude_DD>12.0 && longitude_DD>24.0). Wtedy zastosowanie tablic mieszających wydaje się (a może nie mam racji?) mało pomocne.

Mam nadzieję, że moja wypowiedź jest zrozumiała, jeżeli nie, proszę dopytywać. Zamieściłbym kod, ale nie napisałem jeszcze ani linijki, wolę najpierw pomyśleć nad optymalnym rozwiązaniem, zanim się za to zabiorę.

Może troszkę zmienię pytanie, żeby od czegoś zacząć: czy da się wyszukiwać w ten sposób elementy w przedziale w czasie szybszym niż liniowy? Nawet niewiele, jak (n-log(n))

czy da się wyszukiwać w ten sposób elementy w przedziale w czasie szybszym niż liniowy
Elementy w zbiorze muszą być posortowane.

Nie wiem, ile tych elementów struktury będziesz miał, i jak będziesz je przechowywał (lista tych kontenerów czy coś innego). Pewnie jednak warto byłoby zrobić coś podobnego do tego co sugerujesz, i do tego co jest w bazach danych - indeksy, czyli dodatkowe listy sortowanych na bieżąco (przy wstawianiu elementów) par indeks-wartość (czy to lattitude czy inna). O ile nie jest krytycznym czas operacji innych, niż wyszukiwanie tych kontenerów.

Weź użyj jakieś bazy danych.

spartanPAGE napisał(a):

czy da się wyszukiwać w ten sposób elementy w przedziale w czasie szybszym niż liniowy
Elementy w zbiorze muszą być posortowane.

Tylko w jaki sposób? Gdyby miało to.być po jednej wartości, nic prostszego - ale po kilku?

fourfour napisał(a):

Nie wiem, ile tych elementów struktury będziesz miał, i jak będziesz je przechowywał (lista tych kontenerów czy coś innego). Pewnie jednak warto byłoby zrobić coś podobnego do tego co sugerujesz, i do tego co jest w bazach danych - indeksy, czyli dodatkowe listy sortowanych na bieżąco (przy wstawianiu elementów) par indeks-wartość (czy to lattitude czy inna). O ile nie jest krytycznym czas operacji innych, niż wyszukiwanie tych kontenerów.

Przechowywanie kontenerów w dowolnej strukturze, byleby spełniała moje założenia. Pomysł z listami ok, chociaż zmiany elementu widzę tak samo, jak w przykładzie z tablicami mieszającym. Druga sprawa, jak dojść do tych elementów, w których kilka wartości musi znajdować się w określonym przedziale, tak jak latitude i longtitude w przykładzie?

_13th_Dragon napisał(a):

Weź użyj jakieś bazy danych.

@_13th_Dragon,

zawsze ceniłem Twoje wypowiedzi na forum. Nie zależy mi na zrobieniu tego tak, żeby działało. Zależy mi na nauczaniu się i zrozumieniu, jak to działa.

Poczytaj o b-tree - to przestarzały ale prosty i darmowy silnik dla tworzenia baz danych.
W jaki sposób szukać - metoda połowienia (bisekcji) na dzień dobry daje ci O(log(n)), jak chwile się zastanowisz to da się zejść do O(log(log(n)))

merlinnot napisał(a):

Druga sprawa, jak dojść do tych elementów, w których kilka wartości musi znajdować się w określonym przedziale, tak jak latitude i longtitude w przykładzie?

Też tak samo, jak to się robi w bazach - indeks na kilku polach.

O, @_13th_Dragon dobrze w sumie Ci radzi :)

Moja rada - przeczytaj jak działają różne indeksy w bazie danych :-) ale od strony implementacji. Bo to jest dokładnie to o co pytasz.
Czasem to są tablice hashujące, czasem drzewa b+ albo b-, czasem masz indeksy bitmapowe albo gridowe. Rodzajów jest sporo i każdy jest dobry do czegoś innego :-)