Advanced   Java   Services vector und std::sort Back Next Up Home



std::sort

Eine vollständige Dokumentation des Funktionstemplates std::sort findet man auf den beiden Referenzseiten

http://www.cplusplus.com/reference/algorithm/sort/

http://en.cppreference.com/w/cpp/algorithm/sort

Mit den sort()-Funktionen kann man Arrays und Vektoren sehr einfach und effizient sortieren.


include und Namespace
#include <algorithm>
using namespace std;

Zwei Überladungen

Es gibt zwei Varianten


template <class RandomAccessIterator> void sort (RandomAccessIterator first, RandomAccessIterator last)

Diese Form ist anwendbar bei Containern die über einen RandomAccessIterator verfügen und deren Elemente eine Vergleichsfunktion "operator<()" haben. Das sind bei den primitiven Datentypen alle Zahlentypen wie int, double usw. Für Klassen muß die Operatorfunktion operator<() überladen sein, wobei diese Vergleichsfunktion sowohl eine nichtstatische Memberfunktion als auch eine friend-Funktion der Klasse sein kann. Die Klasse string etwa erfüllt diese Bedingung.

bool operator<(T t1, T t2)    // friend-Funktion
bool operator<(T other)    // Member-Funktion

template <class RandomAccessIterator> void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp)

Diese Form ist anwendbar bei Containern die über einen RandomAccessIterator verfügen und deren Elemente keine Vergleichsfunktion der obigen Art haben. In diesem Fall wird ein Funktionspointer übergeben, der die folgende Signatur haben muß.

bool compare(T t1, T t2)    // Vergleichsfunktion

Wie immer in solchen Fällen kann auch ein Objekt einer Klasse übergeben werden, die den Functioncall-Operator implementiert. std::sort ruft dann den function-call-operator zu dieser Instanz. Im folgenden eine Klasse die diesen Operator implementiert.

template<typename T>
struct Compare
{
   bool operator() (const T& t1, const T& t2)
   {
      return // z. Bsp.: t2 < t1 ;
   }
};

Beispiele

Sortieren von klassischen C-Strings in einem Vector

Für C-Strings braucht man eine externe Vergleichsfunktion oder -klasse.

Codeschnipsel

vector<const char*> cstringVector = { "eins", "zweins", "dreins", "vierns", "fünfs" }; // C++11
printContainer(cstringVector);
std::sort(cstringVector.begin(), cstringVector.end(), compareCStringAscending);
printContainer(cstringVector);

Wobei printContainer() ein Funktionstemplate ist

template<class T>
void printContainer(T container)
{
   for (auto elem : container)
      cout << elem << "  ";

   cout << endl;
};

und compareCStringAscending() die Vergleichsfunktion.

bool compareCStringAscending(const char* s1, const char* s2)
{
   return strcmp(s1,s2) < 0 ;
}

An Stelle der Vergleichsfunktion ist auch der function-call-operator in einer Klasse verwendbar

struct CompareCStringAscending
{
   bool operator() (const char* s1, const char* s2)
   {
      return strcmp(s1,s2) < 0 ;
   }
}

Sortieren von stl-strings in einem Vector

Für stl-strings existiert eine operator<() Funktion

vector<string> stringVector = { "eins", "zweins", "dreins", "vierns", "fünfs" }; // C++11
// verwendet operator< von string
std::sort(stringVector.begin(), stringVector.end());

Abwärts Sortieren mit std::greater()

Eine Abwärtssortierung erreicht man mit dem externen function-template std::greater() aus functional

vector<string>  stringVector = { "eins", "zweins", "dreins", "vierns", "fünfs" };
std::sort(std::begin(stringVector), std::end(stringVector), std::greater<string>());  // C++11

Reihenfolge umdrehen

Im Gegensatz zu list und forward_list besitzt vector keine reverse()-Methode. Mit Hilfe von std::sort kann man das jedoch leicht erreichen. Das folgende Functiontemplate löst die Aufgabe.

template<typename T>
bool reverseOrder(const T& t1, const T& t2) //
{
   //cout << "reverseOrder" << '\n';
   return  true ;  // dreht eine vorhandene reihenfolge um
   //return  false ;  //  verändert nichts
};

Natürlich läßt sich das auch wieder als Klasse schreiben

template<typename T>
struct ReverseOrder
{
   bool operator() (const T& t1, const T& t2)
   {
      return true ;
   }
};

Verwendung

vector<int> intVector{ 7, 9, 3, 11, 13, 1, 5 };  // C++11
printContainer(intVector);
std::sort(std::begin(intVector), std::end(intVector), reverseOrder<int>);  // C++11
printContainer(intVector);

Valid XHTML 1.0 Strict top Back Next Up Home