Notatnik techniczny

Interval Map

Kontener do przechowywania zakresów, pozwala szybko określić do jakiego zakresu należy dana wartość.

Sposób użycia

#include <iostream>

#include "IntervalMap.h"

int main() {
    RR_Containers::IntervalMap<uint64_t, char> obj('X');
    obj.reserve_range(10, 20, 'A');
    obj.reserve_range(15, 30, 'B');

    std::cout << obj[5] << std::endl;    // X
    std::cout << obj[11] << std::endl;   // A
    std::cout << obj[18] << std::endl;   // B
    std::cout << obj[100] << std::endl;  // X
}

Wydajność

Bazowym obiektem jest std::map, Operator[] wywołuje metodę std::map::upper_bound() wiec mamy złożoność O(log(n))O(log(n)) , podobnie jak metoda reserve_range(), która wywołuje maksymalnie dwa razy metody std::map::upper_bound() oraz std::map::insert(), a następnie w dwóch pętlach przesuwa iteratory jednak pętle wykonają maksymalnie po dwa cykle. Ostatnią metodą jest std::map::erase(). Widzimy ze wszystkie te metody mają złożoność O(log(n))O(log(n)) oraz są wykonane maksymalnie 2 razy więc ostateczna złożoność będzie O(log(n))O(log(n)) . Złożoność metod klasy std::map jest opisana tu.

Wymagania odnośnie typu K i V

Typ klucza

  • Implementuje operator mniejszości (operator<)
  • Pozwala się kopiować i pozwala na przypisywanie (operator=)
  • Pozwala na określenie wartości minimalnej przez szablon **std::numeric_limits::min()**

Typ wartości

  • Implementuje operator przypisania (operator=)
  • Pozwala na kopiowania, typ prosty albo klasa z konstruktorem kopiującym.
  • Implementuje operator porównania (operator==)

Implementacja

Kod znajduje się na GitHub.