Operacje arytmetyczne na vector::iterator? Algorytm sortujący

Question

Cześć. Jako projekt dodatkowy do szkoły wpadłem na pomysł napisania algorytmu sortującego. No i dodatkowo chciałem przy tym się czegoś nauczyć, a jako że mam jako jedno z wymagań znajomość STL, to skleciłem takie coś. Tyle że, niewiem jak i czy wogóle da się operować arytmetycznie na iteratorach. Skoro to nie typ, a wskaźnik, to co można z tym faktem zrobić? Chodzi mi tylko o żeby zmienić indeks tablicy na który wskazuje iterator. Na upartego mógłbym zrobić zwykłe pętle, a po prostu za każdym razem inkrementować wskaźnik, ale takie rozwiązanie wydaje mi się "brudne".

Pokrótce omówię jak działa ten algorytm. Na wejściu jest nieposortowana lista np. intów. Szukamy w całym zbiorze największej i najmniejszej wartości. Największą zamieniamy indeksem z ostatnią w zbiorze, a najmniejszą z pierwszym. Następnie zbiór do przeszukania zmniejszamy o tą ostatnią i pierwszą liczbę. Powtarzamy ten proces n/2 lub (jeżeli n nie jest parzysta) (n-1)/2 gdzie n jest liczbą indeksów.

Możecie również dawać rady jak można coś lepiej napisać.

Z góry dzięki.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <iterator>
using namespace std;

template <class T> 
vector<T> sort(vector<T> input) {
	 typename vector<T>::iterator largestIndex = input.begin(), smallestIndex = input.begin(), i, j, minus = input.begin();

	 if ((input.end() - 1) % 2 != 0)
		 ++minus;

	//Sort
	for (i = input.begin(); i != input.end() - minus; ++i) {
		largestIndex = i;
		smallestIndex = i;
		for (j = i; j != input.end() - i; ++j) {
			if (*j > * largestIndex)
				largestIndex = j;
			if (*j < *smallestIndex)
				smallestIndex = j;
		}
		swap(*i, *smallestIndex);
		swap(*(input.end() - i - 1), *largestIndex);
	}
	return input;
}


int main()
{
	vector<int> array = { 3, 8, 2, 9, 6, 5, 4, 12};

	array = sort<int>(array);

	for (vector<int>::iterator m = array.begin(); m != array.end(); ++m) cout << " " << *m;

	return 0;
}

 

Comments

Możecie również dawać rady jak można coś lepiej napisać.

1. Nie przekazuj vectora przez wartość tylko przez referencję. Funkcja nie musi wtedy nic zwracać.
2. W zastosowanym algorytmie kolejność wywołań swap ma znaczenie. W zależności od danych znajdujących się w kontenerze może to powodować błędne wyniki.
3. Używaj słowa auto aby skrócić sobie zapis np.

   auto largestIndex = input.begin();

    

 

Answer 1

Iterator nie jest wskaźnikiem!
Iterator to specjalna klasa z zaimplementowanym operatorem * zwracającym referencję na wskazywany obiekt. Sam też możesz zdefiniować operator * wewnątrz swoich klas.

Przygotowałem przykład w jaki sposób można zamieniać wartości pod dwoma iteratorami.

#include <iostream>
#include <vector>

template <class T>
void mixer(std::vector<T> &v) {
    auto iterator = v.begin();
    auto iteratorNext = iterator+1;
    while (iteratorNext != v.end()) {
        std::swap(*iterator, *iteratorNext);
        iterator = iteratorNext+1;
        if (iterator == v.end())
            break;
        iteratorNext = iterator+1;
    }
}

template <class T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) {
    out << "vector{";
    if (!v.empty()) {
        auto iterator = v.begin();
        out << *iterator;
        while (++iterator != v.end()) {
            out << ", " << *iterator;
        }
    }
    out << "]" << std::endl;
    return out;
}

int main()
{
    std::vector<int> vector{1,2,3,4,5,6,7,8,9,10,11};
    std::cout << vector;
    mixer(vector);
    std::cout << vector;
    return 0;
}

 

Comments

Okej, chyba rozumiem. Cała funkcja ostream jest tylko do wypisania vectora. Więc nie mogę operować tak iteratorSec = v.end()-1, tylko muszę najpierw zrobić iteratorFir = v.end() a dopiero potem iteratorSec = iteratorFir - 1? Czy znowu źle rozumuję.

---

Nie przejmuj się przeciążeniem operatora <<. To tylko funkcja pomocnicza.

Nie wiem co masz zrobić, nie rozumiem logiki w twoim przykładzie. Nie wiem co chcesz osiągnąć.
Czym są iteratory iteratorFir i iteratorSec? Nie było ich wcześniej.

Opisz jak ma działać funkcja
A zwłaszcza co znaczy ten fragment

     if ((input.end() - 1) % 2 != 0)
         ++minus;

Ponadto do czego ci są potrzebne iteratory largestIndex i smallestIndex

---

To wyżej to były tylko "przykłady". Mój bład, w kodzie nie zaktualizowałem nazw zmiennych. Chodzi o to, że: mamy listę np {6, 2, 4, 9, 85, 10, 23}. Ogólny zamysł algorytmu jest taki, że:

1. Skanujemy zbiór szukając największej i najmniejszej liczby. Liczbę największą wrzucamy na koniec, a najmniejszą na początek, zamieniając wartości. Największa to 85, najmniejsza 2. Po tym kroku wygląda to tak: {2, 6, 4, 9, 23, 10, 85}

2. Zmniejszamy zbiór o te skrajne indeksy, które są już posortowane. Wracamy do kroku 1, tylko że skanujemy już tylko ten zbiór o i - ty dalszy od skrajów.

Czyli po kolei dalej będzie już sortował tylko {6, 4, 9, 23, 10}, Za kolejnym powtórzeniem {6, 9, 10}. I tak aż do posortowania. Jeszcze muszę coś tam dodać aby nie sortowało już zbioru posortowanego. largestIndex i smallestIndex przechowywały "wartości" największą i najmniejszą. Nazwy są stąd, bo na samym początku miałem zamiar przechowywać w nich po prostu indeksy i tak jakoś zostało.

A ta funkcja sprawdza po prostu czy ilość indeksów jest nieparzysta. Jeżeli jest, to wtedy główna pętla wykona się dokładnie (n-1)/2 razy. Mój kolejny błąd: w pętli tuż po Sort powinno być i != (input.end() - minus)/2.

---

Strasznie zamotałeś w tym kodzie :D

Proponuję ci następujące rozwiązanie:
1. Utwórz dwa iteratory wyznaczające przedział od pierwszego elementu do ostatniego.
2. Stwórz pętlę wykonującą się dopóki przedział jest przynajmniej dwuelementowy:
   a. Stwórz pętlę. Iteruj po zdefiniowanym przedziale.
      - Jeżeli liczba jest mniejsza od pierwszego elementu przedziału to je zamień
      - Jeżeli liczba jest większa od ostatniego elementu przedziału to je zamień
  b. Zmniejsz przedział o 1 z każdej strony

Spróbuj sam to napisać a potem porównaj z moim rozwiązaniem
https://www.onlinegdb.com/B1uTdnf5P

PS. Pamiętaj, że funkcja pracuje na kopii przekazanego wektora, może lepiej by było przekazać do funkcji referencję i pracować bezpośrednio na wektorze (wtedy funkcja nie musiałaby zwracać żadnej wartości).

---

Dzięki wielkie za pomoc :D Napisałem coś podobnego.