¿Cómo hacer que mi tipo personalizado funcione con "basado en rango para bucles"?

252

Como muchas personas en estos días, he estado probando las diferentes características que trae C ++ 11. Uno de mis favoritos es el "basado en rango para bucles".

Entiendo que:

for(Type& v : a) { ... }

Es equivalente a:

for(auto iv = begin(a); iv != end(a); ++iv)
{
  Type& v = *iv;
  ...
}

Y eso begin()simplemente regresa a.begin()para contenedores estándar.

Pero, ¿qué sucede si quiero que mi tipo personalizado sea "basado en rango para bucle" ?

¿Debo especializarme begin()y end()?

Si mi tipo personalizado pertenece al espacio de nombres xml, ¿debo definir xml::begin()o std::begin()?

En resumen, ¿cuáles son las pautas para hacer eso?

ereOn
fuente
Es posible ya sea definiendo un miembro begin/endo un amigo, estático o libre begin/end. Solo tenga cuidado en qué espacio de nombres coloca la función gratuita: stackoverflow.com/questions/28242073/…
alfC
¿Podría alguien por favor publicar una respuesta con el ejemplo de un rango de valor flotante que no es un contenedor: for( auto x : range<float>(0,TWO_PI, 0.1F) ) { ... }. Tengo curiosidad por cómo evitar el hecho de que `´operator! = ()` `Es difícil de definir. ¿Y qué hay de la desreferenciación ( *__begin) en este caso? ¡Creo que sería una gran contribución si alguien nos mostrara cómo se hace eso !
BitTickler

Respuestas:

183

El estándar ha cambiado desde que la pregunta (y la mayoría de las respuestas) se publicaron en la resolución de este informe de defectos .

La forma de hacer que un for(:)bucle funcione en su tipo Xes ahora una de dos maneras:

  • Crear miembro X::begin()y X::end()que devuelva algo que actúa como un iterador

  • Cree una función libre begin(X&)y end(X&)que devuelva algo que actúe como un iterador, en el mismo espacio de nombres que su tipo X.

Y similar para las constvariaciones. Esto funcionará tanto en los compiladores que implementan los cambios del informe de defectos como en los compiladores que no lo hacen.

Los objetos devueltos no tienen que ser iteradores. El for(:)bucle, a diferencia de la mayoría de las partes del estándar C ++, se especifica para expandirse a algo equivalente a :

for( range_declaration : range_expression )

se convierte en:

{
  auto && __range = range_expression ;
  for (auto __begin = begin_expr,
            __end = end_expr;
            __begin != __end; ++__begin) {
    range_declaration = *__begin;
    loop_statement
  }
}

donde las variables que comienzan con __son solo para exposición, y begin_expry end_expres la magia que llama begin/ end

Los requisitos sobre el valor de retorno de inicio / fin son simples: debe sobrecargar previamente ++, asegurarse de que las expresiones de inicialización sean válidas, binarias !=que se pueden usar en un contexto booleano, unario *que devuelve algo con lo que puede asignar-inicializar range_declarationy exponer un público incinerador de basuras.

Hacerlo de una manera que no sea compatible con un iterador es probablemente una mala idea, ya que las futuras iteraciones de C ++ podrían ser relativamente cautelosas sobre romper su código si lo hace.

Por otro lado, es razonablemente probable que una futura revisión de la norma permita end_exprdevolver un tipo diferente de begin_expr. Esto es útil porque permite una evaluación de "final diferido" (como la detección de terminación nula) que es fácil de optimizar para ser tan eficiente como un bucle C escrito a mano, y otras ventajas similares.


¹ Tenga en cuenta que los for(:)bucles almacenan cualquier temporal en una auto&&variable y se lo pasan a usted como un lvalue. No puede detectar si está iterando sobre un valor temporal (u otro valor r); tal sobrecarga no será invocada por un for(:)bucle. Ver [stmt.ranged] 1.2-1.3 de n4527.

² Llame al método begin/ end, o busque solo ADL de función libre begin/ end, o magia para soporte de matriz de estilo C. Tenga en cuenta que std::beginno se llama a menos que range_expressiondevuelva un objeto de tipo namespace stdo dependiente del mismo.


En la expresión de rango para ha sido actualizada

{
  auto && __range = range_expression ;
  auto __begin = begin_expr;
  auto __end = end_expr;
  for (;__begin != __end; ++__begin) {
    range_declaration = *__begin;
    loop_statement
  }
}

con los tipos de __beginy __endhan sido desacoplados.

Esto permite que el iterador final no sea del mismo tipo que begin. Su tipo de iterador final puede ser un "centinela" que solo es compatible !=con el tipo de iterador de inicio.

Un ejemplo práctico de por qué esto es útil es que su iterador final puede leer "compruebe char*si está apuntando '0'" cuando ==con un char*. Esto permite que una expresión de rango de C ++ genere un código óptimo al iterar sobre un char*búfer con terminación nula .

struct null_sentinal_t {
  template<class Rhs,
    std::enable_if_t<!std::is_same<Rhs, null_sentinal_t>{},int> =0
  >
  friend bool operator==(Rhs const& ptr, null_sentinal_t) {
    return !*ptr;
  }
  template<class Rhs,
    std::enable_if_t<!std::is_same<Rhs, null_sentinal_t>{},int> =0
  >
  friend bool operator!=(Rhs const& ptr, null_sentinal_t) {
    return !(ptr==null_sentinal_t{});
  }
  template<class Lhs,
    std::enable_if_t<!std::is_same<Lhs, null_sentinal_t>{},int> =0
  >
  friend bool operator==(null_sentinal_t, Lhs const& ptr) {
    return !*ptr;
  }
  template<class Lhs,
    std::enable_if_t<!std::is_same<Lhs, null_sentinal_t>{},int> =0
  >
  friend bool operator!=(null_sentinal_t, Lhs const& ptr) {
    return !(null_sentinal_t{}==ptr);
  }
  friend bool operator==(null_sentinal_t, null_sentinal_t) {
    return true;
  }
  friend bool operator!=(null_sentinal_t, null_sentinal_t) {
    return false;
  }
};

ejemplo en vivo en un compilador sin soporte completo de C ++ 17; forbucle expandido manualmente.

Yakk - Adam Nevraumont
fuente
Si el basado en el rango utiliza un mecanismo de búsqueda diferente, entonces tal vez sea posible organizar que el basado en el rango obtenga un par beginy endfunciones diferentes de las que están disponibles en el código normal. Quizás podrían ser muy especializados para comportarse de manera diferente (es decir, más rápido al ignorar el argumento final para obtener las máximas optimizaciones posibles). Pero no soy lo suficientemente bueno con los espacios de nombres para estar seguro de cómo hacerlo.
Aaron McDaid
@AaronMcDaid no es muy práctico. Fácilmente terminaría con resultados sorprendentes, porque algunos medios de llamar a begin / end terminarían con el rango basado en begin / end, y otros no. Los cambios inocuos (del lado del cliente) obtendrían cambios de comportamiento.
Yakk - Adam Nevraumont
1
No es necesario begin(X&&). El temporal se suspende en el aire auto&&en un rango basado en, y beginsiempre se llama con un valor l ( __range).
TC
2
Esta respuesta realmente se beneficiaría de un ejemplo de plantilla que se puede copiar e implementar.
Tomáš Zato - Restablece a Mónica el
Prefiero poner énfasis en las propiedades del tipo de iterador (*, ++,! =). Debería pedirle que reformule esta respuesta para que las especificaciones de tipo de iterador sean más audaces.
Red.Wave
62

Escribo mi respuesta porque algunas personas podrían estar más felices con un ejemplo simple de la vida real sin STL incluido.

Tengo mi propia implementación de matriz de datos simple por alguna razón, y quería usar el rango basado en bucle. Aquí está mi solución:

 template <typename DataType>
 class PodArray {
 public:
   class iterator {
   public:
     iterator(DataType * ptr): ptr(ptr){}
     iterator operator++() { ++ptr; return *this; }
     bool operator!=(const iterator & other) const { return ptr != other.ptr; }
     const DataType& operator*() const { return *ptr; }
   private:
     DataType* ptr;
   };
 private:
   unsigned len;
   DataType *val;
 public:
   iterator begin() const { return iterator(val); }
   iterator end() const { return iterator(val + len); }

   // rest of the container definition not related to the question ...
 };

Entonces el ejemplo de uso:

PodArray<char> array;
// fill up array in some way
for(auto& c : array)
  printf("char: %c\n", c);
csjpeter
fuente
2
El ejemplo tiene los métodos begin () y end (), y también tiene una clase de iterador de ejemplo básico (fácil de entender) que se puede ajustar fácilmente para cualquier tipo de contenedor personalizado. Comparar std :: array <> y cualquier posible implementación alternativa es una pregunta diferente, y en mi opinión no tiene nada que ver con el bucle for basado en rango.
csjpeter
¡Esta es una respuesta muy concisa y práctica! ¡Era exactamente lo que estaba buscando! ¡Gracias!
Zac Taylor
1
¿Sería más apropiado eliminar el const calificador de devolución const DataType& operator*()y permitir que el usuario elija usar const auto&o auto&? Gracias de todos modos, gran respuesta;)
Rick
53

La parte relevante de la norma es 6.5.4 / 1:

si _RangeT es un tipo de clase, los identificadores no calificados comienzan y terminan se buscan en el alcance de la clase _RangeT como si la búsqueda de acceso de miembros de clase (3.4.5), y si cualquiera (o ambos) encuentra al menos una declaración, comience - expr y end-expr son __range.begin()y __range.end(), respectivamente;

- de lo contrario, begin-expr y end-expr son begin(__range)y end(__range), respectivamente, donde se buscan begin y end con búsqueda dependiente de argumentos (3.4.2). Para los fines de esta búsqueda de nombres, el espacio de nombres estándar es un espacio de nombres asociado.

Entonces, puede hacer lo siguiente:

  • definir beginy endfunciones miembro
  • funciones definidas beginy endlibres que ADL encontrará (versión simplificada: colóquelas en el mismo espacio de nombres que la clase)
  • especializarse std::beginystd::end

std::beginllama a la begin()función miembro de todos modos, por lo que si solo implementa uno de los anteriores, los resultados deberían ser los mismos sin importar cuál elija. Esos son los mismos resultados para los bucles basados ​​en rangos, y también el mismo resultado para el simple código mortal que no tiene sus propias reglas mágicas de resolución de nombres, por lo que solo lo using std::begin;sigue una llamada no calificada begin(a).

Sin embargo, si implementa las funciones miembro y las funciones ADL, los bucles basados ​​en rangos deberían llamar a las funciones miembro, mientras que los simples mortales llamarán a las funciones ADL. ¡Mejor asegúrate de que hagan lo mismo en ese caso!

Si lo que estás escribiendo implementa la interfaz contenedor, entonces tendrá begin()y end()funciones miembro, ya que debería ser suficiente. Si se trata de un rango que no es un contenedor (lo que sería una buena idea si es inmutable o si no conoce el tamaño por adelantado), puede elegir libremente.

De las opciones que diseñe, tenga en cuenta que no debe sobrecargarse std::begin(). Se le permite especializar plantillas estándar para un tipo definido por el usuario, pero aparte de eso, agregar definiciones al espacio de nombres estándar es un comportamiento indefinido. Pero de todos modos, la especialización de las funciones estándar es una mala elección, solo porque la falta de especialización parcial de la función significa que solo puede hacerlo para una sola clase, no para una plantilla de clase.

Steve Jessop
fuente
¿No hay ciertos requisitos que el iterador cumple mucho? es decir, ser un ForwardIterator o algo por el estilo.
Pubby
2
@Pubby: Mirando 6.5.4, creo que InputIterator es suficiente. Pero en realidad no creo que el tipo devuelto tenga que ser un iterador para un rango basado en. La declaración se define en el estándar por lo que es equivalente, por lo que es suficiente para implementar solo las expresiones utilizadas en el código en el estándar: operadores !=, prefijo ++y unario *. Probablemente no sea prudente implementar begin()y end()funciones miembro o funciones ADL no miembros que devuelven cualquier cosa que no sea un iterador, pero creo que es legal. Especializado std::beginen devolver un no iterador es UB, creo.
Steve Jessop
¿Estás seguro de que no debes sobrecargar std :: begin? Pregunto porque la biblioteca estándar lo hace en algunos casos.
ThreeBit 01 de
@ThreeBit: sí, estoy seguro. Las reglas para las implementaciones de bibliotecas estándar son diferentes de las reglas para los programas.
Steve Jessop
3
Esto debe actualizarse para open-std.org/jtc1/sc22/wg21/docs/cwg_defects.html#1442 .
TC
34

¿Debo especializarme begin () y end ()?

Que yo sepa, eso es suficiente. También debe asegurarse de que el incremento del puntero se obtenga desde el principio hasta el final.

El siguiente ejemplo (falta la versión constante de inicio y fin) se compila y funciona bien.

#include <iostream>
#include <algorithm>

int i=0;

struct A
{
    A()
    {
        std::generate(&v[0], &v[10], [&i](){  return ++i;} );
    }
    int * begin()
    {
        return &v[0];
    }
    int * end()
    {
        return &v[10];
    }

    int v[10];
};

int main()
{
    A a;
    for( auto it : a )
    {
        std::cout << it << std::endl;
    }
}

Aquí hay otro ejemplo con begin / end como funciones. Ellos tienen que estar en el mismo espacio de nombres que la clase, debido a ADL:

#include <iostream>
#include <algorithm>


namespace foo{
int i=0;

struct A
{
    A()
    {
        std::generate(&v[0], &v[10], [&i](){  return ++i;} );
    }

    int v[10];
};

int *begin( A &v )
{
    return &v.v[0];
}
int *end( A &v )
{
    return &v.v[10];
}
} // namespace foo

int main()
{
    foo::A a;
    for( auto it : a )
    {
        std::cout << it << std::endl;
    }
}
BЈовић
fuente
1
@ereOn En el mismo espacio de nombres donde se define la clase. Vea el segundo ejemplo
B 17овић
2
Felicitaciones también :) Podría valer la pena mencionar los términos Búsqueda dependiente de argumentos (ADL) o Búsqueda Koenig para el segundo ejemplo (para explicar por qué la función libre debería estar en el mismo espacio de nombres que la clase en la que opera).
Matthieu M.
1
@ereOn: en realidad, no lo haces. ADL se trata de extender los ámbitos para buscar para incluir automáticamente los espacios de nombres a los que pertenecen los argumentos. Hay un buen artículo de ACCU sobre la resolución de sobrecarga, que desafortunadamente omite la parte de búsqueda de nombres. La búsqueda de nombres implica la función de recopilación de candidatos, comienza por buscar en el ámbito actual + los ámbitos de los argumentos. Si no se encuentra ningún nombre que coincida, asciende al ámbito principal del ámbito actual y busca de nuevo ... hasta llegar al ámbito global.
Matthieu M.
1
@ BЈовић lo siento, pero ¿por qué motivo en la función end () devuelve un puntero peligroso? Sé que funciona, pero quiero entender la lógica de esto. El final de la matriz es v [9], ¿por qué devolverías v [10]?
gedamial
1
@gedamial Estoy de acuerdo. Creo que debería serlo return v + 10. &v[10]desreferencia la ubicación de la memoria justo después de la matriz.
Millie Smith el
16

En caso de que desee realizar una copia de iteración de una clase directamente con su std::vectoro std::mapmiembro, aquí está el código para ello:

#include <iostream>
using std::cout;
using std::endl;
#include <string>
using std::string;
#include <vector>
using std::vector;
#include <map>
using std::map;


/////////////////////////////////////////////////////
/// classes
/////////////////////////////////////////////////////

class VectorValues {
private:
    vector<int> v = vector<int>(10);

public:
    vector<int>::iterator begin(){
        return v.begin();
    }
    vector<int>::iterator end(){
        return v.end();
    }
    vector<int>::const_iterator begin() const {
        return v.begin();
    }
    vector<int>::const_iterator end() const {
        return v.end();
    }
};

class MapValues {
private:
    map<string,int> v;

public:
    map<string,int>::iterator begin(){
        return v.begin();
    }
    map<string,int>::iterator end(){
        return v.end();
    }
    map<string,int>::const_iterator begin() const {
        return v.begin();
    }
    map<string,int>::const_iterator end() const {
        return v.end();
    }

    const int& operator[](string key) const {
        return v.at(key);
    }
    int& operator[](string key) {
        return v[key];
    } 
};


/////////////////////////////////////////////////////
/// main
/////////////////////////////////////////////////////

int main() {
    // VectorValues
    VectorValues items;
    int i = 0;
    for(int& item : items) {
        item = i;
        i++;
    }
    for(int& item : items)
        cout << item << " ";
    cout << endl << endl;

    // MapValues
    MapValues m;
    m["a"] = 1;
    m["b"] = 2;
    m["c"] = 3;
    for(auto pair: m)
        cout << pair.first << " " << pair.second << endl;
}
Chris Redford
fuente
2
Vale la pena mencionar que const_iteratortambién se puede acceder en un auto(C ++ 11) forma compatible a través de cbegin, cend, etc.
underscore_d
2

Aquí, comparto el ejemplo más simple de crear tipos personalizados, que funcionará con " bucle basado en rango ":

#include<iostream>
using namespace std;

template<typename T, int sizeOfArray>
class MyCustomType
{
private:
    T *data;
    int indx;
public:
    MyCustomType(){
        data = new T[sizeOfArray];
        indx = -1;
    }
    ~MyCustomType(){
        delete []data;
    }
    void addData(T newVal){
        data[++indx] = newVal;
    }

    //write definition for begin() and end()
    //these two method will be used for "ranged based loop idiom"
    T* begin(){
        return &data[0];
    }
    T* end(){
        return  &data[sizeOfArray];
    }
};
int main()
{
    MyCustomType<double, 2> numberList;
    numberList.addData(20.25);
    numberList.addData(50.12);
    for(auto val: numberList){
        cout<<val<<endl;
    }
    return 0;
}

Espero que sea útil para algunos desarrolladores novatos como yo: p :)
Gracias.

RajibTheKing
fuente
¿por qué no asignar un elemento adicional para evitar desreferenciar la memoria no válida en su método final?
AndersK
@Anders Porque casi todos los iteradores finales apuntan después del final de su estructura de contención. La end()función en sí misma obviamente no elimina la referencia de una ubicación de memoria inadecuada, ya que solo toma la 'dirección de' esta ubicación de memoria. Agregar un elemento adicional significaría que necesitaría más memoria, y usarlo your_iterator::end()de cualquier manera que desreferenciara ese valor no funcionaría con ningún otro iterador de todos modos porque están construidos de la misma manera.
Qqwy
@Qqwy su método final de-refences - En return &data[sizeofarray]mi humilde opinión, solo debería devolver los datos de la dirección + sizeofarray, pero qué sé,
AndersK
@ Ansders Estás en lo correcto. Gracias por mantenerme alerta :-). Sí, data + sizeofarraysería la forma correcta de escribir esto.
Qqwy
1

La respuesta de Chris Redford también funciona para contenedores Qt (por supuesto). Aquí hay una adaptación (observe que devuelvo a constBegin(), respectivamente, constEnd()de los métodos const_iterator):

class MyCustomClass{
    QList<MyCustomDatatype> data_;
public:    
    // ctors,dtor, methods here...

    QList<MyCustomDatatype>::iterator begin() { return data_.begin(); }
    QList<MyCustomDatatype>::iterator end() { return data_.end(); }
    QList<MyCustomDatatype>::const_iterator begin() const{ return data_.constBegin(); }
    QList<MyCustomDatatype>::const_iterator end() const{ return data_.constEnd(); }
};
user2366975
fuente
0

Me gustaría elaborar algunas partes de la respuesta de @Steve Jessop, que al principio no entendí. Espero eso ayude.

std::beginllama a la begin()función miembro de todos modos, por lo que si solo implementa uno de los anteriores, los resultados deberían ser los mismos sin importar cuál elija. Esos son los mismos resultados para los bucles basados ​​en rangos, y también el mismo resultado para el simple código mortal que no tiene sus propias reglas mágicas de resolución de nombres, por lo que solo lo using std::begin;sigue una llamada no calificada begin(a).

Sin embargo, si implementa las funciones miembro y las funciones ADL , los bucles basados ​​en rangos deberían llamar a las funciones miembro, mientras que los simples mortales llamarán a las funciones ADL. ¡Mejor asegúrate de que hagan lo mismo en ese caso!


https://en.cppreference.com/w/cpp/language/range-for :

  • Si ...
  • Si range_expressiones una expresión de un tipo de clase Cque tiene un miembro llamado beginy un miembro llamado end(independientemente del tipo o accesibilidad de dicho miembro), entonces begin_expres __range.begin() y end_expres __range.end();
  • De lo contrario, begin_expris begin(__range)y end_expris end(__range), que se encuentran a través de una búsqueda dependiente de argumentos (no se realiza una búsqueda no ADL).

Para el bucle basado en rango, las funciones miembro se seleccionan primero.

Pero para

using std::begin;
begin(instance);

Las funciones ADL se seleccionan primero.


Ejemplo:

#include <iostream>
#include <string>
using std::cout;
using std::endl;

namespace Foo{
    struct A{
        //member function version
        int* begin(){
            cout << "111";
            int* p = new int(3);  //leak I know, for simplicity
            return p;
        }
        int *end(){
            cout << "111";
            int* p = new int(4);
            return p;
        }
    };

    //ADL version

    int* begin(A a){
        cout << "222";
        int* p = new int(5);
        return p;
    }

    int* end(A a){
        cout << "222";
        int* p = new int(6);
        return p;
    }

}

int main(int argc, char *args[]){
//    Uncomment only one of two code sections below for each trial

//    Foo::A a;
//    using std::begin;
//    begin(a);  //ADL version are selected. If comment out ADL version, then member functions are called.


//      Foo::A a;
//      for(auto s: a){  //member functions are selected. If comment out member functions, then ADL are called.
//      }
}
Almiar
fuente