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ę.