Como fazer meu tipo personalizado funcionar com "intervalo de loops"?

252

Como muitas pessoas hoje em dia, tenho tentado os diferentes recursos que o C ++ 11 traz. Um dos meus favoritos é o "intervalo para loops".

Eu entendi aquilo:

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

É equivalente a:

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

E isso begin()simplesmente retorna a.begin()para contêineres padrão.

Mas e se eu quiser tornar meu tipo personalizado "baseado em intervalo para loop" ?

Devo apenas me especializar begin()e end()?

Se meu tipo personalizado pertencer ao espaço para nome xml, devo definir xml::begin()ou std::begin()?

Em resumo, quais são as diretrizes para fazer isso?

ereOn
fonte
É possível definir um membro begin/endou um amigo, estático ou gratuito begin/end. Basta ter cuidado em que namespace você colocar a função livre: stackoverflow.com/questions/28242073/...
ALFC
Alguém poderia por favor postar uma resposta com o exemplo de uma faixa de valor flutuante que não é um recipiente: for( auto x : range<float>(0,TWO_PI, 0.1F) ) { ... }. Estou curioso para saber como você trabalha com o fato de que `´operator! = ()` `É difícil de definir. E o desreferenciamento ( *__begin) neste caso? Eu acho que seria uma grande contribuição se alguém nos mostrasse como isso é feito!
BitTickler 13/10/1918

Respostas:

183

O padrão foi alterado desde que a pergunta (e a maioria das respostas) foi publicada na resolução deste relatório de defeitos .

A maneira de fazer um for(:)loop funcionar no seu tipo Xagora é uma das duas maneiras:

  • Criar membro X::begin()e X::end()retornar algo que age como um iterador

  • Crie uma função livre begin(X&)e end(X&)que retorne algo que age como um iterador, no mesmo espaço de nome que seu tipo X.

E semelhante para constvariações. Isso funcionará tanto nos compiladores que implementam as alterações no relatório de defeitos quanto nos compiladores que não o fazem.

Os objetos retornados não precisam ser realmente iteradores. O for(:)loop, diferente da maioria das partes do padrão C ++, é especificado para expandir para algo equivalente a :

for( range_declaration : range_expression )

torna-se:

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

onde as variáveis ​​que começam com __são apenas para exposição e begin_expre end_expré a mágica que chama begin/ end

Os requisitos do valor de retorno inicial / final são simples: você deve sobrecarregar pré- ++, garantir que as expressões de inicialização sejam válidas, binárias !=que podem ser usadas em um contexto booleano, unárias *que retornam algo com o qual você pode atribuir-inicializar range_declaratione expor um público destruidor.

Fazer isso de uma maneira que não seja compatível com um iterador é provavelmente uma péssima idéia, já que futuras iterações do C ++ podem ser relativamente descuidadas quanto à quebra de seu código, se você o fizer.

Como um aparte, é razoavelmente provável que uma revisão futura da norma permita end_exprretornar um tipo diferente begin_expr. Isso é útil, pois permite a avaliação de "final lento" (como a detecção de terminação nula) que é fácil de otimizar para ser tão eficiente quanto um loop C escrito à mão e outras vantagens semelhantes.


¹ Observe que os for(:)loops armazenam qualquer temporário em uma auto&&variável e o passam para você como um valor l. Você não pode detectar se está iterando sobre um valor temporário (ou outro rvalue); essa sobrecarga não será chamada por um for(:)loop. Veja [stmt.ranged] 1.2-1.3 da n4527.

² Ou chamar o begin/ endmétodo, ou ADL-única pesquisa de função livre begin/ end, ou mágica para suporte de matriz de estilo C. Observe que std::beginnão é chamado, a menos que range_expressionretorne um objeto do tipo namespace stdou dependente do mesmo.


No a expressão de intervalo para foi atualizada

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

com os tipos de __begine __endforam dissociados.

Isso permite que o iterador final não seja do mesmo tipo que o inicial. O seu tipo de iterador final pode ser um "sentinela" que suporta apenas !=o tipo de iterador de início.

Um exemplo prático de por que isso é útil é que o iterador final pode ler "verifique seu char*para ver se aponta para '0'" quando estiver ==com a char*. Isso permite que uma expressão de intervalo de C ++ gere código ideal ao iterar em um char*buffer terminado por nulo .

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

exemplo ao vivo em um compilador sem suporte completo a C ++ 17; forloop expandido manualmente.

Yakk - Adam Nevraumont
fonte
Se for baseado em intervalo, usa um mecanismo de pesquisa diferente, talvez seja possível organizar esse intervalo para obter um par begine endfunções diferentes do que está disponível no código normal. Talvez eles possam ser muito especializados para se comportar de maneira diferente (ou seja, mais rápido ignorando o argumento final para obter as otimizações possíveis ao máximo). Mas eu não sou bom o suficiente com espaços para nome para ter certeza de como fazer isso.
Aaron McDaid
@AaronMcDaid não é muito prático. Você acabaria facilmente com resultados surpreendentes, porque alguns meios de chamar begin / end terminariam com o intervalo baseado em begin / end, e outros não. Mudanças inócuas (do lado do cliente) receberiam mudanças de comportamento.
Yakk - Adam Nevraumont
1
Você não precisa begin(X&&). O temporário é suspenso no ar por auto&&um intervalo baseado em e beginé sempre chamado com um lvalue ( __range).
TC
2
Essa resposta realmente se beneficiaria de um exemplo de modelo que você pode copiar e implementar.
Tomáš Zato - Restabelece Monica
Eu prefiro enfatizar as propriedades do tipo de iterador (*, ++,! =). Peço que você reformule esta resposta para tornar as especificações do tipo de iterador mais ousadas.
Red.Wave em 3/03
62

Escrevo minha resposta porque algumas pessoas podem ficar mais felizes com um exemplo simples da vida real sem o STL.

Eu tenho minha própria implementação simples de matriz de dados por algum motivo e queria usar o intervalo baseado em loop. Aqui está a minha solução:

 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 ...
 };

Em seguida, o exemplo de uso:

PodArray<char> array;
// fill up array in some way
for(auto& c : array)
  printf("char: %c\n", c);
csjpeter
fonte
2
O exemplo possui os métodos begin () e end () e também possui uma classe de iterador de exemplo básica (fácil de entender) que pode ser facilmente ajustada para qualquer tipo de contêiner personalizado. Comparar std :: array <> e qualquer possível implementação alternativa é uma questão diferente e, na minha opinião, não tem nada a ver com o loop for baseado em intervalo.
csjpeter
Esta é uma resposta muito concisa e prática! Era exatamente o que eu estava procurando! Obrigado!
Zac Taylor
1
Seria mais apropriado remover o const qualificador de retorno const DataType& operator*()e deixar o usuário optar por usar const auto&ou auto&? Obrigado de qualquer maneira, ótima resposta;)
Rick
53

A parte relevante da norma é 6.5.4 / 1:

se _RangeT é um tipo de classe, os IDs desqualificados começam e terminam são pesquisados ​​no escopo da classe _RangeT como se pela consulta de acesso de membro da classe (3.4.5) e se (ou ambos) encontrar pelo menos uma declaração, inicie - expr e end-expr são __range.begin()e __range.end(), respectivamente;

- caso contrário, begin-expr e end-expr são begin(__range)e end(__range), respectivamente, onde begin e end são pesquisados ​​com pesquisa dependente de argumento (3.4.2). Para os fins dessa pesquisa de nome, o namespace std é um namespace associado.

Portanto, você pode fazer o seguinte:

  • definir begine endfunções-membro
  • definir begine endliberar funções que serão encontradas pelo ADL (versão simplificada: coloque-as no mesmo espaço de nome da classe)
  • especializar std::beginestd::end

std::beginchama a begin()função membro de qualquer maneira, portanto, se você implementar apenas uma das opções acima, os resultados deverão ser os mesmos, independentemente de qual você escolher. Esses são os mesmos resultados para loops baseados em varredura, e também o mesmo resultado para mero código mortal que não possui suas próprias regras de resolução de nomes mágicos, o que é using std::begin;seguido por uma chamada não qualificada para begin(a).

Se você implementar as funções de membro e as funções de ADL, no entanto, os loops baseados em intervalo devem chamar as funções de membro, enquanto meros mortais chamarão as funções de ADL. Melhor garantir que eles façam a mesma coisa nesse caso!

Se a coisa que você está escrevendo implementa a interface recipiente, então ele terá begin()e end()funções membro já, que deve ser suficiente. Se for um intervalo que não é um contêiner (o que seria uma boa ideia se for imutável ou se você não souber o tamanho antecipadamente), você poderá escolher.

Das opções apresentadas, observe que você não deve sobrecarregar std::begin(). Você tem permissão para especializar modelos padrão para um tipo definido pelo usuário, mas, além disso, adicionar definições ao namespace std é um comportamento indefinido. Mas, enfim, a especialização de funções padrão é uma má escolha, apenas porque a falta de especialização parcial da função significa que você pode fazê-lo apenas para uma única classe, não para um modelo de classe.

Steve Jessop
fonte
Não existem certos requisitos que o iterador atende muito? ou seja, seja um ForwardIterator ou algo desse tipo.
Pubby
2
@Pubby: Olhando para 6.5.4, acho que o InputIterator é suficiente. Mas na verdade eu não acho que o tipo retornado tem que ser um iterador em tudo para baseada no intervalo para. A instrução é definida no padrão pelo que é equivalente; portanto, basta implementar apenas as expressões usadas no código no padrão: operadores !=, prefixo ++e unário *. É provavelmente imprudente para implementar begin()e end()funções membro ou funções ADL terceiros que o retorno outra coisa senão um iterador, mas eu acho que é legal. Especializar std::beginpara devolver um não-iterador é o UB, eu acho.
21812 Steve Jobs (
Você tem certeza de que não deve sobrecarregar std :: begin? Eu pergunto porque a biblioteca padrão faz isso em alguns casos em si.
ThreeBit 01/04
@ThreeBit: sim, tenho certeza. As regras para implementações de bibliotecas padrão são diferentes das regras para programas.
21813 Steve Joplin
3
Isso precisa ser atualizado para open-std.org/jtc1/sc22/wg21/docs/cwg_defects.html#1442 .
TC
34

Devo apenas me especializar begin () e end ()?

Até onde eu sei, isso é suficiente. Você também precisa garantir que o incremento do ponteiro seja obtido do começo ao fim.

O próximo exemplo (está faltando a versão const do begin e end) compila e funciona bem.

#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;
    }
}

Aqui está outro exemplo com begin / end como funções. Eles precisam estar no mesmo espaço para nome da classe, devido à 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Јовић
fonte
1
@ereOn No mesmo espaço para nome em que a classe está definida. Veja o 2º exemplo
B'овић
2
Parabéns também :) Pode valer a pena mencionar os termos Pesquisa de Dependência de Argumento (ADL) ou Pesquisa de Koenig para o segundo exemplo (para explicar por que a função livre deve estar no mesmo espaço de nome da classe em que opera).
precisa
1
@ereOn: na verdade, você não. A ADL trata de estender os escopos à pesquisa para incluir automaticamente os namespaces aos quais os argumentos pertencem. Há um bom artigo da ACCU sobre resolução de sobrecarga, que infelizmente ignora a parte de pesquisa de nome. A pesquisa de nome envolve a coleta da função de candidatos. Você começa procurando no escopo atual + nos escopos dos argumentos. Se nenhum nome for encontrado que corresponda, você passa para o escopo pai do escopo atual e pesquisa novamente ... até atingir o escopo global.
Matthieu M.
1
@ Desculpe, mas por qual motivo na função end () você retorna um ponteiro perigoso? Eu sei que funciona, mas quero entender a lógica disso. O final da matriz é v [9], por que você retornaria v [10]?
gedamial
1
@gedamial Eu concordo. Eu acho que deveria ser return v + 10. &v[10]desreferencia a localização da memória logo após a matriz.
Millie Smith #
16

Caso você queira fazer o backup da iteração de uma classe diretamente com o membro std::vectorou std::map, aqui está o código para isso:

#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
fonte
2
Vale a pena mencionar que const_iteratortambém pode ser acessado em um auto(++ 11 C) forma-compatível via cbegin, cendetc.
underscore_d
2

Aqui, estou compartilhando o exemplo mais simples de criação de tipo personalizado, que funcionará com " loop for for baseado em intervalo ":

#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 seja útil para algum desenvolvedor iniciante como eu: p :)
Obrigado.

RajibTheKing
fonte
por que não alocar um elemento extra para evitar a exclusão de memória inválida no seu método final?
AndersK
Porque @Anders ponto de quase todos os iterators-finais para após o fim da sua estrutura que contém. A end()função em si, obviamente, não faz dereference um local de memória imprópria, já que ele só tem o 'endereço-de' este local de memória. Adicionar um elemento extra significaria que você precisaria de mais memória e usar your_iterator::end()de qualquer maneira que desdiferenciasse esse valor não funcionaria com outros iteradores, porque eles são criados da mesma maneira.
Qqwy 12/02/19
@Qqwy seu método final de-refences - return &data[sizeofarray]IMHO ele deve apenas retornar o endereço de dados + sizeofarray mas o que eu sei,
AndersK
@ Você está correto. Obrigado por me manter afiada :-). Sim, data + sizeofarrayseria a maneira correta de escrever isso.
Qqwy 12/02/19
1

A resposta de Chris Redford também funciona para contêineres Qt (é claro). Aqui está uma adaptação (observe que eu retorno a constBegin(), respectivamente, constEnd()dos 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
fonte
0

Gostaria de elaborar algumas partes da resposta de Steve Jessop, para as quais, a princípio, não entendi. Espero que ajude.

std::beginchama a begin()função membro de qualquer maneira, portanto, se você implementar apenas uma das opções acima, os resultados deverão ser os mesmos, independentemente de qual você escolher. Esses são os mesmos resultados para loops baseados em varredura, e também o mesmo resultado para mero código mortal que não possui suas próprias regras de resolução de nomes mágicos, o que é using std::begin;seguido por uma chamada não qualificada para begin(a).

Se você implementar as funções de membro e as funções de ADL , no entanto, os loops baseados em intervalo devem chamar as funções de membro, enquanto meros mortais chamarão as funções de ADL. Melhor garantir que eles façam a mesma coisa nesse caso!


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

  • E se ...
  • Se range_expressioné uma expressão de um tipo de classe Cque possui um membro nomeado begine um membro nomeado end(independentemente do tipo ou acessibilidade desse membro), então begin_expré __range.begin() e end_expré __range.end();
  • Caso contrário, begin_expré begin(__range)e end_expré end(__range), encontrados através da pesquisa dependente de argumento (a pesquisa não-ADL não é executada).

Para loop for baseado em intervalo, as funções de membro são selecionadas primeiro.

Mas pelo

using std::begin;
begin(instance);

As funções ADL são selecionadas primeiro.


Exemplo:

#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.
//      }
}
Rick
fonte