Jaka jest podstawowa struktura danych zestawu STL w C++?

Question

Chciałbym wiedzieć, jak zestaw jest zaimplementowany w C++. Gdybym miał zaimplementować własny zestaw kontenerów bez użycia kontenera dostarczonego przez STL, jaki byłby najlepszy sposób na wykonanie tego zadania?

Rozumiem, że zestawy STL są oparte na abstrakcyjnej strukturze danych drzewa wyszukiwania binarnego. Więc jaka jest podstawowa struktura danych? Tablica?

Ponadto, jak działa insert() dla zestawu? W jaki sposób zestaw sprawdza, czy element już w nim istnieje?

Czytałem na wikipedii, że innym sposobem na wdrożenie zestawu jest tablica haszująca. Jak to działa?

Answer 1

Można zaimplementować przeszukiwania binarnego drzewa najpierw zdefiniowanie Node struct:

struct Node 
{ 
    void *nodeData; 
    Node *leftChild; 
    Node *rightChild; 
} 

Następnie można zdefiniować korzeń drzewa z innym Node *rootNode;

Wpis Wikipedia na Binary Search Tree ma dość dobry przykład jak zaimplementować metodę insertów, więc poleciłbym to sprawdzić.

Pod względem duplikatów zazwyczaj nie są one dozwolone w zestawach, więc można po prostu odrzucić to wejście, wyrzucić wyjątek itp. W zależności od specyfikacji.

Answer 2

Sposób implementacji konkretnego kontenera w C++ zależy wyłącznie od implementacji. Wystarczy spełnić wymagania określone w standardzie, takie jak złożoność różnych metod, wymagania dotyczące iteratorów itp.

Answer 3

Jak powiedział KTC, sposób w jaki std::set może się różnić - standard C++ po prostu określa abstrakcyjny typ danych. Innymi słowy, standard nie określa, w jaki sposób kontener powinien zostać wdrożony, tylko jakie operacje musi obsługiwać. Jednak większość implementacji STL, o ile mi wiadomo, korzysta z red-black trees lub innych zbalansowanych drzew wyszukiwania binarnego (GNU libstdC++, na przykład używa drzewek czerwono-czarnych).

Chociaż teoretycznie można zaimplementować zestaw jako tablicę asocjacyjną i uzyskać szybszą asymptotyczną wydajność (zamortyzowany O (długość klucza) w porównaniu z O (log n) dla wyszukiwania i wstawiania), który wymagałby podania przez użytkownika funkcji mieszania dla niezależnie od tego, jaki typ chcieli przechowywać (patrz: Wikipedia's entry on hash tables), aby dobrze wyjaśnić, jak działają. Jeśli chodzi o implementację binarnego drzewa wyszukiwania, nie chciałbyś używać tablicy - jak wspomniał Raul, chciałbyś mieć jakąś strukturę danych w postaci Node.

Answer 4

Rozumiem, że zestawy STL są oparte na abstrakcyjnej strukturze danych binarnego drzewa wyszukiwania. Więc jaka jest podstawowa struktura danych? Tablica?

Jak inni podkreślili, jest różna. Zestaw jest zwykle implementowany jako drzewo (drzewo czerwono-czarne, drzewo zrównoważone itp.), Ale mogą istnieć inne implementacje, które istnieją.

Co więcej, jak działa funkcja insert() dla zestawu ?

To zależy od podstawowej realizacji zestawu.Jeśli jest zaimplementowany jako drzewo binarne, to Wikipedia ma przykładową rekurencyjną implementację dla funkcji insert(). Możesz to sprawdzić.

W jaki sposób zestaw sprawdza, czy element już w nim istnieje?

Jeśli jest zaimplementowana jako drzewo, przechodzi przez drzewo i sprawdza każdy element. Jednak zestawy nie pozwalają na przechowywanie zduplikowanych elementów. Jeśli chcesz zestaw, który pozwala na powielanie elementów, potrzebujesz multiset.

czytałem na wikipedii, że inny sposób do zaimplementowania zestawu jest z hash tabeli. Jak to działa?

Możesz odwoływać się do hash_set, gdzie zestaw jest zaimplementowany przy użyciu tabel mieszania. Musisz podać funkcję skrótu, aby wiedzieć, w której lokalizacji przechowywać element. Ta implementacja jest idealna, gdy chcesz szybko wyszukać element. Jeśli jednak ważne jest, aby twoje elementy były przechowywane w określonej kolejności, wówczas implementacja drzewa jest bardziej odpowiednia, ponieważ możesz ją wykonać w przedsprzedaży, w trybie zamówienia lub postorder.