Sortowanie wskaźników

Question

Mam klasę o takiej budowie:

#ifndef VECTOR_H_
#define VECTOR_H_
#include <iostream>
#include <iterator>

template <class Type>
class Vector {
	Type *tab;
	size_t rozmiar;
public:
	void sortuj(); //wywoluje funkcje sortuj_algorytm
	void sortuj_algorytm(Type *tab, int lewy, int prawy); //funkcja rekurencyjna
};

template<class Type>
void Vector<Type>::sortuj() {
	sortuj_algorytm(tab, 0, (rozmiar - 1));
}

template<class Type>
void Vector<Type>::sortuj_algorytm(Type *tab, int lewy, int prawy) {
	if (prawy <= lewy) return;
	int i = lewy - 1, j = prawy + 1,
		pivot = tab[(lewy + prawy) / 2];
	while (1)
	{
		while (pivot>tab[++i]);
		while (pivot<tab[--j]);
		if (i <= j) {
			int temp = tab[i];
			tab[i] = tab[j];
			tab[j] = temp;
		}
		else
			break;
	}
	if (j > lewy)
		sortuj_algorytm(tab, lewy, j);
	if (i < prawy)
		sortuj_algorytm(tab, i, prawy);
}

Chciałbym posortować int *tab wykorzystując coś, co się nazywa RandomAccessIterator, z czym nie miałem do tej pory do czyniena, więc poprosiłbym o pomoc w implementacji tego.

Comments

Podaj rodzaj sortowania (algorytm). Z tego co masz w funkcji sortowanie() trudno wywnioskować jak chciałbyś sortować.

---

Już poprawiłem swoje pytanie, algorytm QuickSort używam tutaj, jednak chciałbym to zaimplementować używając RandomAccessIterator.

Answer 1

Gdyby to była zmienna typu tab[] to nie miałbym problemu, ale tu zmienną jest *tab. 

To nie ma absolutnie żadnego znaczenia w tym przypadku.

Przede wszystkim: std::iterator_traits<T> ma jakikolwiek sens gdy T jest iteratorem lub wskaźnikiem.

Kolejna sprawa: nie mam pojęcia czy algorytm w stylu...

    while (n > 0) {
        typename std::iterator_traits<Type>::value_type tmp = first[];
        first[]++ = --last[];
        last[] = tmp;
        n -= 2;
    }

...w ogóle ma szanse coś posortować, więc najpierw mógłbyś wytłumaczyć jak to ma działać (nie wiem jak to zabrzmiało, ale żeby było jasne - niczego nie neguje, tylko zwyczajnie pytam).

Nie wiem też co miałeś na myśli przez zapisy w stylu first[], ale możesz być pewny, że jest niepoprawny.

Comments

Eh... masz rację. Troszkę zbłądziłem chyba. Funkcja "sortująca" brana stąd: http://en.cppreference.com/w/cpp/iterator/iterator_traits . A dopiero teraz zauważyłem, że ta funkcja jedynie odwraca kolejność elementów... Wydawało mi się, że sortuje malejąco.

Więc inaczej. Chciałem wykorzystać w sortowaniu funkcje sort(tab.begin(), tab.end()); ale nie działa. Z pamięci piszę, że były błędy, że zmienna *tab musi być strukturą, coś w tym stylu.

Postanowiłem więc, że wykorzystam RandomAccessIterator i napiszę coś swojego, ale nie pykło. Mam jedną funkcję sortującą:

#ifndef VECTOR_H_
#define VECTOR_H_
#include <iostream>
#include <iterator>

template <class Type>
class Vector {
	Type *tab;
	size_t rozmiar;
public:
	void sortuj(); //wywoluje funkcje sortuj_algorytm
	void sortuj_algorytm(Type tab, int lewy, int prawy); //funkcja rekurencyjna
};

template<class Type>
void Vector<Type>::sortuj() {
	sortuj_algorytm(*tab, 0, (rozmiar - 1));
}

template<class Type>
void Vector<Type>::sortuj_algorytm(Type tab, int lewy, int prawy) {
	if (prawy <= lewy) return;
	int i = lewy - 1, j = prawy + 1,
		pivot = tab[(lewy + prawy) / 2];
	while (1)
	{
		while (pivot>*tab[++i]);
		while (pivot<*tab[--j]);
		if (i <= j) {
			int temp = *tab[i];
			*tab[i] = *tab[j];
			*tab[j] = temp;
		}
		else
			break;
	}
	if (j > lewy)
		sortuj_algorytm(tab, lewy, j);
	if (i < prawy)
		sortuj_algorytm(tab, i, prawy);
}

Wywołuje tą funkcję w pliku main.cpp:

tablica.sortuj();

Ale dostaje błąd: Indeks dolny wymaga tablicy lub wskaźnika typu.  - błąd odnosi się do wszystkich tab/*tab w funkcji sortuj_algorytm.

To była moja pierwsza myśl z tym algorytmem. Jest to QuickSort.

Jednak wolałbym coś w stylu tak jak napisałem, sort(tab.begin(), tab.end()) ale nie idzie mi tego skleić.

---

Z pamięci piszę, że były błędy, że zmienna *tab musi być strukturą, coś w tym stylu.

Żeby w ogóle użyć operatora kropki, zmienna musi być obiektem. Widocznie w twoim wypadku byl to jakiś typ podstawowy.

Wskaźniki nie mają metod begin() i end(), cokolwiek by to miało znaczyć :D, bo nawet nie są obiektami.

Jeśli chcesz użyć std::sort, to po prostu

std::sort(tab, tab + rozmiar); 

---

Udało mi się przed chwilą poprawić ten algorytm swój i się kompiluje (pytanie przy okazji poprawiłem). Wypróbuje ten pomysł od Ciebie teraz.

---

Hm.. działa. Czyli begin(), end() było niepotrzebne. Dzięki Criss.

---

Na pewno rozumiesz co tu się dzieje?

.begin() i .end() zwracają iteratory. std::sort operuje na typach spełniających wymagania RandomAccessIterator (zobacz paragraf Type requirements w zalinkowanej dokumentacji std::sort). Tak się składa, że wskaźniki spełniają te wymagania, więc możesz wywołać sort w powyższy sposób.
edit: Ah, właśnie zauważyłem, że mokrowski już to wyjaśnił w ten sam sposób :D whatever

Btw. std::vector<T>::iterator, to też po prostu T* i... działa - także masz nawet przykład prosto z biblioteki standardowej :P

---

Muszę sobie przypomnieć o tym Criss, bo czytałem jakiś czas temu sporo o rodzajach iteratorów (wejściowe, wyjściowe, postępujące, dwukierunkowe, dostępu swobodnego itd.) ale sporo już zapomniałem. Dzięki jeszcze raz za wytłumaczenie,

Answer 2

#include <iostream>
#include <iterator>
#include <algorithm>

template <class Type>
class Vector {
    Type* tab;
    size_t rozmiar;
  public:
    void sortuj();
};

template<class Type>
void Vector<Type>::sortuj() {
    std::sort(tab, tab + rozmiar, [](Type t1, Type t2) {
        return t1 < t2;
    });
}

Ale i tak myślę że nie ma powodu stosować tu gołej tablicy (chyba że Ci kazali).

RandomAccessIterator ma semantykę wywołań taką samą jak wskaźnik. Dlatego algorytm sort będzie działał.

PS. Poprawiony błąd wywołania.

Comments

Czy to znowu jakaś nowość, którą mój kompilator nie rozumie? Wersja od Crissa mi działa, tutaj dostaje błędy:

„bool Vector<int>::sortowanie::<lambda_c461e16ab8333d4dd14a265e202731c2>::operator ()(Type *,Type *) const”: nie można dokonać konwersji argumentu 1 z „int” do „int *”.

 

---

Argumenty lambdy powinny być typu Type zamiast Type*.

Swoją drogą, to w ogóle niepotrzebna ta lambda, bo std::sort i tak domyślnie (w wersji dwu-argumentowej) porównuje elementy za pomocą właśnie operatora <.