Advanced   Java   Services

vector und 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 <algorithm>
using namespace std;

Es gibt zwei Varianten

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

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 ;
   }
};

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 ;
   }
}

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());

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

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);