Wyzwanie - wydajny uporządkowany zbiór w C++

      Dużo jest dostępnych bibliotek C++ implementujących uporządkowany zbiór z możliwością modyfikowania i wyszukiwania (i nie tylko) w czasie Log(N), gdzie N jest ilością danych przechowywanych w zbiorze. Szablony  takie jak std::set, std::map, QMap z biblioteki standardowej i biblioteki QT, oferują taką możliwość.  Szablony te oferują taką możliwość dzięki temu, że zostały zaimplementowane w oparciu o strukturę danych nazywaną drzewami czerwono-czarnymi (ang red-black trees). Strukturami o podobnych możliwościach są drzewa AWL, B-Drzewa, 2-3-4 drzewa, a także po prostu wszelkie drzewa wyszukiwań (nie koniecznie wyszukiwań binarnych) z dowolnym mechanizmem równoważenia.

      Drzewa bez  mechanizmu równoważenia nie zawsze gwarantują szybkie wyszukiwe, modyfikowanie (i kilka innych operacji) w czasie logarytmicznym Log(N). Gdy dane do drzewa nie są wstawiane w kolejności losowej, to drzewa bez mechanizmu balansowania mogą mieć bardzo duże głębokości lub mogą wręcz zdegenerować się do listy. Wykonanie operacji takich jak: maksimim, minimum, search, upperBound, lowerBound, może być także wykonane efektywnie na zwykłej uporzdkowanej (posortowanej) tablicy, dzięki wyszukiwaniu binarnemu. Jednak gdy tablica zawiera dużo elementów, to modyfikowanie tablicy jest bardzo czasochłonne.

      Wracając do wyzwania, istnieją gotowe szablony oferujące możliwości o jakich mowa. Przykładami takich szablonów są właśnie std::set, std::map, QMap. Wszystkie te szablony są przykładami bardzo dobrze zaimplementowanych drzew czerwono-czarnych. Powstaje więc obawa, czy w ogóle warto próbować napisać strukturę o większej wydajności?

      Okazuje się, że warto, ponieważ można uzyskać wydajniejszy kod.