Sortowanie elementów kontenera vector
Stronę tą wyświetlono już: 4022 razy
Można by się bawić w tworzenie własnego algorytmu sortującego elementy kontenera vector, jednakże nie ma takiej potrzeby albowiem istnieją już gotowe rozwiązania tego problemu zaimplementowane w pliku nagłówkowym algorithm. Zanim jednak przejdę do rzeczy konieczne jest zaimplementowanie jakiejś przykładowej klasy z obsługą operatora <. Ponieważ już wcześniej tworzyłem taką klasę, więc wystarczy nią się tutaj posłużyć:
- #include <iostream>
- #include <vector>
- #include <math.h>
- #include <windows.h>
- #include <algorithm>
- #include <stdlib.h>
- #include <time.h>
- using namespace std;
- class point2d{
- private:
- double x;
- double y;
- public:
- point2d():x(0), y(0){}
- point2d(double x,double y):x(x), y(y){}
- point2d(const point2d &p):x(p.x), y(p.y){}
- inline double GetLength() const {return sqrt(x * x + y * y);}
- inline double GetX() const {return x;}
- inline double GetY() const {return y;}
- // operator podstawiania
- point2d & operator =(const point2d &p){
- x = p.x;
- y = p.y;
- return *this;}; // proste podstawienie
- void operator =(double length){ // ustaiwa długość wektora
- if(x!=0 && y !=0){ // gdy jego wartość nie jest równa zero
- double k = length / GetLength(); // oblicz współczynnik skalowania
- x *= k; // skalowanie x
- y *= k; // skalowanie y
- }
- };
- // operatory porównania wartości
- inline bool operator == (const point2d &p) const {return x * x + y * y == p.x * p.x + p.y * p.y;};
- inline bool operator == (const double &length) const {return x * x + y * y == length * length;};
- inline bool operator != ( point2d &p) const {return x * x + y * y != p.x * p.x + p.y * p.y;};
- inline bool operator != (const double &length) const {return x * x + y * y != length * length;};
- inline bool operator <(const point2d &p) const {return x * x + y * y < p.x * p.x + p.y * p.y;};
- inline bool operator <(const double &length) const {return x * x + y * y < length * length;};
- inline bool operator >(const point2d &p) const {return x * x + y * y > p.x * p.x + p.y * p.y;};
- inline bool operator >(const double &length) const {return x * x + y * y > length * length;};
- inline bool operator >=(const point2d &p) const {return x * x + y * y >= p.x * p.x + p.y * p.y;};
- inline bool operator >=(const double &length) const {return x * x + y * y >= length * length;};
- inline bool operator <=(const point2d &p) const {return x * x + y * y <= p.x * p.x + p.y * p.y;};
- inline bool operator <=(const double &length) const {return x * x + y * y <= length * length;};
- // Operatory matematyczne
- inline point2d & operator +=(const point2d &p){x += p.x; y += p.y; return *this;};
- /*point2d operator +(point2d p){ point2d p1(x + p.x, y + p.y); return p1;};*/
- };
- ostream & operator << (ostream &iostr, const point2d &p2d){
- return iostr << "x = "<<p2d.GetX()<<"; y = "<<p2d.GetY()<<";";
- }
- point2d operator +(const point2d &p1, const point2d &p2){
- point2d p = p1;
- p += p2;
- return p;
- }
- bool operator == (const double &length, const point2d &p){
- return p == length; // wykorzystanie operatora zawartego w definicji klasy point2d
- }
- bool operator != (const double &length, const point2d &p){
- return p != length; // wykorzystanie operatora zawartego w definicji klasy point2d
- }
- bool operator < (const double &length, const point2d &p){
- return p < length; // wykorzystanie operatora zawartego w definicji klasy point2d
- }
- bool operator > (const double &length,const point2d &p){
- return p > length; // wykorzystanie operatora zawartego w definicji klasy point2d
- }
- bool operator <= (const double &length,const point2d &p){
- return p <= length; // wykorzystanie operatora zawartego w definicji klasy point2d
- }
- bool operator >= (const double &length,const point2d &p){
- return p >= length; // wykorzystanie operatora zawartego w definicji klasy point2d
- }
Powyższy kod obsługuje wiele operatorów, lecz dla algorytmu sortującego będzie potrzebny jedynie operator <, zanim jednak pokażę, jak go wykorzystuje pierwszy wariant funkcji sort, utworzę jeszcze funkcję porównującą dwa elementy według innych kryteriów:
- bool check_point2d(point2d p1, point2d p2){ // funkcja spradzająca czy x z p1 jest mniejszy od x z p2
- return p1.GetX() < p2.GetX();
- }
Teraz już można przykładowy kod sortowania stworzyć:
- int main(){
- setlocale(LC_CTYPE,"Polish"); // żeby polskie znaki były (windows.h)
- vector<point2d> tPoint2d;
- srand(time(NULL)); // ustawienie losowanka
- for(int i = 0; i < 10; i++){
- tPoint2d.push_back(point2d(rand() % 1000, rand() % 1000)); // losowanie
- }
- cout<<"Przed posortowaniem według długości: "<<endl<<endl;
- for(std::vector<point2d>::iterator i = tPoint2d.begin(); i < tPoint2d.end(); i++){
- cout<<"Długość wektora: "<<(*i).GetLength()<<" "<<*i<<endl; // wyświetlanie
- }
- sort(tPoint2d.begin(),tPoint2d.end()); // sortowanie z wykorzystaniem operatora <
- cout<<endl<<"Po posortowaniu według długości: "<<endl<<endl;
- for(std::vector<point2d>::iterator i = tPoint2d.begin(); i < tPoint2d.end(); i++){
- cout<<"Długość wektora: "<<(*i).GetLength()<<" "<<*i<<endl; // wyświetlanie
- }
- sort(tPoint2d.begin(),tPoint2d.end(),check_point2d); // sortowanie z przebiegłym wykorzystaniem funkcji check_point2d
- cout<<endl<<"Po posortowaniu według współrzędnej x: "<<endl<<endl;
- for(std::vector<point2d>::iterator i = tPoint2d.begin(); i < tPoint2d.end(); i++){
- cout<<*i<<endl; // wyświetlanie
- }
- cout<<"Wcisnij enter, aby zamknac program...";
- cin.get();
- return 0;
- }
Wynik działania:
Przed posortowaniem według długości: Długość wektora: 1208.53 x = 823; y = 885; Długość wektora: 922.736 x = 185; y = 904; Długość wektora: 646.743 x = 624; y = 170; Długość wektora: 334.964 x = 99; y = 320; Długość wektora: 799.436 x = 547; y = 583; Długość wektora: 574.474 x = 554; y = 152; Długość wektora: 553.521 x = 417; y = 364; Długość wektora: 754.036 x = 87; y = 749; Długość wektora: 844.009 x = 836; y = 116; Długość wektora: 467.898 x = 448; y = 135; Po posortowaniu według długości: Długość wektora: 334.964 x = 99; y = 320; Długość wektora: 467.898 x = 448; y = 135; Długość wektora: 553.521 x = 417; y = 364; Długość wektora: 574.474 x = 554; y = 152; Długość wektora: 646.743 x = 624; y = 170; Długość wektora: 754.036 x = 87; y = 749; Długość wektora: 799.436 x = 547; y = 583; Długość wektora: 844.009 x = 836; y = 116; Długość wektora: 922.736 x = 185; y = 904; Długość wektora: 1208.53 x = 823; y = 885; Po posortowaniu według współrzędnej x: x = 87; y = 749; x = 99; y = 320; x = 185; y = 904; x = 417; y = 364; x = 448; y = 135; x = 547; y = 583; x = 554; y = 152; x = 624; y = 170; x = 823; y = 885; x = 836; y = 116; Wcisnij enter, aby zamknac program...
W pliku nagłówkowym algorithm znajduje się również funkcja is_sorted w dwóch wersjach tak jak funkcja sort a zadanie tej funkcji wydaje się być oczywiste, czyli sprawdzanie czy zawartość kontenera została posortowana według określonych kryteriów.

Tytuł:
Architektura oprogramowania bez tajemnic. Wykorzystaj język C++ do tworzenia wydajnych aplikacji i systemów
Autor:
Adrian Ostrowski, Piotr Gaczkowski

Tytuł:
Opus magnum C++ 11. Programowanie w języku C++. Wydanie II poprawione (komplet)
Autor:
Jerzy Grębosz

Tytuł:
Programowanie wieloplatformowe z C++ i wxWidgets 3
Autor:
Bartosz W. Warzocha

Tytuł:
Język C++ i przetwarzanie współbieżne w akcji. Wydanie II
Autor:
Anthony Williams

Tytuł:
C++ dla bystrzaków. Wydanie VII
Autor:
Stephen R. Davis

Tytuł:
Tablice informatyczne. Podstawy C++
Autor:
Radosław Sokół

Tytuł:
Opus magnum C++11. Programowanie w języku C++ (komplet)
Autor:
Jerzy Grębosz

Tytuł:
OpenCV 3. Komputerowe rozpoznawanie obrazu w C++ przy użyciu biblioteki OpenCV
Autor:
Adrian Kaehler, Gary Bradski

Tytuł:
C++ w 24 godziny. Wydanie VI
Autor:
Rogers Cadenhead, Jesse Liberty

Tytuł:
C++ Optymalizacja kodu. Sprawdzone techniki zwiększania wydajności
Autor:
Guntheroth Kurt