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 Iterator
ForwardIterator
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?
In der Tat scheint dies verdächtig. –
@MatthieuM. Ich frage mich jedoch, ob man es für Input-Iteratoren funktionieren lassen könnte, indem man den zuletzt gelesenen Wert zwischenspeichert. – TemplateRex
Es würde dann eine Anforderung an diesen Wert auferlegen: es müsste kopierbar sein. –