Perché tutte le funzioni dell'algoritmo accettano solo intervalli, non contenitori?

46

Ci sono molte funzioni utili in <algorithm> , ma tutte funzionano su "sequenze" - coppie di iteratori. Ad esempio, se ho un contenitore e mi piace eseguire std::accumulate su di esso, devo scrivere:

std::vector<int> myContainer = ...;
int sum = std::accumulate(myContainer.begin(), myContainer.end(), 0);

Quando tutto ciò che intendo fare è:

int sum = std::accumulate(myContainer, 0);

Che è un po 'più leggibile e chiaro, ai miei occhi.

Ora vedo che ci possono essere casi in cui si desidera operare solo su parti di un contenitore, quindi è decisamente utile avere l'opzione di intervalli passanti. Ma almeno nella mia esperienza, questo è un caso speciale raro. Di solito voglio operare su interi contenitori.

È facile scrivere una funzione wrapper che prende un contenitore e chiama begin() e end() su di esso, ma tali funzioni di convenienza non sono incluse nella libreria standard.

Mi piacerebbe conoscere il ragionamento alla base di questa scelta di progettazione STL.

    
posta lethal-guitar 05.03.2014 - 14:14
fonte

5 risposte

37

... it's definitely useful to have the option of passing ranges. But at least in my experience, that's a rare special case. I'll usually want to operate on whole containers

Potrebbe essere un caso speciale raro in la tua esperienza , ma in realtà il intero contenitore è il caso speciale e il intervallo arbitrario è il caso generale.

Hai già notato che puoi implementare il caso whole container utilizzando l'interfaccia corrente, ma non puoi fare il contrario.

Quindi, lo scrittore di librerie aveva una scelta tra l'implementazione di due interfacce in primo piano o l'implementazione di una sola che copre ancora tutti i casi.

It's easy to write a wrapper function which takes a container and calls begin() and end() on it, but such convenience functions are not included in the standard library

È vero, soprattutto perché le funzioni gratuite std::begin e std::end sono ora incluse.

Quindi, supponiamo che la libreria offra un sovraccarico di convenienza:

template <typename Container>
void sort(Container &c) {
  sort(begin(c), end(c));
}

ora ha anche bisogno di fornire il sovraccarico equivalente prendendo un funtore di comparazione, e abbiamo bisogno di fornire gli equivalenti per ogni altro algoritmo.

Ma abbiamo coperto almeno tutti i casi in cui vogliamo operare su un container completo, giusto? Bene, non proprio. Considerare

std::for_each(c.rbegin(), c.rend(), foo);

Se vogliamo gestire indietro sui contenitori, abbiamo bisogno di un altro metodo (o coppia di metodi) per algoritmo esistente.

Quindi, l'approccio basato sulla distanza è più generale nel senso semplice che:

  • può fare tutto ciò che la versione dell'intero contenitore può
  • l'approccio di intero contenitore raddoppia o triplica il numero di sovraccarichi richiesti, pur essendo meno potente
  • anche gli algoritmi basati sulla gamma sono componibili (è possibile impilare o incatenare gli adattatori iteratori, sebbene questo sia più comunemente fatto in linguaggi funzionali e Python)

C'è ovviamente un'altra ragione valida, ovvero che era già molto lavoro per ottenere lo standard STL standardizzato e gonfiarlo con i wrapper di convenienza prima che fosse ampiamente utilizzato non sarebbe un grande uso del tempo limitato del comitato. Se sei interessato, puoi trovare Stepanov & Rapporto tecnico di Lee qui

Come menzionato nei commenti, Boost.Range fornisce un approccio più recente senza richiedere modifiche allo standard.

    
risposta data 05.03.2014 - 15:44
fonte
18

C'è un articolo di Herb Sutter su questo argomento . Fondamentalmente, il problema è l'ambiguità del sovraccarico. Considerato quanto segue:

template<typename Iter>
void sort( Iter, Iter ); // 1

template<typename Iter, typename Pred>
void sort( Iter, Iter, Pred ); // 2

E aggiungendo quanto segue:

template<typename Container>
void sort( Container& ); // 3

template<typename Container, typename Pred>
void sort( Container&, Pred ); // 4

Renderà difficile distinguere correttamente 4 e 1 .

I concetti, come proposto ma alla fine non inclusi in C ++ 0x, lo avrebbero risolto, ed è anche possibile aggirarlo usando enable_if . Per alcuni algoritmi, non c'è alcun problema. Ma hanno deciso di non farlo.

Ora, dopo aver letto tutti i commenti e le risposte qui, penso che range oggetti sarebbe la soluzione migliore. Penso che darò un'occhiata a Boost.Range .

    
risposta data 06.03.2014 - 14:54
fonte
10

Fondamentalmente una decisione legacy. Il concetto di iteratore è modellato sui puntatori, ma i contenitori non sono modellati sugli array. Inoltre, poiché gli array sono difficili da superare (in genere richiedono un parametro template non di tipo), spesso una funzione ha solo puntatori disponibili.

Ma sì, a ben vedere la decisione è sbagliata. Saremmo stati meglio con un oggetto range costruibile da begin/end o begin/length ; ora abbiamo invece più algoritmi suffissi con _n .

    
risposta data 05.03.2014 - 16:26
fonte
4

Aggiungerli non ti manterrebbe alcun potere (puoi già fare l'intero contenitore chiamando .begin() e .end() te stesso) e aggiungerebbe un'altra cosa alla libreria che deve essere specificata correttamente, aggiunta al librerie dei produttori, testate, mantenute, ecc.

In breve, probabilmente non è lì perché non vale la pena di mantenere un set di modelli extra solo per salvare gli utenti di interi contenitori dal digitare un parametro di chiamata di funzione extra.

    
risposta data 05.03.2014 - 14:51
fonte
-1

Ormai, il link è una bella alternativa a std::for_each . Osserva, senza iteratori espliciti:

int a[5] = {1, 2, 3, 4, 5};
for (auto &i: a) { i *= 2; }

(Ispirato al link .)

    
risposta data 22.05.2015 - 21:54
fonte

Leggi altre domande sui tag