Existe uma classe de intervalo em C ++ 11 para uso com loops for baseados em intervalo?

101

Eu me peguei escrevendo isso há pouco:

template <long int T_begin, long int T_end>
class range_class {
 public:
   class iterator {
      friend class range_class;
    public:
      long int operator *() const { return i_; }
      const iterator &operator ++() { ++i_; return *this; }
      iterator operator ++(int) { iterator copy(*this); ++i_; return copy; }

      bool operator ==(const iterator &other) const { return i_ == other.i_; }
      bool operator !=(const iterator &other) const { return i_ != other.i_; }

    protected:
      iterator(long int start) : i_ (start) { }

    private:
      unsigned long i_;
   };

   iterator begin() const { return iterator(T_begin); }
   iterator end() const { return iterator(T_end); }
};

template <long int T_begin, long int T_end>
const range_class<T_begin, T_end>
range()
{
   return range_class<T_begin, T_end>();
}

E isso me permite escrever coisas como:

for (auto i: range<0, 10>()) {
    // stuff with i
}

Agora, eu sei que o que escrevi talvez não seja o melhor código. E talvez haja uma maneira de torná-lo mais flexível e útil. Mas me parece que algo assim deveria fazer parte do padrão.

Então é isso? Foi adicionado algum tipo de nova biblioteca para iteradores em um intervalo de inteiros ou talvez um intervalo genérico de valores escalares computados?

Omniforme
fonte
17
+1. Eu gostaria de ter essas classes em meus utilitários. :-)
Nawaz
2
A propósito, qual é o ponto de escrever a rangefunção de modelo? Não acrescenta nada ao uso em que range_classé usado. Quero dizer, range<0,10>()e range_class<0,10>()parecem exatamente iguais!
Nawaz
2
@Nawaz: Sim, você está certo. Tive uma visão estranha de que poderia fazer a função lidar com a diferenciação entre o case dinâmico e estático, mas não acho que isso possa ser feito.
Onifário
2
@iammilind: Nawaz fez a mesma pergunta 35 minutos antes de você;)
Sebastian Mach
3
Para ser pedante, acho que essa implementação tem um bug, que é que você não pode usá-la para iterar em todo o intervalo inteiro. Se você inserir INT_MIN e INT_MAX como seus argumentos de modelo, INT_MAX quando incrementado irá estourar, fornecer INT_MIN e causar loops infinitos. "fim" no STL é suposto ser "um após o fim", que não cabe dentro do próprio tipo de inteiro, então não sei se isso pode realmente ser implementado de forma eficiente para o tipo de inteiro mais amplo em uma determinada plataforma. Para tipos inteiros menores, você sempre pode fazer com que use um tipo mais amplo internamente ...
Joseph Garvin

Respostas:

59

A biblioteca padrão C ++ não tem um, mas Boost.Range tem boost :: counter_range , que certamente se qualifica. Você também pode usar boost :: irange , que é um pouco mais focado no escopo.

A biblioteca range do C ++ 20 permitirá que você faça isso via view::iota(start, end).

Nicol Bolas
fonte
3
Sim, essa é definitivamente a natureza do que estou procurando. Estou feliz que Boost fez isso. Estou triste porque o comitê padrão não o incluiu por qualquer motivo. Teria sido um ótimo complemento para o recurso range-base-for.
Omnifário
Essa resposta responde melhor à minha pergunta direta e, portanto, vou escolhê-la, embora a resposta de Nawaz seja muito boa.
Omnifário
6
Ultimamente tem havido muito progresso para colocar os intervalos no padrão (N4128). Consulte github.com/ericniebler/range-v3 para obter uma proposta e implementação de referência.
Ela782 de
1
@ Ela782: ... e ainda assim parece que não o veremos no C ++ 17, certo?
einpoklum
1
@Andreas Sim, os intervalos tornaram-se um TS há algum tempo, mas não acho que haja / houve uma implementação de referência que o tornou nos principais compiladores sob o std::experimental::rangesnamespace. range-v3sempre foi uma espécie de implementação de referência, eu diria. Mas agora eu acredito que as coisas básicas da gama também foram recentemente votadas em C ++ 20, então nós iremos colocá-las em std::breve! :-)
Ela782
47

Pelo que eu sei, essa classe não existe em C ++ 11.

Enfim, tentei melhorar sua implementação. Eu o tornei não modelo , pois não vejo nenhuma vantagem em torná-lo modelo . Ao contrário, tem uma grande desvantagem: você não pode criar o intervalo em tempo de execução, pois você precisa saber os argumentos do modelo no próprio tempo de compilação.

//your version
auto x = range<m,n>(); //m and n must be known at compile time

//my version
auto x = range(m,n);  //m and n may be known at runtime as well!

Aqui está o código:

class range {
 public:
   class iterator {
      friend class range;
    public:
      long int operator *() const { return i_; }
      const iterator &operator ++() { ++i_; return *this; }
      iterator operator ++(int) { iterator copy(*this); ++i_; return copy; }

      bool operator ==(const iterator &other) const { return i_ == other.i_; }
      bool operator !=(const iterator &other) const { return i_ != other.i_; }

    protected:
      iterator(long int start) : i_ (start) { }

    private:
      unsigned long i_;
   };

   iterator begin() const { return begin_; }
   iterator end() const { return end_; }
   range(long int  begin, long int end) : begin_(begin), end_(end) {}
private:
   iterator begin_;
   iterator end_;
};

Código de teste:

int main() {
      int m, n;
      std::istringstream in("10 20");
      if ( in >> m >> n ) //using in, because std::cin cannot be used at coliru.
      {
        if ( m > n ) std::swap(m,n); 
        for (auto i : range(m,n)) 
        {
             std::cout << i << " ";
        }
      }
      else 
        std::cout <<"invalid input";
}

Resultado:

10 11 12 13 14 15 16 17 18 19

Demonstração onine .

Nawaz
fonte
3
Eu gosto disso. Pensei em uma versão sem modelo. E suponho que um bom compilador iria otimizá-lo bem no caso em que os valores realmente são constantes. Vou ter que testar isso.
Omnifário
10
@Nawaz: Eu ainda o modelaria, no tipo integral :) Eu também proporia alias iteratorpara const_iterator, iteratorderivar de std::iteratore rangeimplementar cbegine cend. Ah e ... por que iterator::operator++retorna uma referência const ?
Matthieu M.
6
@RedX: Dijkstra tem um bom artigo sobre por que a rotulagem por faixa é melhor [begin, end). @OP: +1 para o trocadilho com loops baseados em alcance que não é um trocadilho :-)
Kerrek SB
2
A vantagem da versão sem template é que os comprimentos de seus loops não precisam ser conhecidos no momento da compilação. Você poderia fazer o tipo inteiro modelado, é claro.
CashCow
2
@weeska: Essa sobrecarga deve implementar o incremento postfix v++que deve retornar o valor antes da operação de incremento ocorrer. Aconselho você a explorar a diferença entre ++ie i++onde iestá declarado int.
Nawaz
13

Eu escrevi uma biblioteca chamada rangeexatamente para o mesmo propósito, exceto que é um intervalo de tempo de execução, e a ideia no meu caso veio do Python. Eu considerei uma versão em tempo de compilação, mas na minha humilde opinião não há nenhuma vantagem real em obter a versão em tempo de compilação. Você pode encontrar a biblioteca no bitbucket, e está em Boost License: Range . É uma biblioteca de um cabeçalho, compatível com C ++ 03 e funciona perfeitamente com loops for baseados em intervalo em C ++ 11 :)

Características :

  • Um verdadeiro contêiner de acesso aleatório com todos os sinos e assobios!

  • Os intervalos podem ser comparados lexicograficamente.

  • Duas funções exist (retorna bool) e find(retorna iterador) para verificar a existência de um número.

  • A biblioteca é testada por unidade usando CATCH .

  • Exemplos de uso básico, trabalhando com contêineres padrão, trabalhando com algoritmos padrão e trabalhando com loops for baseados em alcance.

Aqui está uma introdução de um minuto . Por fim, agradeço qualquer sugestão sobre esta pequena biblioteca.

AraK
fonte
A introdução de um minuto diz que não tenho acesso ao Wiki. Você precisa tornar seu wiki público.
Nicol Bolas
@Nicol Bolas Lamento muito, agora é público :)
AraK
Obrigado por isso, é incrível. Eu sinto que mais pessoas deveriam saber sobre isso.
Rafael Kitover
5

Descobri que boost::irangeera muito mais lento do que o loop inteiro canônico. Então, decidi pela seguinte solução muito mais simples usando uma macro de pré-processador:

#define RANGE(a, b) unsigned a=0; a<b; a++

Então você pode fazer um loop assim:

for(RANGE(i, n)) {
    // code here
}

Este intervalo começa automaticamente do zero. Ele poderia ser facilmente estendido para começar a partir de um determinado número.

user2664470
fonte
7
Observe que for (RANGE(i, flag? n1: n2))produzirá resultados surpreendentes, porque você falhou em seguir uma das Regras Básicas de Macros Não-Mal, que é colocar entre parênteses todos os seus parâmetros (incluindo, neste caso, b). Sua abordagem também não fornece nenhum benefício de desempenho em relação à abordagem não macro, baseada em "objeto de alcance" (por exemplo, a resposta de Nawaz ).
Quuxplusone
2

Aqui está um formulário mais simples que está funcionando bem para mim. Existe algum risco na minha abordagem?

r_iteratoré um tipo que se comporta, tanto quanto possível, como a long int. Portanto, muitos operadores como ==e ++simplesmente passam para o long int. Eu "exponho" o int longo subjacente por meio das conversões operator long inteoperator long int &

#include <iostream>
using namespace std;

struct r_iterator {
        long int value;
        r_iterator(long int _v) : value(_v) {}
        operator long int () const { return value; }
        operator long int& ()      { return value; }
        long int operator* () const { return value; }
};
template <long int _begin, long int _end>
struct range {
        static r_iterator begin() {return _begin;}
        static r_iterator end  () {return _end;}
};
int main() {
        for(auto i: range<0,10>()) { cout << i << endl; }
        return 0;
}

( Editar: - podemos fazer os métodos de rangeestático em vez de const.)

Aaron McDaid
fonte
1

Pode ser um pouco tarde, mas acabei de ver esta pergunta e estou usando esta classe há algum tempo:

#include <iostream>
#include <utility>
#include <stdexcept>

template<typename T, bool reverse = false> struct Range final {
    struct Iterator final{
        T value;
        Iterator(const T & v) : value(v) {}
        const Iterator & operator++() { reverse ? --value : ++value; return *this; }
        bool operator!=(const Iterator & o) { return o.value != value; }
        T operator*() const { return value; }
    };
    T begin_, end_;
    Range(const T & b, const T & e)  : begin_(b), end_(e) {
        if(b > e) throw std::out_of_range("begin > end");
    }

    Iterator begin() const { return reverse ? end_ -1 : begin_; }
    Iterator end() const { return reverse ? begin_ - 1: end_; }

    Range() = delete;
    Range(const Range &) = delete;
};

using UIntRange = Range<unsigned, false>;
using RUIntRange = Range<unsigned, true>;

Uso:

int main() {
    std::cout << "Reverse : ";
    for(auto i : RUIntRange(0, 10)) std::cout << i << ' ';
    std::cout << std::endl << "Normal : ";
    for(auto i : UIntRange(0u, 10u)) std::cout << i << ' ';
    std::cout << std::endl;
}
OneOfOne
fonte
0

você já tentou usar

template <class InputIterator, class Function>
   Function for_each (InputIterator first, InputIterator last, Function f);

Na maioria das vezes se encaixa a conta.

Por exemplo

template<class T> void printInt(T i) {cout<<i<<endl;}
void test()
{
 int arr[] = {1,5,7};
 vector v(arr,arr+3);

 for_each(v.begin(),v.end(),printInt);

}

Observe que printInt pode ser substituído por um lambda em C ++ 0x. Além disso, mais uma pequena variação desse uso pode ser (estritamente para random_iterator)

 for_each(v.begin()+5,v.begin()+10,printInt);

Para iterador Fwd apenas

 for_each(advance(v.begin(),5),advance(v.begin(),10),printInt);
Ajeet Ganga
fonte
Como você usaria isso? Suponho que você usaria um lambda para a função, mas não tenho certeza.
Onifário
1
Diria, mas você terá que aceitar a resposta se achar que é a maneira certa de usá-la. : P Brincadeira. Já postou o exemplo.
Ajeet Ganga
Você pode usar um lambda aqui, então auto range = myMultiMap.equal_range (key); for_each (range.first, range.second, [&] (decltype (* range.first) const & item) {// code vai here});
CashCow
-3

Você pode gerar facilmente uma sequência crescente em C ++ 11 usando std :: iota ():

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

template<typename T>
std::vector<T> range(T start, T end)
{
  std::vector<T> r(end+1-start, T(0));
  std::iota(r.begin(), r.end(), T(start));//increasing sequence
  return r;
}

int main(int argc, const char * argv[])
{
  for(auto i:range<int>(-3,5))
    std::cout<<i<<std::endl;

  return 0;
}
escorpião azul
fonte
3
A rangeclasse deve modelar o intervalo. No entanto, você está literalmente construindo. Isso é um desperdício de memória e acessos à memória. A solução é altamente redundante, porque o vetor não contém nenhuma informação real, exceto para o número de elementos e o valor do primeiro elemento (se existir).
not-a-user
Sim, isso é muito ineficiente.
Onifário