"end()" Iterator für Back Inserter?

Question

Gibt es für Iteratoren wie die, die von std::back_inserter() zurückgegeben werden, etwas, das als "End" Iterator verwendet werden kann?

Dies scheint ein wenig zunächst unsinnig, aber ich habe eine API, die:

template<typename InputIterator, typename OutputIterator> 
void foo(
    InputIterator input_begin, 
    InputIterator input_end, 
    OutputIterator output_begin, 
    OutputIterator output_end 
); 

foo führt eine Operation an der Eingangssequenz, um eine Ausgangssequenz zu erzeugen. (Wer ist Länge ist auf foo bekannt, aber möglicherweise nicht an die Eingangssequenz der Länge gleich sein.)

Die Einnahme des output_end Parameter der ungerade Teil ist: std::copy tut dies nicht, zum Beispiel, und vorausgesetzt, dass Sie‘ Ich werde es nicht Müll übergeben. foo tut es, um Reichweitenprüfung zur Verfügung zu stellen: Wenn Sie einen Bereich zu klein übergeben, löst es eine Ausnahme im Namen der defensiven Programmierung aus. (Anstatt potentiell zufällige Bits im Speicher zu überschreiben.)

Nun sage ich, dass ich foo einen Back-Inserter übergeben möchte, insbesondere einen aus einem std::vector, der keine Begrenzung außerhalb von Speicherbeschränkungen hat. Ich brauche immer noch einen "Ende" Iterator - in diesem Fall etwas, das niemals gleich wird. (Oder, wenn ich eine std::vector aber mit einer Beschränkung auf Länge hätte, vielleicht könnte es manchmal gleich vergleichen?)

Wie gehe ich dabei vor? Ich habe die Möglichkeit, foo API zu ändern - ist es besser, nicht den Bereich zu überprüfen, und stattdessen eine alternative Möglichkeit, den erforderlichen Ausgabebereich zu erhalten? (Was sowieso für Raw-Arrays benötigt wird, aber nicht für Back-Inserter in einen Vektor benötigt wird.) Dies scheint weniger robust zu sein, aber ich bemühe mich, das "Robuste" (oben) zu arbeiten.

Answer 1

Wenn foo überprüft, um sicherzustellen, dass distance(output_begin, output_end) ausreichend groß ist, um die Ergebnisse zu enthalten, was könnten Sie als "Ende" Iterator verwenden? A back_inserter fügt Elemente zum Ende hinzu; Die distance zwischen der Stelle, an der eine back_inserter Elemente hinzugefügt und das Ende der Sequenz ist per Definition 0.

Eine foo mit der std::copy -ähnliche Signatur foo(InIt, InIt, OutIt) ist meiner Meinung nach Ihre beste Option. Es ist nicht wirklich "nicht robust". Für die meisten Algorithmen möchten Sie diese Art von Bereichsüberprüfung nur in Debug-Builds aus Leistungsgründen durchführen, und eine anständige Standardbibliotheksimplementierung (wie die Visual C++ - Standardbibliothek) wird bereits eine Vielzahl von Bereichsüberprüfungen in Debug-Builds bereitstellen.

Alternativ können Sie auch eine back_inserting_foo(InIt, InIt, Container) erstellen, obwohl das Erstellen eines Sonderfalls für diese Funktion etwas ungewöhnlich wäre und Benutzern der Funktion eine größere Last aufbürdet, welche Überladung sie für verschiedene Arten von Iteratoren benötigen.

Answer 2

Sie vermeiden, indem Sie die Sicherheitsprüfung foo() ‚s API zu ändern, wie Sie gehen, indem Sie die curr_output_iter != output_end vor jedem Elemente ausgeschrieben wird (siehe unten), statt einmal zu Beginn mit einem distance() Scheck als James McNellis suggests.

Dazu müssen Sie Ihren eigenen "Iterator-Adapter" schreiben, um einen "erweiterten" Ausgabe-Iterator bereitzustellen, der prüfen kann, ob er am Ende seines gültigen Bereichs ist. Dann würden Sie zu Recht die Vorlage typenames von OutputIterator zu SafeOutputIterator ändern - obwohl dies nur als Dokumentation dient, da es etwas ist, das in C++ nicht durchgesetzt werden kann.Wir unterscheiden zwischen "begrenzten" und "unbegrenzten" Iteratorpaaren: für letztere werden keine zwei Iteratoren jemals gleich vergleichen, und in der Tat wird der zweite Iterator niemals für irgendetwas außer seinem Typ benötigt werden.

/* Metafunction for determining whether the range has a fixed endpoint. 
* Assume all iterators are bounded except for OutputIterators. */ 
template <typename Tag> 
struct helper { 
    static bool value = true; 
}; 

template <> 
struct helper<output_iterator_tag> { 
    static bool value = false; 
}; 

template <typename It> 
struct is_bounded { 
    static bool value = helper<typename iterator_traits<It>::iterator_category>::value; 
}; 

/* Wraps an output iterator. */ 
template<typename It, bool BOUNDED = is_bounded<It>::value> 
class safe_output_iterator { 
    typedef typename iterator_traits<It>::value_type value_type; 

public: 
    explicit safe_output_iterator(It iter, size_t limit = 0) : iter_(iter), limit_(limit) {} 

    safe_output_iterator& operator++() { /* Preinc */ 
     ++iter_; 
     return *this; 
    } 

    safe_output_iterator operator++(int) { /* Postinc */ 
     safe_output_iterator temp(*this); 
     ++iter_; 
     return temp; 
    } 

    /* Trick: Deferencing returns the same object, so that operator=() works */ 
    safe_output_iterator& operator*() { 
     return *this; 
    } 

    /* Will be called despite "dereferencing" this iterator object */ 
    safe_output_iterator& operator=() { 
     /* Insert check for limit == 0 here if you want */ 
     --limit_; 
     return *_iter; 
    } 

    /* Addition to the OutputIterator concept. */ 
    bool operator==(safe_output_iterator const& x) { 
     return BOUNDED && limit_ == x.limit_; 
    } 

    bool operator!=(safe_output_iterator const& x) { 
     return !(*this == x); 
    } 

private: 
    It iter_; 
    size_t limit_; 
}; 

/* Helper function templates to avoid typing out long typenames */ 

/* Handle iterators */ 
template <typename It> 
safe_output_iterator<It> soi_begin(It it, size_t limit = 0) { 
    return safe_output_iterator<It>(it, limit); 
} 

template <typename It> 
safe_output_iterator<It> soi_end(It it, size_t limit = 0) { 
    return safe_output_iterator<It>(it, limit); 
} 

/* Handle STL containers like vector and list */ 
template <typename C> 
safe_output_iterator<It> soi_begin_cont(C cont) { 
    return safe_output_iterator<typename C::iterator>(cont.begin(), cont.size()); 
} 

template <typename C> 
safe_output_iterator<It> soi_end_cont(C cont) { 
    /* Actually the iterator supplied (here cont.end()) is unimportant... */ 
    return safe_output_iterator<typename C::iterator>(cont.end()); 
} 

können Sie jetzt Code schreiben wie:

vector<int> u(10, 42), v(ENOUGH_SPACE), w, x(ENOUGH_SPACE); 

// Explicit iterator pair; bounded 
foo(u.begin(), u.end(), soi_begin(v.begin(), ENOUGH_SPACE), soi_end(v)); 

// Explicit iterator pair; unbounded (2nd iterator ignored, but we need the type) 
foo(u.begin(), u.end(), soi_begin(w.back_inserter()), soi_end(w.back_inserter())); 

// Use whole container 
foo(u.begin(), u.end(), soi_begin_cont(x), soi_end_cont(x)); 

Sie entweder foo() Check curr_output_iter != output_end vor jedem Schreibvorgang durch *curr_output_iter oder alternativ legen Sie die Check-in safe_output_iterator::operator=() haben kann. Letzteres scheint vorzuziehen, da Sie dann nicht vergessen können, die Prüfung jedes Mal durchzuführen, wenn ein Paar safe_output_iterators an irgendeinen beliebigen Algorithmus übergeben wird (vermutlich ähnelt dies der Funktionsweise von Debug-Versionen der STL). Sie könnten auch Überladungen von soi_begin_cont() und soi_end_cont() für Arrays fester Größe schreiben.

All dies wäre viel weniger umständlich, wenn ranges von STL-Algorithmen anstelle von Iteratorpaaren verwendet würde - so könnte beispielsweise eine einzelne Funktionsvorlage einen geeigneten Bereich zurückgeben, der ein ganzes Array überspannt.

Answer 3

Wie ich in einem Kommentar zu j_random_hacker Antwort erwähnt, wenn Sie der Algorithmus so modifizieren, dass die an sie übergeben Iteratoren unterschiedlicher Art sein können, beispielsweise

template <typename InIt1, InIt2, OutIt1, OutIt2> 
void foo(InIt1 in_begin, InIt2 in_end, OutIt1 out_begin, OutIt2 out_end) { } 

dann kann man sehr leicht eine back_inserter_end schreiben Klasse testen gegen:

class back_inserter_end 
    : std::iterator<std::output_iterator_tag, void> 
{ }; 

bool operator==(back_inserter_end, back_inserter_end) { return true; } 
bool operator!=(back_inserter_end, back_inserter_end) { return false; } 

template <typename Container> 
bool operator==(const back_insert_iterator<Container>&, back_inserter_end) { 
    return false; 
} 

template <typename Container> 
bool operator==(back_inserter_end, const back_insert_iterator<Container>&) { 
    return false; 
} 

template <typename Container> 
bool operator!=(const back_insert_iterator<Container>&, back_inserter_end) { 
    return true; 
} 

template <typename Container> 
bool operator!=(back_inserter_end, const back_insert_iterator<Container>&) { 
    return true; 
} 

Sie können dann Ihren "sicheren" Algorithmus nennen:

foo(it, it, std::back_inserter(v), back_inserter_end()); 

Innerhalb Ihres "sicheren" Algorithmus können Sie testen, ob out_it == out_end vor der Verwendung out_it; Da out_it ein back_insert_iterator ist, gibt dieser Test immer false zurück (was das gewünschte Verhalten ist).