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ść , 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ść oraz są wykonane maksymalnie 2 razy więc ostateczna złożoność będzie . Złożoność metod klasy std::map jest opisana tu (opens new window).

Wymagania odnośnie typu K i V

Typ klucza <K>

• 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<K>::min()

Typ wartości <V>

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

Implementacja

Kod znajduje się na GitHub (opens new window).