c++ - español - Algoritmos STL: ¿Por qué no hay una interfaz adicional para contenedores(adicional a los pares de iteradores)?

foreach c++ 11

Question

Me pregunto por qué el STL no sobrecarga sus funciones de algoritmo de manera que pueda llamarlas simplemente proporcionando un contenedor y no tomando la forma más detallada para pasar los iteradores de inicio y fin. Por supuesto, entiendo por qué también queremos usar un par de iteradores para procesar subsecuencias de un contenedor / matriz, sin embargo, casi todas las llamadas a estos métodos están usando un contenedor completo:

std::for_each(myVector.begin(), myVector.end(), doSomething);

Me parece más conveniente, legible y fácil de escribir solo escribir

std::for_each(myVector, doSomething);

¿Hay alguna razón por la cual STL no proporcione estas sobrecargas ? [EDITAR: no pretendo reemplazar la interfaz con esta restringida, sino también proporcionar una interfaz basada en contenedor]. ¿Introducen ambigüedad? Estoy pensando en algo como esto:

template<typename _Container, typename _Funct>
inline _Funct for_each(_Container c, _Funct f) {
    return for_each(begin(c), end(c), f);
}

¿Me estoy perdiendo de algo?

Answer 1

Aquí hay una respuesta relevante del blog de Herb Sutter: ¿Por qué no hay algoritmos basados ​​en contenedores ? Muestra contraejemplos como lo hizo Bo Persson en su respuesta anterior.

Answer 2

Cabe señalar que es muy fácil definir sus propios envoltorios triviales para agregar versiones en contenedores.

Por ejemplo:

template<typename Container, typename Func>
Func for_each(Container& c, Func f) {
    return std::for_each(c.begin(), c.end(), f);
}

Ahora puedes hacer la simple llamada que quieras. No hay ambigüedad porque sus envoltorios no están en el espacio de nombres estándar. Puede definir sobrecargas que tomen const Container &. Si desea versiones que llamen a los métodos del iterador de constantes de C ++ - 11 (por ejemplo, cbegin ()), creo que tendrá que nombrar al contenedor de manera diferente. Yo uso for_each_const.

Answer 3

Desafortunadamente, este es un problema mucho más genérico; a saber, que los iteradores fueron diseñados para vencer a las APIs de C y al estilo de Java "Ponga los algoritmos como métodos de cada contenedor individual" en las soluciones. Son la solución genérica de primera generación y no sorprende que, al reflexionar, no fueran tan buenos como otras soluciones genéricas posibles que se pueden obtener después de que pasemos veinte años pensando en ello.

Agregar estas sobrecargas de contenedores sería solo una ayuda de banda en una pequeña parte del espacio del problema; e incluso podría empeorar las cosas en el futuro. La solución es rangos, que C ++ está buscando para introducir lo antes posible.

Answer 4

Hay una biblioteca de Operadores de Rango con la intención de arreglar eso. La verbosidad se redujo varias veces.

Tu ejemplo se vería así:

auto newVector = myVector * doSomething;

Sí, doSomething - es sin paréntesis.

Lenguaje familiar desde shell (con algoritmo estándar):

auto t = vector<int>{3,2,1,4} | sort | unique; 

Answer 5

Introducen ambigüedad para muchos algoritmos. Un montón de <algorithm> parece

template<class iterator>
void do_something(iterator, iterator);

template<class iterator, class funct>
void do_something(iterator, iterator, funct);

Si agrega sobrecargas adicionales

template<class container, class funct>
void do_something(container, funct);

El compilador tendrá algunos problemas para entender qué do_something(x, y) . Si y son del mismo type , coincidirá con iterator = type y container = type, funct = type . ^*)

C ++ 11 intentó resolver esto con "concepts" que podían reconocer la diferencia entre un contenedor y un iterador. Sin embargo, estos "conceptos" resultaron ser demasiado complicados para convertirlos en el estándar, por lo que tampoco lo hicieron estas sobrecargas.

^*) aquí los compiladores no están de acuerdo, el compilador de Comeau afirma que es ambiguo, g ++ 4.5 y MSVC 10 llaman a la primera función.

Después de una discusión extremadamente larga en los comentarios, aquí hay un ejemplo en el que no funciona como se esperaba: usar un adaptador de contenedor que también puede funcionar como predicado.

#include <iostream>
#include <vector>

template<class iterator>
void test(iterator, iterator)
{
   std::cout << "test iterator/n";
}

template<class iterator, class predicate>
void test(iterator, iterator, predicate)
{
   std::cout << "test iterator, predicate/n";
}

template<class container, class predicate>
void test(const container& cont, predicate compare)
{
   std::cout << "test container, predicate/n";

   test(cont.begin(), cont.end(), compare);
}

template<class container>
class adapter
{
public:
   typedef typename container::iterator   iterator;

   adapter(container* cont) : cont(cont)
   { }

   iterator begin() const
   { return cont->begin(); }

   iterator end() const
   { return cont->end(); }

   bool operator()(const iterator& one, const iterator& two)
   { return *one < *two; }

private:
   container* cont;
};

int main()
{
   std::vector<int>   v;

   adapter<std::vector<int>>   a(&v);

   test(a, a);

}

Salida:

iterador de prueba

http://ideone.com/wps2tZ

Answer 6

Obviamente, como han mencionado otros usuarios, es un problema difícil, por lo que, lamentablemente, ha pasado mucho tiempo y todavía no hay una solución en la biblioteca estándar. Sin embargo, ya existen bibliotecas de rango disponibles, como Boost :: Range y la de las bibliotecas de Adobe Source, que proporcionan no solo la simplicidad de la interfaz que describe en su pregunta, sino también algunas características más sofisticadas.

Su ejemplo funciona perfectamente con Boost (estamos using namespace boost::range::adaptors continuación):

boost::for_each(myVector, doSomething);

También podemos cortar myVector rápida y fácilmente:

boost::for_each(myVector | sliced(10, 20), doSomething)

Incluso podemos comprimir myVector con otro, filtrar por un predicado y muestrear cada otro elemento de los pares resultantes en una sola declaración simple (esto requiere que desempaquemos en doSomethingElse las tuplas producidas por boost::combined ):

boost::for_each( boost::combined(myVector, myOtherVector) | strided(2), doSomethingElse)

Answer 7

Para entender que creo que uno debe tener que entender la filosofía de los algoritmos de C ++. Vamos a hacer esta pregunta primero:

¿Por qué los algoritmos de C ++ se implementan como funciones gratuitas en lugar de funciones miembro?

Bueno, la respuesta es bastante simple: evitar explosiones de implementación. Supongamos que tiene M contenedores y N algoritmos, y si los implementa como miembros de los contenedores, habrá implementaciones de M*N Hay dos problemas (relacionados) en este enfoque:

• Primero, no hace uso de la reutilización de código. La mayoría de las implementaciones se repetirán.
• En segundo lugar, las explosiones de implementación, que es una consecuencia directa de lo anterior.

C ++ resuelve estos problemas implementándolos como funciones gratuitas, de modo que solo tenga N implementaciones. Cada uno de los algoritmos que operan en un contenedor toma un par de iteradores, que definen el rango . Si desea sobrecargas que tomen contenedores, en lugar de un par de iteradores, entonces el Estándar tiene que proporcionar dichas sobrecargas para cada uno de los algoritmos, y habrá implementaciones 2*N que prácticamente anularán el propósito por el cual C ++ ha separado los algoritmos de Los contenedores en primer lugar, y la mitad de estas funciones no hacen nada que no pueda hacerse por la otra mitad.

Así que no creo que sea un gran problema. Solo para evitar un solo argumento, ¿por qué implementar N más funciones (que también imponen alguna restricción en su uso, como que no se le pueden pasar los punteros )? Sin embargo, si los programadores quieren tales funciones en su utilidad, ¡pueden implementarlas en cualquier momento junto con muchas otras basadas en el algoritmo estándar!

Usted comentó:

Bueno, las implementaciones 2 * N son de hecho solo implementaciones N. Las otras N son sobrecargas en línea que llaman directamente la versión "real" del algoritmo, por lo que son solo una cosa de cabecera. Proporcionar sobrecargas de contenedores no anula el propósito de separar los algoritmos de los contenedores, ya que (como puede ver en mi ejemplo) pueden usar plantillas para manejar todo tipo de contenedores.

Basado en esta lógica, uno puede argumentar muy bien para los algoritmos M*N ¿Así que hazles funciones de miembro también (y llama a las funciones gratuitas internamente)? Estoy seguro de que muchos chicos de OOP preferirían

auto result = container.accumulate(val);

terminado

auto result = std::accumulate(container.begin(), container.end(), val);