Esercizio - Array dinamico ordinato come classe template (quarto appello 2022-23, programmazione)

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <string>
#include <utility>
using namespace std;

// Array dinamico template i cui elementi sono SEMPRE ordinati (crescenti). Niente contenitori STL.
// Invarianti: data_[0..size_-1] e' ordinato; 0 <= size_ <= capacity_; data_ == nullptr se capacity_ == 0.
// Requisiti su T: costruttore di default, assegnamento di copia, operator<  (e operator== non serve).
template <typename T>
class SortedArray {
public:
    static constexpr size_t npos = static_cast<size_t>(-1);    // "non trovato"

    SortedArray() : size_{0}, capacity_{0}, data_{nullptr} {}
    ~SortedArray() { delete[] data_; }

    SortedArray(const SortedArray& o) : size_{o.size_}, capacity_{o.size_}, data_{o.size_ ? new T[o.size_] : nullptr}
    {
        copy(o.data_, o.data_ + size_, data_);
    }
    SortedArray& operator=(const SortedArray& o)
    {
        if (this != &o) {
            T* nuovo = o.size_ ? new T[o.size_] : nullptr;
            copy(o.data_, o.data_ + o.size_, nuovo);
            delete[] data_;
            data_ = nuovo;
            size_ = capacity_ = o.size_;
        }
        return *this;
    }
    SortedArray(SortedArray&& o) noexcept : size_{o.size_}, capacity_{o.capacity_}, data_{o.data_}
    {
        o.size_ = o.capacity_ = 0;
        o.data_ = nullptr;
    }
    SortedArray& operator=(SortedArray&& o) noexcept
    {
        if (this != &o) {
            delete[] data_;
            size_ = o.size_; capacity_ = o.capacity_; data_ = o.data_;
            o.size_ = o.capacity_ = 0;
            o.data_ = nullptr;
        }
        return *this;
    }

    // inserisce mantenendo l'ordine: cerca la posizione con una ricerca binaria, sposta a destra, scrive
    void insert(const T& value)
    {
        if (size_ == capacity_) reserve(capacity_ == 0 ? 4 : 2 * capacity_);
        size_t pos = primo_maggiore(value);                    // posizione del primo elemento > value
        for (size_t i = size_; i > pos; --i) data_[i] = data_[i - 1];   // fa posto
        data_[pos] = value;
        ++size_;
    }

    // ricerca binaria: O(log n). Restituisce l'indice di un elemento uguale a value, oppure npos
    size_t find(const T& value) const
    {
        size_t lo = 0, hi = size_;                             // intervallo [lo, hi)
        while (lo < hi) {
            size_t mid = lo + (hi - lo) / 2;
            if (data_[mid] < value) lo = mid + 1;
            else if (value < data_[mid]) hi = mid;
            else return mid;
        }
        return npos;
    }

    size_t size() const { return size_; }
    const T& operator[](size_t i) const { return data_[i]; }   // SOLA lettura: scrivere romperebbe l'ordine

private:
    size_t primo_maggiore(const T& value) const                // indice del primo elemento > value (o size_)
    {
        size_t lo = 0, hi = size_;
        while (lo < hi) {
            size_t mid = lo + (hi - lo) / 2;
            if (value < data_[mid]) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
    void reserve(size_t nuova)
    {
        T* nuovo = new T[nuova];
        copy(data_, data_ + size_, nuovo);
        delete[] data_;
        data_ = nuovo;
        capacity_ = nuova;
    }

    size_t size_;
    size_t capacity_;
    T* data_;
};

template <typename T>
void stampa(const SortedArray<T>& a)
{
    for (size_t i = 0; i < a.size(); ++i) cout << a[i] << ' ';
    cout << '\n';
}

int main()
{
    SortedArray<int> a;
    for (int x : {42, 7, 19, 7, 88, 3, 56})                    // inseriti disordinati
        a.insert(x);
    cout << "ordinato: ";
    stampa(a);
    cout << "find(19) = " << a.find(19) << ", find(88) = " << a.find(88)
         << ", find(5) e' npos? " << (a.find(5) == SortedArray<int>::npos) << '\n';

    SortedArray<int> b = a;                                    // copia profonda
    b.insert(1);
    cout << "a ha " << a.size() << " elementi, b ne ha " << b.size() << ": ";
    stampa(b);

    SortedArray<int> c = std::move(a);                         // spostamento
    cout << "dopo lo spostamento: a ha " << a.size() << " elementi, c ne ha " << c.size() << '\n';

    SortedArray<string> s;                                     // anche con le stringhe (ordine alfabetico)
    for (string w : {"pera", "mela", "uva", "banana"}) s.insert(w);
    stampa(s);
    cout << "find(\"uva\") = " << s.find("uva") << '\n';
    return 0;
}

ordinato: 3 7 7 19 42 56 88 
find(19) = 3, find(88) = 6, find(5) e' npos? 1
a ha 7 elementi, b ne ha 8: 1 3 7 7 19 42 56 88 
dopo lo spostamento: a ha 0 elementi, c ne ha 7
banana mela pera uva 
find("uva") = 3