Jak sprawić, by mój typ niestandardowy działał z „opartym na zakresie dla pętli”?

252

Jak wiele osób próbuję obecnie różnych funkcji, które oferuje C ++ 11. Jednym z moich ulubionych jest „oparte na zakresie pętle”.

Rozumiem, że:

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

Jest równa:

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

A to begin()po prostu zwraca a.begin()standardowe pojemniki.

Ale co jeśli chcę, aby mój niestandardowy typ „oparty na zakresie dla pętli” był widoczny ?

Czy powinienem się po prostu specjalizować begin()i end()?

Jeśli mój niestandardowy typ należy do przestrzeni nazw xml, czy powinienem zdefiniować xml::begin()czy std::begin()?

Krótko mówiąc, jakie są wytyczne, aby to zrobić?

ereOn
źródło
Jest to możliwe poprzez zdefiniowanie członka begin/endlub przyjaciela, statyczne lub wolne begin/end. Uważaj tylko, w której przestrzeni nazw umieścisz darmową funkcję: stackoverflow.com/questions/28242073/...
alfC
Może ktoś proszę pisać odpowiedź na przykładzie szeregu wartości pływak, który nie jest pojemnik: for( auto x : range<float>(0,TWO_PI, 0.1F) ) { ... }. Jestem ciekawy, jak omijasz fakt, że `operator! = ()` `Jest trudny do zdefiniowania. A co *__beginw tym przypadku z dereferencing ( )? Myślę, że będzie to wielki wkład, jeśli ktoś pokazał nam, jak to jest zrobione!
BitTickler,

Odpowiedzi:

183

Standard został zmieniony, ponieważ pytanie (i większość odpowiedzi) zostało zamieszczone w rezolucji tego raportu o defektach .

Sposób, aby for(:)pętla działała na twoim typie, Xjest teraz jednym z dwóch sposobów:

  • Tworzenie elementu X::begin()i X::end()że coś powrotny, który działa jak iteratora

  • Stwórz darmową funkcję begin(X&)i end(X&)że coś powrotny, który działa jak iteratora, w tej samej przestrzeni nazw jako typ X

I podobne dla constodmian. Będzie to działać zarówno na kompilatorach, które implementują zmiany raportu defektów, jak i na kompilatorach, które tego nie robią.

Zwrócone obiekty nie muszą tak naprawdę być iteratorami. for(:)Pętli, w przeciwieństwie do większości części C ++ standardowego jest określony rozszerzyć na coś równoważne :

for( range_declaration : range_expression )

staje się:

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

gdzie zmienne zaczynające się od __są tylko dla prezentacji begin_expri end_exprsą magią, która wywołuje begin/ end

Wymagania dotyczące ++początkowej / końcowej wartości zwracanej są proste: należy przeciążać wstępnie , upewnić się, że wyrażenia inicjujące są poprawne, binarne !=, których można użyć w kontekście logicznym, jednoargumentowe, *które zwraca coś, co można przypisać-zainicjować range_declaration, i ujawnić publiczny burzyciel.

Robienie tego w sposób niezgodny z iteratorem jest prawdopodobnie złym pomysłem, ponieważ przyszłe iteracje C ++ mogą być względnie nonszalanckie jeśli chodzi o złamanie kodu.

Nawiasem mówiąc, istnieje uzasadnione prawdopodobieństwo, że przyszła zmiana standardu pozwoli end_exprna zwrot innego rodzaju niż begin_expr. Jest to przydatne, ponieważ pozwala na ocenę „leniwego końca” (jak wykrywanie zerowego zakończenia), którą łatwo zoptymalizować, aby była tak wydajna jak odręcznie napisana pętla C, i inne podobne zalety.


¹ Zauważ, że for(:)pętle przechowują dowolne pliki tymczasowe w auto&&zmiennej i przekazują je jako wartość. Nie możesz wykryć, czy iterujesz po tymczasowej (lub innej wartości); takie przeciążenie nie będzie wywoływane przez for(:)pętlę. Patrz [stmt.ranged] 1.2-1.3 z n4527.

² albo wywołać begin/ endlub innej metody ADL tylko odnośników wolnej funkcji begin/ end, lub magicznych wsparcia tablicy stylu C. Zauważ, że std::beginnie jest wywoływany, chyba że range_expressionzwraca obiekt typu namespace stdlub zależny od niego.


W wyrażenie dla zakresu zostało zaktualizowane

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

z typami __begini __endzostały oddzielone.

To pozwala, aby iterator końcowy nie był tego samego typu co start. Twój typ iteratora końcowego może być „wartownikiem”, który obsługuje tylko !=typ iteratora początkowego.

Praktycznym przykładem tego, dlaczego jest to przydatne, jest to, że twój iterator końcowy może przeczytać „sprawdź, char*czy wskazuje, że '0'”, gdy ==jest to char*. Dzięki temu wyrażenie w zakresie C ++ może generować optymalny kod podczas iteracji w char*buforze zakończonym zerem.

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

przykład na żywo w kompilatorze bez pełnej obsługi C ++ 17; forpętla rozwinięta ręcznie.

Jak - Adam Nevraumont
źródło
Jeśli oparte na zakresie używa innego mechanizmu wyszukiwania, być może możliwe jest ustawienie tego w oparciu o zakres dla innej pary funkcji begini endfunkcji niż jest to dostępne w normalnym kodzie. Być może mogliby być bardzo wyspecjalizowani w zachowaniu się inaczej (tzn. Szybciej, ignorując argument końcowy, aby uzyskać maksymalną optymalizację możliwą). Ale nie jestem wystarczająco dobry w przestrzeniach nazw, aby mieć pewność, jak to zrobić.
Aaron McDaid,
@AaronMcDaid nie bardzo praktyczne. Z łatwością uzyskałbyś zaskakujące wyniki, ponieważ niektóre sposoby wywoływania początku / końca kończyłyby się na podstawie zakresu dla początku / końca, a inne nie. Nieszkodliwe zmiany (od strony klienta) spowodowałyby zmiany w zachowaniu.
Yakk - Adam Nevraumont
1
Nie trzeba begin(X&&). Tymczasowe jest zawieszone w powietrzu auto&&w zakresie dla i beginzawsze jest wywoływane za pomocą lvalue ( __range).
TC
2
Ta odpowiedź naprawdę skorzystałaby na przykładzie szablonu, który można skopiować i wdrożyć.
Tomáš Zato - Przywróć Monikę
Wolę położyć nacisk na właściwości typu iteratora (*, ++,! =). Poproszę cię o ponowne sformułowanie tej odpowiedzi, aby specyfikacje typu iteratora były pogrubione.
Red.Wave
62

Piszę odpowiedź, ponieważ niektórzy ludzie mogą być bardziej zadowoleni z prostego przykładu z życia bez STL.

Z jakiegoś powodu mam własną prostą implementację tablicy danych i chciałem użyć zakresu opartego na pętli. Oto moje rozwiązanie:

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

Następnie przykład użycia:

PodArray<char> array;
// fill up array in some way
for(auto& c : array)
  printf("char: %c\n", c);
csjpeter
źródło
2
Przykład ma metody begin () i end (), a także podstawową (łatwą do zrozumienia) przykładową klasę iteratora, którą można łatwo dostosować do dowolnego niestandardowego typu kontenera. Porównanie std :: array <> i każdej możliwej alternatywnej implementacji to inne pytanie i moim zdaniem nie ma to nic wspólnego z pętlą opartą na zakresie.
csjpeter
To bardzo zwięzła i praktyczna odpowiedź! Właśnie tego szukałem! Dzięki!
Zac Taylor
1
Czy lepiej byłoby usunąć const kwalifikator zwrotu dla const DataType& operator*()i pozwolić użytkownikowi wybrać opcję const auto&lub auto&? W każdym razie dzięki, świetna odpowiedź;)
Rick
53

Odpowiednią częścią normy jest 6.5.4 / 1:

jeśli _RangeT jest typem klasy, identyfikatory niekwalifikowane zaczynają się i kończą w zakresie klasy _RangeT, tak jak w przypadku wyszukiwania dostępu członków klasy (3.4.5), i jeśli jedna (lub obie) znajdzie przynajmniej jedną deklarację, zacznij - wyrażenie końcówki wyrażenie jest __range.begin()i __range.end(), odpowiednio;

- w przeciwnym razie, zaczynają lista_wyrażeń_sortowania i końcowe wyrażenie jest begin(__range)i end(__range), odpowiednio, w których rozpoczyna się i kończy się wzrok z odnośnika argumentu zależne (3.4.2). Na potrzeby tego wyszukiwania nazw przestrzeń nazw std jest powiązaną przestrzenią nazw.

Możesz więc wykonać dowolną z następujących czynności:

  • definiować begini endskładać funkcje
  • zdefiniuj begini endzwolnij funkcje, które zostaną znalezione przez ADL (wersja uproszczona: umieść je w tej samej przestrzeni nazw co klasa)
  • specjalizować się std::beginistd::end

std::begini tak wywołuje funkcję begin()członka, więc jeśli zaimplementujesz tylko jeden z powyższych, wyniki powinny być takie same bez względu na to, który wybierzesz. To te same wyniki dla pętli opartych na dystansie, a także ten sam wynik dla zwykłego śmiertelnego kodu, który nie ma własnych reguł rozpoznawania magicznych nazw, więc using std::begin;następuje po nim niewykwalifikowane wywołanie begin(a).

W przypadku zastosowania funkcji członków i funkcji ADL, choć wtedy piecyk oparciu o pętle powinny wywoływać funkcje członków, podczas gdy zwykli śmiertelnicy będą wywoływać funkcje ADL. Najlepiej upewnij się, że robią to samo w takim przypadku!

Jeśli to, co piszesz, implementuje interfejs kontenera, to będzie już miał begin()i end()funkcje składowe, co powinno wystarczyć. Jeśli jest to zakres, który nie jest kontenerem (co byłoby dobrym pomysłem, jeśli jest niezmienny lub jeśli nie znasz rozmiaru z przodu), możesz wybrać.

Z opcjami rozplanować, notatkę, która nie musi przeciążenia std::begin(). Możesz specjalizować się w standardowych szablonach dla typu zdefiniowanego przez użytkownika, ale oprócz tego dodawanie definicji do przestrzeni nazw std jest nieokreślonym zachowaniem. Ale w każdym razie specjalizacja standardowych funkcji jest złym wyborem, choćby dlatego, że brak częściowej specjalizacji funkcji oznacza, że ​​możesz to zrobić tylko dla jednej klasy, a nie dla szablonu klasy.

Steve Jessop
źródło
Czy nie istnieją pewne wymagania, które iterator bardzo spełnia? tj. być ForwardIteratorem lub czymś podobnym.
Pubby
2
@Pubby: Patrząc na 6.5.4, myślę, że InputIterator jest wystarczający. Ale faktycznie nie sądzę typ zwrócony ma być w ogóle za iterator zakres oparte na. Instrukcja jest zdefiniowana w standardzie przez to, co jest równoważne, więc wystarczy zaimplementować tylko wyrażenia użyte w kodzie w standardzie: operatory !=, prefiks ++i unary *. Prawdopodobnie nierozsądne jest wdrażanie funkcji członkowskich begin()i end()funkcji ADL, które zwracają wszystko inne niż iterator, ale myślę, że jest to legalne. std::beginMyślę, że specjalizacją w zwróceniu nie-iteratora jest UB.
Steve Jessop,
Czy na pewno nie możesz przeciążać std :: begin? Pytam, ponieważ standardowa biblioteka robi to sama w kilku przypadkach.
ThreeBit
@ThreeBit: tak, jestem pewien. Reguły dla standardowych implementacji bibliotek różnią się od reguł dla programów.
Steve Jessop,
3
To musi być zaktualizowane dla open-std.org/jtc1/sc22/wg21/docs/cwg_defects.html#1442 .
TC
34

Czy powinienem po prostu specjalizować start () i end ()?

O ile mi wiadomo, to wystarczy. Musisz także upewnić się, że zwiększenie wskaźnika będzie miało miejsce od początku do końca.

Następny przykład (brakuje stałej wersji początku i końca) kompiluje się i działa dobrze.

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

Oto kolejny przykład z funkcjami początku / końca. Oni muszą być w tej samej przestrzeni nazw, jako klasy, z powodu 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Јовић
źródło
1
@ereOn W tej samej przestrzeni nazw, w której zdefiniowano klasę. Zobacz drugi przykład
BЈовић
2
Gratulacje również :) Warto wspomnieć o pojęciu Argument Dependent Lookup (ADL) lub Koenig Lookup w drugim przykładzie (aby wyjaśnić, dlaczego darmowa funkcja powinna znajdować się w tej samej przestrzeni nazw, co klasa, na której działa).
Matthieu M.,
1
@ereOn: właściwie nie. ADL polega na rozszerzeniu zakresu na wyszukiwanie, aby automatycznie obejmował przestrzenie nazw, do których należą argumenty. Jest dobry artykuł ACCU na temat rozwiązywania problemów z przeciążeniem, który niestety pomija część wyszukiwania nazwy. Wyszukiwanie nazw obejmuje zbieranie funkcji kandydatów, zaczynasz od spojrzenia w bieżącym zakresie + zakresach argumentów. Jeśli nie zostanie znaleziona żadna nazwa pasująca, przejdź do zakresu nadrzędnego bieżącego zakresu i przeszukuj ponownie ..., aż osiągniesz zakres globalny.
Matthieu M.,
1
@ BЈовић przepraszam, ale z jakiego powodu w funkcji end () zwracasz niebezpieczny wskaźnik? Wiem, że to działa, ale chcę zrozumieć logikę tego. Koniec tablicy to v [9], dlaczego miałbyś zwracać v [10]?
gedamial
1
@gedamial Zgadzam się. Myślę, że tak powinno być return v + 10. &v[10]dereferencje lokalizacji pamięci tuż obok tablicy.
Millie Smith,
16

Jeśli chcesz poprzeć iterację klasy bezpośrednio za pomocą jej std::vectorlub std::mapczłonka, oto kod do tego:

#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
źródło
2
Warto wspomnieć, że const_iteratormogą być dostępne również w auto(C ++ 11) -Kompatybilny sposób poprzez cbegin, cenditp
underscore_d
2

Tutaj udostępniam najprostszy przykład tworzenia niestandardowego typu, który będzie działał z „ opartą na zakresie dla pętli ”:

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

Mam nadzieję, że będzie to pomocne dla początkującego programisty takiego jak ja: p :)
Dziękuję.

RajibTheKing
źródło
dlaczego nie przydzielić jednego dodatkowego elementu, aby uniknąć dereferencji nieprawidłowej pamięci w metodzie końcowej?
AndersK
@Anders ponieważ prawie wszystkie końcowe iteratorami wskazują na po zakończeniu ich zawierającego strukturę. Sama end()funkcja oczywiście nie wyklucza niewłaściwego miejsca w pamięci, ponieważ zajmuje tylko „adres” tego miejsca w pamięci. Dodanie dodatkowego elementu oznaczałoby, że potrzebujesz więcej pamięci i użycie your_iterator::end()w jakikolwiek sposób, który odrzuciłby tę wartość, i tak nie działałoby z innymi iteratorami, ponieważ są one zbudowane w ten sam sposób.
Qqwy,
@ Qqwy jego metoda końcowa jest cofnięta - return &data[sizeofarray]IMHO powinno po prostu zwrócić dane adresowe + sizeofarray, ale co wiem,
AndersK
@Anders Masz rację. Dzięki za trzymanie mnie ostro :-). Tak, data + sizeofarraybyłby to właściwy sposób na napisanie tego.
Qqwy
1

Odpowiedź Chrisa Redforda działa również dla kontenerów Qt (oczywiście). Oto adaptacja (zauważ, że zwracam constBegin()odpowiednio a constEnd()z metod 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(); }
};
użytkownik2366975
źródło
0

Chciałbym rozwinąć niektóre części odpowiedzi @Steve Jessop, na które początkowo nie rozumiałem. Mam nadzieję, że to pomoże.

std::begini tak wywołuje funkcję begin()członka, więc jeśli zaimplementujesz tylko jeden z powyższych, wyniki powinny być takie same bez względu na to, który wybierzesz. To te same wyniki dla pętli opartych na dystansie, a także ten sam wynik dla zwykłego śmiertelnego kodu, który nie ma własnych reguł rozpoznawania magicznych nazw, więc using std::begin;następuje po nim niewykwalifikowane wywołanie begin(a).

Jeśli realizować funkcje składowe i funkcje ADL , choć wtedy piecyk oparciu o pętle powinny wywoływać funkcje członków, podczas gdy zwykli śmiertelnicy będą wywoływać funkcje ADL. Najlepiej upewnij się, że robią to samo w takim przypadku!


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

  • Jeśli ...
  • Jeśli range_expressionjest wyrażeniem typu klasy, Cktóry ma zarówno nazwanego członka, jak begini członka nazwanego end(niezależnie od typu lub dostępności takiego członka), to begin_exprjest __range.begin() i end_exprjest __range.end();
  • W przeciwnym razie begin_exprjest begin(__range)i end_exprjest end(__range), które można znaleźć poprzez wyszukiwanie zależne od argumentów (wyszukiwanie inne niż ADL nie jest wykonywane).

W przypadku pętli opartej na zakresie najpierw wybiera się funkcje składowe.

Ale dla

using std::begin;
begin(instance);

Funkcje ADL są wybierane jako pierwsze.


Przykład:

#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.
//      }
}
Stóg
źródło