Mit dem C++ Typsystem ist es möglich Informationen und Algorithmen in das Programm zu codieren, die schon vor der Compilezeit fest stehen.
Wie würdet ihr folgendes Problem lösen:
Ein Algorithmus, zum Beispiel die binäre Suche, benötigt einen bereits sortieren Datensatz. Den Datensatz zu sortieren und danach die Suche anzuwenden ist trivial. Aber in einem anderen Teil des Programms muss danach noch einmal die binäre Suche angewendet werden. Nur kann dieser andere Programm Teil nicht annehmen, dass der übergebene Datensatz sortiert ist. Noch einmal die Sortierung angewandt kostet viel Laufzeit. Zu testen ob die Daten bereit sortiert sind, ist immer noch ein linearer Algorithmus.
Der Programmierer könnte auch eine bool Variable mit geben, die aussagt ob die Daten bereits sortiert sind. Das ist immerhin nur ein konstanter Mehraufwand. Der Datensatz muss stark mit dieser Statusvariable gekoppelt sein, damit keine Inkonsistenz entsteht. Also kommen beide zusammen in einem neuen Datentyp. Wenn man den sortierten Datensatz noch read-only macht, muss man kein Aufwand treiben festzustellen, ob der Datensatz durch ein Schreibzugriff nun nicht mehr sortiert ist. Damit ist auch die Statusvariable konstant.
Jetzt passiert etwas besonderes. Die Statusvariable wird von einer Funktion erzeugt und hat immer den selben Wert. Nämlich true, für "sortiert". Damit ist es möglich, diese Idee auch zur Compilezeit auszuführen und einen neuen Datentype Sorted einzuführen, der nur von einer sort() Funktion erzeugt werden kann und IMMER sortierte Daten enthält. Die bool Variable fällt komplett weg. Ihre Semantik ist im neuen Datentyp kodiert.
Wie sieht diese Idee in der Praxis aus? Es braucht eine sorted() Funktion welche die Daten sortiert und einen Sorted Typ zurück gibt. Damit, bei Bedarf, keine unnötigen Kopien erstellt werden, ist es auch möglich mit moveOwnership() die Daten in den Sorted Typ zu verschieben.
Jeder Algorithmus welcher sortiere Daten benötigt, soll nur Datensätze von Typ Sorted akzeptieren. Damit ist zur Compilezeit sichergestellt, dass nie aus Versehen unsortierte Daten übergeben werden und es wird nur einmal der Datensatz sortiert. Und alles kommt dank statischer Typisierung mit zero-overhead.
std::vector<int> vec {3,2,1};
// sort and move ownership to Sorted
Sorted sortedVec = sorted(acpl::moveOwnership(vec));
// can be used with the strong typed binary_search function
binary_search(sortedVec, valueToSearch);
Der Type Sorted implementiert nur ein read-only Interface und ist ein Wrapper um einen beliebigen Container. Der Konstruktor ist privat, damit nur die spezielle sorted Funktion diesen Typen erstellen kann.
auto nope = Sorted<std::vector<int>>{vec}; // error: ‘Sorted<Container>::Sorted(Container&&) is private within this context
Für bestehende Algorithmen können leicht Wrapper geschrieben werden. Wie beispielsweise für die binäre Suche:
template<typename Container, typename T>
bool binary_search(const Sorted<Container>& data, const T& value) {
return std::binary_search(data.begin(), data.end(), value);
}
Die Implementierung der sorted() Funktion ist relativ einfach, wenn die Sache mit Universal Referenz geklärt ist
template<typename Container>
Sorted<std::remove_reference_t<Container>> sorted(Container&& data) {
// variable data is a univeral reference. pattern: "deducted type&&" so we use forward
std::remove_reference_t<Container> sorted(std::forward<Container>(data));
std::sort(sorted.begin(), sorted.end());
// variable sorted is not a universal reference so we use move
return {std::move(sorted)};
}
Natürlich gibt es auch einen overload für die Funktion isSorted() diese gibt trivialierweise immer true zurück.
template<typename Container>
bool isSorted(const Sorted<Container>&) {
return true;
}
Und die Implementierung des Typ Sorted selbst
template<typename Container>
// requires Sequence container
class Sorted {
Sorted(Container&& data)
: c(std::forward<Container>(data))
{ }
public:
using value_type = typename Container::value_type;
using const_iterator = typename Container::const_iterator;
using const_reference = typename Container::const_reference;
auto size() const {
return std::size(c);
}
const_iterator begin() const {
return c.begin();
}
const_iterator end() const {
return c.end();
}
const_reference at(const auto& i) const {
return c.at(i);
}
const_reference operator[](const auto& i) const {
return c[i];
}
const_reference front() const {
return c.front();
}
template<typename C>
friend Sorted<std::remove_reference_t<C>> sorted(C&& data);
const Container c;
};