8. hét: Jobbérték referenciák

return std::move(*this);

Jobbérték + balérték mátrixösszeadás, tagfüggvényként megvalósítva.

class Matrix {
    double *data;
    size_t w, h;
  public:
    /* ... */
    Matrix operator+(Matrix const & rhs) && {
        for (size_t i = 0; i < w*h; ++i)
            data[i] += rhs.data[i];

        return std::move(*this);    // de miért?
    }
};

Miért úgy kell írni a jelölt sort, ahogy írva van?

Hova kell std::move()?

Adottak az alábbi algoritmusok. Tedd ki az std::move() hívásokat mindenhova, ahova lehet!

/* megcseréli két változó tartalmát. */
template <typename T>
void swap(T & a, T & b) {
    T temp = a;
    a = b;
    b = temp;
}

/* feltölti a [begin; end) tartományt a megadott értékkel. */
template <typename IT, typename VAL>
void fill(IT begin, IT end, VAL val) {
    for (IT it = begin; it != end; ++it)
        *it = val;
}

/* egy lépéssel balra tolja a tömböt (pl. 1234 -> 2341) */
template <typename T>
void rotate(T * tomb, size_t s) {
    T temp = tomb[0];
    for (size_t i = 1; i < s; ++i)
        tomb[i-1] = tomb[i];
    tomb[s-1] = temp;
}

/* a tömb elejére gyűjti a p tulajdonsággal rendelkező elemeket.
 * visszaad egy iterátort, ami azt mutatja, meddig lett tele a tömb.
 * specifikálatlan, hogy mi marad a tömb végén. */
template <typename IT, typename PRED>
IT remove_if(IT begin, IT end, PRED p) {
    IT filled = begin;
    while (filled != end && p(*filled))
        ++filled;
    IT it = filled;
    while (++it != end)
        if (p(*it))
            *filled++ = *it;
    return filled;
}

Összefésülő rendezés

Az összefésülő rendezés (merge sort, lásd Prog1/Algel) lényege a következő:

• Rekurzívan rendezzük a tömb első és második felét.
• Ezek után pedig a két különálló, rendezett tartományt összefésüljük egyetlen rendezett tartománnyá.

Alább egy megvalósítás int-ek tömbjére.

void merge(int *in, int begin, int mid, int end, int *out) {
    int i = begin, j = mid;
    for (int c = begin; c < end; ++c) {
        if (i < mid && (j >= end || in[i] <= in[j])) {
            out[c] = in[i];
            i++;
        } else {
            out[c] = in[j];
            j++;
        }
    }
}
 
void copy(int *in, int begin, int end, int *out) {
    for (int c = begin; c < end; ++c) {
        out[c] = in[c];
    }
}

void merge_sort(int *tomb, int begin, int end, int *temp) {
    if (end - begin < 2)
        return;
    int mid = (begin + end) / 2;
    merge_sort(tomb, begin, mid, temp);
    merge_sort(tomb, mid, end, temp);
    merge(tomb, begin, mid, end, temp);
    copy(temp, begin, end, tomb);
}

Az összefésüléshez szükséges egy segédtömb: a két fél tartomány az összefésülés (merge) során a segédtömbbe kerül, ahonnan aztán vissza kell másolni (copy). A fenti rendező függvény ezért elvárja a hívójától, hogy kapjon egy munkaterületet, amelyik az eredeti tömb méretével megegyező méretű.

Végezd el az alábbi módosításokat a kódon!

• Template-esítsd: ne inteken dolgozzon, hanem tetszőleges típusú elemeken. Természetesen a <, >= stb. operátorokat attól a típustól elvárhatod.
• Csinálj egy csomagoló függvényt, amely lefoglalja magától a megfelelő méretű segédtömböt, hogy ezzel ne a hívónak kelljen bajlódnia!
• Figyeld meg, hogy az összefésülésnél a segédtömbbe MÁSOLÓDNAK az objektumok, aztán onnan az eredeti helyükre visszaMÁSOLÓDNAK megint. Ezeknek a lépéseknek nem másolásnak, hanem mozgatásoknak kellene lenniük. Alakítsd át úgy a kódot, hogy
  1. a segédtömb inicializálatlan memóriaterület legyen, amelyre
  2. az összefésülés átmozgatja az objektumokat, és ahonnan végül a lecserélt copy függvény
  3. az eredeti tömbbe, a végleges helyükre visszamozgatja azokat!

A rendezendő tömb elemeitől nem várhatod el, hogy alapértelmezett konstruktoruk legyen: T() lehet, hogy nem létezik. Ha segédfüggvényt írsz a rekurzió indításához, akkor már javítsd ki a paraméterezést is: a tömböt a szokásos módon kelljen átadni, méret megjelölésével.

Ügyelj arra, hol használsz konstruktort, destruktort és értékadást! A megoldásod az extrák menüpont alatt elérhető SuperNoisy osztállyal is tesztelheted.

#include <utility>
#include <iostream>
#include <new>
#include <string>

template <typename T>
void osszefuz(T *tomb, int eleje, int kozepe, int vege, T *seged) {
    /* összefűzés - átmozgatás az új tömbbe */
    int i = eleje, j = kozepe;
    for (int c = eleje; c < vege; ++c) {
        T *honnan;
        if (i < kozepe && (j >= vege || tomb[i] <= tomb[j])) {
            honnan = &tomb[i];
            i++;
        } else {
            honnan = &tomb[j];
            j++;
        }
        new (&seged[c]) T(std::move(*honnan));
        honnan->~T();
    }
    /* az összefűzött adatok visszamozgatása */
    for (int c = eleje; c < vege; ++c) {
        new (&tomb[c]) T(std::move(seged[c]));
        seged[c].~T();
    }
}

template <typename T>
void osszefuz_rendez_belso(T *tomb, int eleje, int vege, T *seged) {
    if (vege - eleje < 2)
        return;
    int kozepe = (eleje + vege) / 2;
    osszefuz_rendez_belso(tomb, eleje, kozepe, seged);
    osszefuz_rendez_belso(tomb, kozepe, vege, seged);
    osszefuz(tomb, eleje, kozepe, vege, seged);
}

template <typename T>
void osszefuz_rendez(T *tomb, int meret) {
    T *seged = (T*) ::operator new(sizeof(T) * meret);
    osszefuz_rendez_belso(tomb, 0, meret, seged);
    ::operator delete(seged);
}

int main() {
    std::string tomb[4] = { "alma", "korte", "barack", "szilva" };
    osszefuz_rendez(tomb, 4);
    for (auto s: tomb) {
        std::cout << s << std::endl;
    }
}