¿Por qué todas las funciones <algorithm> toman solo rangos, no contenedores?

49

Hay muchas funciones útiles <algorithm>, pero todas operan en "secuencias": pares de iteradores. Por ejemplo, si tengo un contenedor y me gusta ejecutarlo std::accumulate, necesito escribir:

std::vector<int> myContainer = ...;
int sum = std::accumulate(myContainer.begin(), myContainer.end(), 0);

Cuando todo lo que pretendo hacer es:

int sum = std::accumulate(myContainer, 0);

Lo cual es un poco más legible y más claro, a mis ojos.

Ahora puedo ver que puede haber casos en los que solo desee operar en partes de un contenedor, por lo que definitivamente es útil tener la opción de pasar rangos. Pero al menos en mi experiencia, ese es un caso especial raro. Por lo general, querré operar en contenedores enteros.

Es fácil escribir una función de contenedor que tiene un recipiente y las llamadas begin()y end()en él, pero este tipo de funciones de confort no están incluidos en la librería estándar.

Me gustaría saber el razonamiento detrás de esta elección de diseño STL.

guitarra letal
fuente
77
¿El STL generalmente proporciona envoltorios de conveniencia, o sigue la política anterior de C ++ aquí-las-herramientas-ahora-ve-dispara-en-el-pie?
Kilian Foth
2
Para el registro: en lugar de escribir su propio contenedor, debe usar los algoritmos de envoltura en Boost.Range; en este caso,boost::accumulate
ecatmur

Respuestas:

40

... definitivamente es útil tener la opción de pasar rangos. Pero al menos en mi experiencia, ese es un caso especial raro. Por lo general, querré operar en contenedores completos

Puede ser un caso especial raro en su experiencia , pero en realidad todo el contenedor es el caso especial, y el rango arbitrario es el caso general.

Ya ha notado que puede implementar todo el caso del contenedor utilizando la interfaz actual, pero no puede hacer lo contrario.

Entonces, el escritor de la biblioteca tenía la opción de implementar dos interfaces por adelantado, o solo implementar una que todavía cubra todos los casos.


Es fácil escribir una función de contenedor que tome un contenedor y llame a begin () y end (), pero esas funciones de conveniencia no están incluidas en la biblioteca estándar

Es cierto, especialmente porque las funciones gratuitas std::beginy std::endahora están incluidas.

Entonces, digamos que la biblioteca proporciona la sobrecarga de conveniencia:

template <typename Container>
void sort(Container &c) {
  sort(begin(c), end(c));
}

ahora también debe proporcionar la sobrecarga equivalente tomando un functor de comparación, y necesitamos proporcionar los equivalentes para cualquier otro algoritmo.

Pero al menos cubrimos todos los casos en los que queremos operar en un contenedor lleno, ¿verdad? Bueno, no del todo. Considerar

std::for_each(c.rbegin(), c.rend(), foo);

Si queremos manejar el funcionamiento al revés en contenedores, necesitamos otro método (o un par de métodos) por algoritmo existente.


Entonces, el enfoque basado en el rango es más general en el sentido simple de que:

  • puede hacer todo lo que puede hacer la versión de contenedor completo
  • el enfoque de contenedor completo duplica o triplica el número de sobrecargas requeridas, sin dejar de ser menos potente
  • los algoritmos basados ​​en rango también son componibles (puede apilar o encadenar adaptadores iteradores, aunque esto se hace más comúnmente en lenguajes funcionales y Python)

Hay otra razón válida, por supuesto, que es que era ya un montón de trabajo para obtener el STL normalizado, e inflando con envolturas de conveniencia antes de que había sido ampliamente utilizado no sería un gran uso del tiempo comité limitado. Si está interesado, puede encontrar el informe técnico de Stepanov & Lee aquí.

Como se mencionó en los comentarios, Boost.Range proporciona un enfoque más nuevo sin requerir cambios en el estándar.

Inútil
fuente
99
No creo que nadie, incluido OP, sugiera agregar sobrecargas para cada caso especial. Incluso si "contenedor completo" fuera menos común que "un rango arbitrario", definitivamente es mucho más común que "contenedor completo, invertido". Restrinja a f(c.begin(), c.end(), ...), y quizás solo a la sobrecarga más comúnmente utilizada (sin embargo, usted determina eso) para evitar duplicar el número de sobrecargas. Además, los adaptadores de iterador son completamente ortogonales (como observa, funcionan bien en Python, cuyos iteradores funcionan de manera muy diferente y no tienen la mayor parte de la potencia de la que habla).
3
Estoy de acuerdo con todo el contenedor, el caso de reenvío es muy común, pero quería señalar que es un subconjunto de usos posibles mucho más pequeño que la pregunta sugerida. Específicamente porque la elección no es entre un contenedor completo y un contenedor parcial, sino entre un contenedor completo y un contenedor parcial, posiblemente invertido o adaptado de otra manera. Y creo que es justo sugerir que la complejidad percibida del uso de adaptadores es mayor, si también tiene que cambiar la sobrecarga de su algoritmo.
Inútil
23
Tenga en cuenta la versión de contenedor podría cubrir todos los casos si el STL ofreció un objeto de rango; por ej std::sort(std::range(start, stop)).
3
Por el contrario: los algoritmos funcionales componibles (como mapa y filtro) toman un solo objeto que representa una colección y devuelven un solo objeto, ciertamente no usan nada parecido a un par de iteradores.
svick
3
una macro podría hacer esto: #define MAKE_RANGE(container) (container).begin(), (container).end()</jk>
ratchet freak
21

Resulta que hay un artículo de Herb Sutter sobre este mismo tema. Básicamente, el problema es la sobrecarga de la ambigüedad. Dado lo siguiente:

template<typename Iter>
void sort( Iter, Iter ); // 1

template<typename Iter, typename Pred>
void sort( Iter, Iter, Pred ); // 2

Y agregando lo siguiente:

template<typename Container>
void sort( Container& ); // 3

template<typename Container, typename Pred>
void sort( Container&, Pred ); // 4

Hará difícil distinguir 4y 1correctamente.

Los conceptos, tal como se propusieron pero finalmente no se incluyen en C ++ 0x, lo habrían resuelto, y también es posible eludirlo usando enable_if. Para algunos de los algoritmos, no hay ningún problema. Pero decidieron no hacerlo.

Ahora, después de leer todos los comentarios y respuestas aquí, creo que los rangeobjetos serían la mejor solución. Creo que voy a echar un vistazo Boost.Range.

guitarra letal
fuente
1
Bueno, usar solo un typename Iterparece ser demasiado tipeado para un lenguaje estricto. Yo preferiría por ejemplo, template<typename Container> void sort(typename Container::iterator, typename Container::iterator); // 1y template<template<class> Container, typename T> void sort( Container<T>&, std::function<bool(const T&)> ); // 4etc (que quizá resolvería el problema de la ambigüedad)
Vlad
@Vlad: Desafortunadamente, esto no funcionará para matrices antiguas simples, ya que no hay T[]::iteratordisponible. Además, el iterador adecuado no está obligado a ser un tipo anidado de ninguna colección, es suficiente definirlo std::iterator_traits.
firegurafiku
@firegurafiku: Bueno, los arreglos son fáciles de usar con algunos trucos básicos de TMP.
Vlad
11

Básicamente una decisión heredada. El concepto de iterador se modela en punteros, pero los contenedores no se modelan en matrices. Además, dado que las matrices son difíciles de pasar (en general necesitan un parámetro de plantilla que no sea de tipo para la longitud), a menudo una función solo tiene punteros disponibles.

Pero sí, en retrospectiva, la decisión es incorrecta. Hubiéramos estado mejor con un objeto de rango construible a partir de begin/endo begin/length; ahora tenemos múltiples _nalgoritmos con sufijo en su lugar.

MSalters
fuente
5

Agregarlos no le otorgaría poder (ya puede hacer todo el contenedor llamando .begin()y .end()usted mismo), y agregaría una cosa más a la biblioteca que debe ser especificada correctamente, agregada a las bibliotecas por los proveedores, probada, mantenida, etcétera etcétera.

En resumen, probablemente no esté allí porque no vale la pena mantener un conjunto de plantillas adicionales solo para evitar que los usuarios de contenedores completos escriban un parámetro de llamada de función adicional.

Michael Kohne
fuente
99
No me daría poder, eso es cierto, pero al final, tampoco lo hace std::getline, y aún así, está en la biblioteca. Uno podría ir tan lejos como para decir que las estructuras de control extendidas no me dan poder, ya que podría hacer todo usando solo ify goto. Sí, comparación injusta, lo sé;) Creo que puedo entender el / aplicación / carga de mantenimiento especificación de alguna manera, pero es sólo un pequeño envoltorio que estamos hablando aquí, así que ..
letal-guitarra
Codificar un pequeño contenedor no cuesta nada y tal vez no tenga ningún sentido estar en la biblioteca.
ebasconp
-1

Por ahora, http://en.wikipedia.org/wiki/C++11#Range-based_for_loop es una buena alternativa a std::for_each. Observe, no hay iteradores explícitos:

int a[5] = {1, 2, 3, 4, 5};
for (auto &i: a) { i *= 2; }

(Inspirado en https://stackoverflow.com/a/694534/2097284 .)

Camille Goudeseune
fuente
1
Solo resuelve esa parte <algorithm>, no todos los algos reales que necesitan begine enditeradores, ¡pero el beneficio no puede ser exagerado! Cuando probé C ++ 03 por primera vez en 2009, evité los iteradores debido a la repetición de los bucles, y por suerte o no, mis proyectos en ese momento lo permitieron. Al reiniciar en C ++ 11 en 2014, fue una actualización increíble, el lenguaje C ++ siempre debería haber sido, y ahora no puedo vivir sin auto &it: them:)
underscore_d