C ++ Iterators: best practice per rappresentare la fine dell'intervallo - Last or Beyond-last?

Segui lo standard - la fine è l'iteratore che supera quello che vuoi. Ciò ti consente di utilizzare tutti gli algoritmi e i contenitori standard senza problemi.

Significa anche che i tuoi utenti saranno in grado di scrivere il codice che hanno sempre (es. for (x=startIt; x != endIt; x++) e questo funzionerà come previsto.

Se si modifica questo comportamento e si imposta l'ultimo iteratore sull'ultimo elemento, tutto ciò che viene fuori dalla finestra e si potrebbe anche usare una nomenclatura diversa da quella degli iteratori mentre si sta effettivamente cambiando il modo in cui tutti si aspetteranno che funzionino .

Con la tua convenzione:

• ogni funzione nella libreria deve essere usata cambiando il limite superiore dell'intervallo e può essere abbastanza soggetto a errori
• non è facile rappresentare sequenze vuote (questo era l'argomento di Dijkstra in Perché La numerazione dovrebbe iniziare a zero ).
• puoi facilmente incorrere in errori off-by-one (ad es. quando prendi una partizione di una raccolta).

Devi rimanere con intervalli semichiusi.

Hai scritto:

The std convention is to have the last iterator point beyond the last element

Penso di poter aiutare il tuo modello mentale dandoti due piccole risposte (una sezione ciascuno).

• Non pensarci come al di là dell'ultima indicizzazione, considerala come indicizzazione basata sui bordi
• Perché l'indicizzazione basata sui bordi (indicizzazione dell'intervallo aperto a destra) è piacevole

Non pensarci come al di là dell'ultima indicizzazione, pensaci come indicizzazione basata sui bordi

Ho sostanzialmente semplificato e C ++ ha aggiunto questa sezione grazie a un commento molto utile di Pupazzo di neve :

C++ iterators are defined in terms of "which item will it retrieve next" instead of "to which item is it currently pointing?

Quindi, mi aiuta a pensare a un iteratore come a riposo non su un oggetto, ma sul bordo poco prima.

Per le sottosequenze con inizio e fine, invece di numerare il oggetti, ho mentalmente numerato i bordi tra gli oggetti. 0 è il bordo prima del primo oggetto. Il startIt è il margine da cui inizio; il stopIt è il limite su cui mi sto fermando.

La seguente immagine è adattata da Introduzione informale a Python .

   item    0   1   2   3   4   5
         +---+---+---+---+---+---+
         | P | y | t | h | o | n |
         +---+---+---+---+---+---+
iterator 0   1   2   3   4   5   6

Quindi startIt = 2 e stopIt = 5 portano a t, h, o .

Perché l'indicizzazione basata sui bordi (indicizzazione dell'intervallo aperto a destra) è piacevole

Ottieni alcune proprietà davvero belle:

• numero di elementi in una sottosequenza: n = stop - start
• Per creare sottosequenze adiacenti, stop of one == start of the next.

Esempi di seguito. Sto usando la sintassi di Python qui sotto perché non conosco il C ++. Se qualcuno è disposto a tradurre questa sezione in C ++ (Non disturbare lasciando il Python), sarò molto grato. Ad ogni modo, la notazione è non è importante: leggi [start:stop] come startIt e stopIt .

Questo è il contenitore che utilizzeremo

my_container = [ 'a', 'b', 'c', 'd' ]
## edges       ^    ^    ^    ^     ^
##             0    1    2    3     4

Accedi alle sottosequenze tagliando come c[start:stop] - ottieni tutto tra i bordi 1 e 3.

my_container[1:3] == ['b', 'c']

Per ottenere una porzione di lunghezza 3, mi assicuro stop = start + 3

my_container[1:4] == ['b', 'c', 'd']
# or do stop - start to find out how long the slice is:
4 - 1 == 3  # 3 elements in this slice.

Voglio che una sezione inizi dove finisce la fetta precedente. Quindi, ho lasciato il primo slice end on edge x e il secondo inizia sul bordo x . In questo modo io dividere in modo pulito il contenitore in due.

my_container[0:3] == ['a', 'b', 'c']
my_container[3:4] == ['d']

Commento conclusivo

Leggi il saggio di Edsger W. Dijkstra in risposta di manlio . È meno di 700 parole, con un pensiero cristallino e ugualmente chiaro scrittura a mano (e un collegamento a una versione html all'interno).

La libreria standard utilizza i puntatori finali one-past-end per una buona ragione: attenersi a questo modello. L'alternativa non lascia un buon modo per descrivere un intervallo vuoto.

Inoltre, a meno che tu non abbia assolutamente bisogno di qualcosa di diverso / speciale / scritto qui , usa Boost.Range .

Devi mantenere le convenzioni (definizioni) usate in un linguaggio di programmazione.

Esempio:

#include <iterator>

template< class Iterator>
class Range
{
    public:
    typedef typename std::iterator_traits<Iterator>::value_type value_type;
    typedef Iterator iterator;

    Range(const iterator& first, const iterator& last) noexcept
    :   m_first(first), m_last(last)
    {}

    Range(iterator&& first, iterator&& last) noexcept
    :   m_first(std::move(first)), m_last(std::move(last))
    {}

    Range(Range&& other) noexcept
    :   m_first(std::move(other.m_first)),
        m_last(std::move(other.m_last))
    {}

    Range& operator = (Range&& other) noexcept {
        m_first = std::move(other.m_first);
        m_last = std::move(other.m_last);
        return *this;
    }

    iterator begin() const noexcept { return m_first; }
    iterator end() const noexcept { return m_last; }

    private:
    iterator m_first;
    iterator m_last;
};

template<typename T>
inline Range<T> range(T&& first, T&& last) noexcept {
    return Range<T>(std::forward<T>(first), std::forward<T>(last));
}

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = { 1,2,3,4,5,6 };
    for(auto i : range(v.begin() + 1, v.end() - 1))
        std::cout << i << '\n';
    for(auto i : range(v.end(), v.end()))
        std::cout << i << '\n';
}

Senza attenersi alle convenzioni, l'utilizzo di librerie (algoritmi) o funzionalità linguistiche (a seconda dell'intervallo) diventa ingombrante. Ancor peggio, potrebbe portare i programmatori ad aspettarsi che la convenzione comune si trasformi in errori impercettibili. Inoltre, non c'è modo di esprimere un intervallo vuoto se [primo, ultimo] sono inclusi.