Ist es möglich, standardkonforme Direktzugriffs (oder zumindest Vorwärts-) Integer-Iteratoren zu schreiben?

Question

Angenommen, wir haben die Funktion f, die eine Ganzzahl annimmt und einen monoton ansteigenden Wert zurückgibt. Wir wollen minimal x so finden, dass f(x) >= C. Der Einfachheit halber sagen wir, dass die Antwort im Bereich [l;r) liegt. Offensichtlich können wir unsere eigene Implementierung der binären Suche schreiben, aber wir wollen die existierende verwenden (std::patition_point).

So naive Implementierung, wird (wahrscheinlich) Arbeit:

// f; 
std::vector<int> v(r - l); 
std::iota(v.begin(), v.end(), l); 
answer = l + partition_point(v.begin(), v.end(), [&](int x) { 
    return f(x) <= C; 
}) - v.begin(); 

Das offensichtliche Problem ist, dass wir alle Zahlen speichern haben, die viel Speicher braucht und nimmt auch Zeit, um das Array zu füllen

nächste logische Idee ist integer zu Iteratoren auf diese Weise wickeln:

struct IntIterator: std::iterator<std::random_access_iterator_tag, int> { 
    int current; 
    IntIterator(int i) : current(i) {} 
    int operator*() const { return current; } 
    IntIterator& operator++() { ++current; return *this; } 
    IntIterator& operator+=(size_t n) { current += (int)n; return *this; } 
    IntIterator operator+(size_t n) const { return current+(int)n; } 
    size_t operator-(IntIterator that) const { return size_t(current - that.current); } 
    // others operators to conform 
}; 

answer = partition_point(IntIterator{l}, IntIterator{r}, [&](int x) { 
    return f(x) <= C; 
}); 

Dies wird mit meinem Compiler (Standardbibliothek) arbeitet, ist aber nicht rand konform om Zugriff Iterator, weil

• Operator * sollte std::iterator_traits<IntIterator>::reference zurückgeben.

• wenn wir std::iterator_traits<IntIterator>::reference ändern (zB durch Template-Parameter zu std::iterator Ändern) in int es wird nicht Anforderung von vorn Iterator erfüllen:

  wenn X ein veränderliches Iterator ist, reference ist ein Verweis auf T; wenn X ein const iterator ist, reference ist eine Referenz T const,

• wenn wir Rückgabetyp operator*-[const ]T& ändern wird es scheitern weitere Forderung der Vorwärts Iterator zu erfüllen

  Wenn ein und b sind beide dereferenzierbar, dann a == b wenn und nur wenn *a und *b an das gleiche Objekt gebunden sind.

So verstehe ich nicht, wie man es machen konforme und Frage stellen, ob es möglich ist.

Answer 1

Die Iteratoren teilen sich einen Zeiger auf eine Cache-Map.

Die Cachemap bildet den Index auf (count, value) ab, wobei count die Anzahl der Iteratoren in diesem Index angibt.

Der Iterator erinnert sich, wenn er * aufgerufen hat.

Wenn * aufgerufen wird, wird der Wert ausgefüllt, wenn er fehlt. Unabhängig davon wird count inkrementiert, dann wird ein Verweis auf value zurückgegeben.

Wenn der Iterator zerstört wird oder der Iterator sich verschiebt (++), wird der Zähler dekrementiert, wenn * aufgerufen wurde.

Wenn count auf Null dekrementiert wird, wird der Eintrag entfernt.

Dadurch werden die Werte für alle gültigen Iteratoren desselben Indexes während ihrer gemeinsamen überlappenden Lebensdauer zwischengespeichert.

Answer 2

wenn X ein veränderliches Iterator ist, reference ist ein Verweis auf T; wenn X ein const iterator ist, ist reference ein Verweis auf const T

Ich denke, dass Sie nicht nehmen sollten zu ernst diese Anforderung. Die Standardbibliothek enthält einen Container (std::vector<bool>), dessen const_iterator und iterator diese Anforderung nicht erfüllen. Ich weiß, dass es a point of view ist, dass "std::vector<bool> ist kein Container", aber ich bin eher geneigt, die zitierte Anforderung als zu restriktiv zu sehen, als mit dieser Sichtweise völlig zuzustimmen.