2014-02-26 20 views
11

Die C++ 11 Algorithmen std::is_sorted und std::is_sorted_until erfordern beide ForwardIterator s. Die Boost.Range-Version boost::is_sorted benötigt jedoch nur SinglePassRange s, was InputIterator s entspricht. Insbesondere ist es die Delegierten zu einem Iterator-basierte Implementierung wie folgt aus:Warum benötigt Boost.Range is_sorted keine Iteratoren?

template<class Iterator, class Comp> 
inline Iterator is_sorted_until (Iterator first, Iterator last, Comp c) { 
    if (first == last) 
    return last; 

    Iterator it = first; ++it; 

    for (; it != last; first = it, ++it) 
    if (c(*it, *first)) 
     return it; 

    return it; 
} 

Hier sehen wir eine *first Iterator dereferenzieren, dass nach der Erhöhung ++it Iterator passiert. Dies bedeutet, dass IteratorForwardIterator als erforderliche Kategorie haben sollte. Warum? Da die Norm sagt so in

24.2.3 Eingang Iteratoren [input.iterators]/p2 (siehe Tabelle 107 mit der Linie über ++r)

Beitrag: alle Kopien von dem vorherigen Wert von r sind nicht mehr erforderlich entweder dereferenzierbar sein oder in der Domäne von == sein.

Hinweis: dies ist nicht als „ein Beweis durch einzelnes Beispiel“ gedacht, aber es scheint, dass jeder Vergleich basierter Algorithmus (zB adjacent_find) würde notwendigerweise nach vorne Iteratoren erfordern, um einen Vergleich machen zu können, zwischen zwei Iteratoren.

Frage: warum nicht die Boost.Range Version von is_sorted erfordert das stärkere Konzept der ForwardRange (und ForwardIterator für seine Low-Level-Routinen), die von std::is_sorted erforderlich ist? Ist es ein Fehler in Boost.Range?

+0

In der Tat scheint dies verdächtig. –

+0

@MatthieuM. Ich frage mich jedoch, ob man es für Input-Iteratoren funktionieren lassen könnte, indem man den zuletzt gelesenen Wert zwischenspeichert. – TemplateRex

+1

Es würde dann eine Anforderung an diesen Wert auferlegen: es müsste kopierbar sein. –

Antwort

2

Es sieht so aus, als ob die Iterator-Versionen in boost.algorithm korrekt ForwardIterators erfordern. Und ob Sie es glauben oder nicht, there are also range-based versions in boost.algorithm. Code Duplikation von seiner besten Seite. Die Dokumentation ist hinter der Quelle nach Ticket #9367, Changeset #86741, die den Rest der Dokumentation korrigiert, um anzugeben, dass alle Varianten der Sortierprüfalgorithmen ForwardIterators erfordern.

würde ich die Implementierungen in <boost/algorithm/cxx11/is_sorted.hpp> über diejenigen in <boost/range/algorithm_ext/is_sorted.hpp> bevorzugen, die Bit-Fäulnis zu sein scheinen seit 2010

EDIT: Graben herum, scheint es, dass die Boost.Range Implementierungen hat erfordern ForwardIterator, aber this commit broke them in 2010?!? .

+0

+1 und akzeptiert.Danke, dass du Boost den ganzen Dreck aufgegeilt hast. Es ist ein Durcheinander, es schön zu sagen. – TemplateRex

Verwandte Themen