¿Por qué hay una separación de algoritmos, iteradores y contenedores en C++ STL

Question

No puedo entender por qué tienen algoritmos, iteradores y contenedores separados en C++ STL. Si es un uso intensivo de plantillas en todas partes, entonces podemos tener clases que tengan todo en un solo lugar con los parámetros de la plantilla.

Algunos textos que obtuve explican que los iteradores ayudan a los algoritmos a interactuar con los datos de los contenedores, pero ¿qué pasa si los contenedores exponen algún mecanismo para acceder a los datos que posee?

Answer 1

Con M contenedores + N algoritmos, uno normalmente necesita M * N piezas de código, pero con iteradores que actúan como "pegamento", esto puede ser reducido a M + N piezas de código.

Ejemplo: Run 2 algoritmos en 3 contenedores

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

Está llamando a sólo 2 algoritmos diferentes, y sólo tienen código para 3 contenedores. Cada contenedor pasa los iteradores begin() y end() al contenedor. A pesar de que tiene 3 * 2 líneas de código para generar las respuestas, solo hay 3 + 2 piezas de funcionalidad que deben escribirse.

Para más contenedores y algoritmos, esta separación es una reducción enorme en la explosión combinatoria en el código que de otro modo seguiría: hay 5 contenedores de secuencia, 8 contenedores asociativos y 3 adaptadores de contenedor en el STL, y hay casi 80 algoritmos en <algorithm> solo (sin contar los en <numeric>) para que tenga solo 16 + 80 en lugar de 16 * 80, ¡una reducción de código de 13 veces! (Por supuesto, no todos los algoritmos tienen sentido en cada contenedor, pero el punto debe ser claro).

Los iteradores se pueden dividir en 5 categorías (entrada, salida, reenvío, bidireccional y acceso aleatorio), y algunos algoritmos delegarán en versiones especializadas dependiendo de las capacidades del iterador. Esto disminuirá algo la reducción del código, pero mejorará en gran medida la eficiencia al seleccionar el algoritmo mejor adaptado para el iterador en cuestión.

Tenga en cuenta que el TEL no es completamente consistente en la separación: std::list tiene su propia función sort miembro que utiliza los detalles de implementación específicas para ponerse en orden, y std::string tiene un enorme número de algoritmos de función miembro, la mayoría de los cuales podrían haber sido implementadas como funciones no miembro.