Obrni dinamički niz

Napisati funkciju

template <typename T>
void obrni(DinamickiNiz<T>& niz);

koja obrće redosled elemenata niza u mestu (bez pomoćnog niza), u vremenu $O(n)$. Koristi se klasa DinamickiNiz<T> iz zaglavlja dinamicki_niz.h.

Pitanje za razmišljanje: Da li vaše rešenje radi za prazan niz? Šta je vrednost izraza std::size_t(0) - 1?

Ulaz

U prvom redu učitava se broj n $(0 \le n \le 10^5)$, a zatim n celih brojeva. Nakon toga učitava se broj m $(0 \le m \le 10^5)$, a zatim m reči.

Izlaz

U prvom redu ispisati obrnut niz brojeva, a u drugom obrnut niz reči.

Primer

Ulaz

5
1 2 3 4 5
3
ana voli milovana

Izlaz

5 4 3 2 1
milovana voli ana

Postavka

main.cpp

#include <iostream>
#include <string>

#include "dinamicki_niz.h"

namespace matf {

    // Obrce redosled elemenata niza u mestu, u vremenu O(n).
    template <typename T>
    void obrni(DinamickiNiz<T>& niz)
    {
        // Ovde ide vasa implementacija
    }

} // namespace matf

template <typename T>
void ucitaj(DinamickiNiz<T>& niz)
{
    std::size_t n;
    std::cin >> n;
    for (std::size_t i = 0; i < n; ++i) {
        T x;
        std::cin >> x;
        niz.dodaj(x);
    }
}

template <typename T>
void ispisi(const DinamickiNiz<T>& niz)
{
    for (std::size_t i = 0; i < niz.velicina(); ++i)
        std::cout << niz[i] << " ";
    std::cout << std::endl;
}

int main()
{
    DinamickiNiz<int> brojevi;
    ucitaj(brojevi);
    matf::obrni(brojevi);
    ispisi(brojevi);

    DinamickiNiz<std::string> reci;
    ucitaj(reci);
    matf::obrni(reci);
    ispisi(reci);

    return 0;
}

Rešenje

main.cpp

#include <iostream>
#include <string>

#include "dinamicki_niz.h"

namespace matf {

    // Obrce redosled elemenata niza u mestu, u vremenu O(n).
    template <typename T>
    void obrni(DinamickiNiz<T>& niz)
    {
        // Poluotvoren opseg [i, j): jer bi prazan niz bi dao
        // std::size_t(0) - 1, odnosno najveci neoznaceni broj.
        std::size_t i = 0;
        std::size_t j = niz.velicina();
        while (i + 1 < j) {
            --j;
            T pom = niz[i];
            niz[i] = niz[j];
            niz[j] = pom;
            ++i;
        }
    }

} // namespace matf

template <typename T>
void ucitaj(DinamickiNiz<T>& niz)
{
    std::size_t n;
    std::cin >> n;
    for (std::size_t i = 0; i < n; ++i) {
        T x;
        std::cin >> x;
        niz.dodaj(x);
    }
}

template <typename T>
void ispisi(const DinamickiNiz<T>& niz)
{
    for (std::size_t i = 0; i < niz.velicina(); ++i)
        std::cout << niz[i] << " ";
    std::cout << std::endl;
}

int main()
{
    DinamickiNiz<int> brojevi;
    ucitaj(brojevi);
    matf::obrni(brojevi);
    ispisi(brojevi);

    DinamickiNiz<std::string> reci;
    ucitaj(reci);
    matf::obrni(reci);
    ispisi(reci);

    return 0;
}