Warum gibt es eine Trennung von Algorithmen, Iteratoren und Container in C++ STL

Question

Ich kann nicht herausfinden, warum sie Algorithmen, Iteratoren und Container in C++ STL getrennt haben. Wenn die Vorlagen überall stark verwendet werden, können wir Klassen haben, die alles mit Template-Parametern an einem Ort haben.

Einige Texte, die ich bekam, erklären, dass Iteratoren Algorithmen helfen, mit Containern Daten zu interagieren, aber was ist, wenn Container einen Mechanismus offenlegen, um auf die Daten zuzugreifen, die er besitzt?

Answer 1

Mit M Container + N Algorithmen, würde man normalerweise benötigen M * N Teile des Codes, aber mit Iteratoren als „Kleber“ wirkt, kann dies zu M + N Teile des Codes reduziert werden.

Beispiel: run 2 Algorithmen auf 3 Containern

std::list<int> l = { 0, 2, 5, 6, 3, 1 }; // C++11 initializer lists 
std::vector<int> v = { 0, 2, 5, 6, 3, 1 }; // C++11 initializer lists 
std::array<int, 5> a = { 0, 2, 5, 6, 3, 1 }; 

auto l_contains1 = std::find(l.begin(), l.end(), 1) != l.end(); 
auto v_contains5 = std::find(v.begin(), v.end(), 5) != v.end(); 
auto a_contains3 = std::find(a.begin(), a.end(), 3) != a.end(); 

auto l_count1 = std::count(l.begin(), l.end(), 1); 
auto v_count5 = std::count(v.begin(), v.end(), 5); 
auto a_count3 = std::count(a.begin(), a.end(), 3); 

Sie sind nur zwei verschiedene Algorithmen aufrufen und haben nur Code für 3 Container. Jeder Container übergibt die begin() und end() Iteratoren an den Container. Obwohl Sie 3 * 2 Codezeilen haben, um die Antworten zu generieren, gibt es nur 3 + 2 Teile der Funktionalität, die geschrieben werden müssen.

Für mehr Container und Algorithmen ist diese Trennung eine enorme Reduzierung der kombinatorischen Explosion im Code, die sonst folgen würde: Es gibt 5 Sequenzcontainer, 8 assoziative Container und 3 Containeradapter in der STL, und es gibt fast 80 Algorithmen in <algorithm> allein (nicht einmal diejenigen in <numeric>), so dass Sie nur 16 + 80 anstelle von 16 * 80, eine 13-fache Kürzung in Code haben! (Natürlich ist nicht jeder Algorithmus auf jedem Container sinnvoll, aber der Punkt sollte klar sein).

Die Iteratoren können in 5 Kategorien unterteilt werden (Eingabe, Ausgabe, Weiterleitung, bidirektionaler und wahlfreier Zugriff), und einige Algorithmen delegieren abhängig von den Iteratorfähigkeiten an spezialisierte Versionen. Dies wird die Code-Reduktion etwas verringern, aber die Effizienz stark verbessern, indem der am besten geeignete Algorithmus für den vorliegenden Iterator ausgewählt wird.

Beachten Sie, dass die STL nicht vollständig konsistent in der Trennung ist: std::list hat seine eigene sort Member-Funktion, die Implementierung spezifische Details verwendet, um sich zu sortieren, und std::string hat eine enorme Anzahl von Mitgliedsfunktion Algorithmen, von denen die meisten umgesetzt worden sein könnte als Nichtmitgliedsfunktionen.