Mit dem C++ Typsystem ist es m\u00f6glich Informationen und Algorithmen in das Programm zu codieren, die schon vor der Compilezeit fest stehen. <\/p>\n
Wie w\u00fcrdet ihr folgendes Problem l\u00f6sen:
\nEin Algorithmus, zum Beispiel die bin\u00e4re Suche, ben\u00f6tigt 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\u00e4re Suche angewendet werden. Nur kann dieser andere Programm Teil nicht annehmen, dass der \u00fcbergebene 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.
\nDer Programmierer k\u00f6nnte 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. <\/p>\n
Jetzt passiert etwas besonderes. Die Statusvariable wird von einer Funktion erzeugt und hat immer den selben Wert. N\u00e4mlich true<\/em>, f\u00fcr \"sortiert\". Damit ist es m\u00f6glich, diese Idee auch zur Compilezeit auszuf\u00fchren und einen neuen Datentype Sorted<\/em> einzuf\u00fchren, der nur von einer sort()<\/em> Funktion erzeugt werden kann und IMMER sortierte Daten enth\u00e4lt. Die bool Variable f\u00e4llt komplett weg. Ihre Semantik ist im neuen Datentyp kodiert. <\/p>\n Wie sieht diese Idee in der Praxis aus? Es braucht eine sorted()<\/em> Funktion welche die Daten sortiert und einen Sorted<\/em> Typ zur\u00fcck gibt. Damit, bei Bedarf, keine unn\u00f6tigen Kopien erstellt werden, ist es auch m\u00f6glich mit moveOwnership()<\/em><\/a> die Daten in den Sorted Typ zu verschieben.<\/p>\n Jeder Algorithmus welcher sortiere Daten ben\u00f6tigt, soll nur Datens\u00e4tze von Typ Sorted<\/em> akzeptieren. Damit ist zur Compilezeit sichergestellt, dass nie aus Versehen unsortierte Daten \u00fcbergeben werden und es wird nur einmal der Datensatz sortiert. Und alles kommt dank statischer Typisierung mit zero-overhead.<\/p>\n Der Type Sorted<\/em> implementiert nur ein read-only Interface und ist ein Wrapper um einen beliebigen Container. Der Konstruktor ist privat, damit nur die spezielle sorted<\/em> Funktion diesen Typen erstellen kann.<\/p>\n F\u00fcr bestehende Algorithmen k\u00f6nnen leicht Wrapper geschrieben werden. Wie beispielsweise f\u00fcr die bin\u00e4re Suche:<\/p>\n\r\nstd::vector<int> vec {3,2,1};\r\n\/\/ sort and move ownership to Sorted\r\nSorted sortedVec = sorted(acpl::moveOwnership(vec));\r\n\r\n\/\/ can be used with the strong typed binary_search function\r\nbinary_search(sortedVec, valueToSearch);\r\n<\/pre>\n\r\nauto nope = Sorted<std::vector<int>>{vec}; \/\/ error: \u2018Sorted<Container>::Sorted(Container&&) is private within this context\r\n<\/pre>\n\r\ntemplate<typename Container, typename T>\r\nbool binary_search(const Sorted<Container>& data, const T& value) {\r\n return std::binary_search(data.begin(), data.end(), value);\r\n}\r\n<\/pre>\n