Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

10 int main()

11 {

12 const int SIZE = 6;

13 int a[ SIZE ] = { 1, 2, 3, 4, 5, 6 };

14 vector< int > v( a, a + SIZE );

15 ostream_iterator< int > output( cout, " " );

16 cout << "Il vector v contiene: ";

17 copy( v.begin(), v.end(), output );

18

19 cout << "\nPrimo elemento di v: " << v.front()

20 << "\nUltimo elemento di v: " << v.back();

21

22 v[ 0 ] = 7; // imposta a 7 il primo elemento

23 v.at( 2 ) = 10; // imposta l’elemento di posizione 2 a 10

24 v.insert( v.begin() + 1, 22 ); // inserisce 22 al 2 elemento

25 cout << "\nContenuto di v dopo il cambiamento: ";

26 copy( v.begin(), v.end(), output );

27

28 try {

29 v.at( 100 ) = 777; // accesso ad un elemento non valido

30 }

31 catch ( out_of_range e ) {

32 cout << "\nEccezione: " << e.what();

33 }

34

35 v.erase( v.begin() );

36 cout << "\ nContenuto di v dopo l’uso di erase(): ";

37 copy( v.begin(), v.end(), output );

38 v.erase( v.begin(), v.end() );

39 cout << "\nDopo erase(), il vector v "

40 << ( v.empty() ? "e’" : "non e’" ) << " vuoto";

41

42 v.insert( v.begin(), a, a + SIZE );

43 cout << "\ nContenuto di v prima di clear(): ";

44 copy( v.begin(), v.end(), output );

45 v.clear(); // clear() usa erase() per svuotare una collezione

46 cout << "\nDopo clear(), il vector v "

47 << ( v.empty() ? "e’" : "non e’" ) << " vuoto";

48

49 cout << endl;

50 return 0;

51 }

Esecuzione:

Il vector v contiene: 1 2 3 4 5 6

Primo elemento di v: 1

Ultimo elemento di v: 6

Contenuto di v dopo il cambiamento: 7 22 2 10 4 5 6

23

Eccezione: invalid vector<T> subscript

Contenuto di v dopo l’uso di erase(): 22 2 10 4 5 6

Dopo erase(), il vector v e’ vuoto

Contenuto di v prima di clear(): 1 2 3 4 5 6

Dopo clear(), il vector v e’ vuoto

La linea 15

ostream iterator< int > output( cout, );

dichiara un ostream iterator di nome output che può essere utilizzato per visualizzare interi

separati da uno spazio tramite cout. Un ostream iterator costituisce un meccanismo di output

sicuro per i tipi di dato, perché invia in output soltanto i valori di tipo int o di tipo compatibile

con int. Il primo argomento del costruttore specifica lo stream di output e il secondo argomento

è una stringa che specifica i caratteri da utilizzare come separatori per i valori inviati in output, in

iterator per visualizzare il contenuto del vector

questo caso uno spazio. Utilizzeremo ostream

in questo esempio.

La linea 17

copy( v.begin(), v.end(), output );

utilizza l’algoritmo copy() della STL per inviare l’intero contenuto del vector v sull’output stan-

dard. L’algoritmo copy() copia ogni elemento del container v a partire dalla posizione specificata

dall’iteratore passato come primo argomento fino alla posizione specificata dall’iteratore passato

come secondo argomento: quest’ultima posizione è esclusa. Il primo e il secondo argomento devono

soddisfare i requisiti degli iteratori di input, cioè degli iteratori tramite i quali si possono leggere

valori da un container. Gli elementi sono copiati alla posizione specificata dall’iteratore di output

(cioè un iteratore tramite il quale si può memorizzare o inviare in output un valore) specificato

iterator utilizzato

come ultimo argomento. In questo caso, l’iteratore di output è un ostream

con cout, per cui gli elementi sono copiati sull’output standard. Per utilizzare gli algoritmi della

STL, dovete includere il file di intestazione <algorithm>.

Le linee 19 e 20 utilizzano le funzioni front() e back() (disponibili per tutti i container

sequenziali) che determinano rispettivamente il primo e l’ultimo elemento del vector.

I risultati delle funzioni front() e back() sono indefiniti su un oggetto vector

Errore Tipico 3

vuoto.

Le linee 22 e 23

v[ 0 ] = 7; // imposta a 7 il primo elemento

v.at( 2 ) = 10; // imposta l’elemento di posizione 2 a 10

illustrano due modi per indirizzare un vector utilizzando gli indici che si possono anche utilizzare

con i container deque. La linea 22 utilizza l’operatore di indicizzazione in overloading che restituisce

un riferimento al valore della posizione specificata o un riferimento costante a tale valore, a seconda

se il container sia costante o meno. La funzione at() effettua la stessa operazione effettuando, però,

il controllo di validità dell’indice. La funzione at() controlla prima che il valore fornitole come

argomento si trovi nei limiti del vector. Se cosı̀ non è, at() lancia un’eccezione out of bounds

(come mostrano le linee 28-33). La Tabella 16 mostra alcuni tipi di eccezione della STL.

24

Tipi di eccezione Descrizione

out of range Indica che l’indice non è valido perché è fuori dai limiti del vector: questa eccezione

viene tipicamente lanciata dalla funzione at()

invalid argument Indica che una funzione ha ricevuto un argomento non valido

length error Indica un tentativo di creare un container troppo lungo, e vale anche per le string,

ecc.

bad alloc Indica che il tentativo di allocare memoria di new (o di un allocatore) non è andato

a buon fine perché non c’è memoria sufficiente

Tabella 12: Tipi di eccezione della STL

La linea 24

v.insert( v.begin() + 1, 22 ); // inserisce 22 al 2 elemento

utilizza una delle tre funzioni insert() disponibili per tutti i container sequenziali. Questa istru-

zione inserisce il valore 22 prima dell’elemento che si trova alla posizione specificata dall’iteratore

passato come primo argomento. In questo esempio, l’iteratore punta al secondo elemento del

vector, per cui 22 viene inserito nel secondo elemento e il secondo elemento originario diventa il

terzo del vector. Le altre versioni di insert() consentono di inserire copie multiple dello stesso

valore a partire da una particolare posizione del container o di inserire un intervallo di valori pro-

venienti da un altro container (o da un array) a partire da una particolare posizione del container

origine.

Le linee 35 e 38

v.erase( v.begin() );

v.erase( v.begin(), v.end() );

utilizzano le due funzioni erase() disponibili per tutti i container di prima classe. La linea 35

indica che l’elemento che si trova alla posizione specificata dall’argomento iteratore deve essere

eliminato dal container (in questo esempio l’elemento iniziale del vector). La linea 38 specifica

che devono essere eliminati dal container tutti gli elementi nell’intervallo che va dalla posizione

specificata dal primo argomento fino a quella del secondo argomento (esclusa). In questo esempio,

dal vector sono eliminati tutti gli elementi. La linea 40 utilizza la funzione empty() (disponibili

per tutti i container e gli adattatori) per avere la conferma che il vector sia vuoto.

Se si elimina un elemento che contiene un puntatore a un oggetto allocato dina-

Errore Tipico 4

micamente non si elimina anche tale oggetto.

La linea 42

v.insert( v.begin(), a, a + SIZE );

utilizza la versione di insert() che indica di inserire nel vector una sequenza di valori compresi tra

la posizione iniziale specificata dal secondo argomento e quella finale specificata dal terzo: i valori

possono provenire anche da un altro container, ma in questo caso provengono dall’array di interi

a. Ricordate che la posizione finale specifica la posizione della sequenza dopo l’ultimo elemento da

inserire: la copia non include anche quest’ultima posizione.

Infine, la linea 45

v.clear(); 25

utilizza la finzione clear() (disponibili per tutti i container di prima classe) per svuotare il vector.

Questa funzione chiama in realtà la versione di erase() utilizzata nella linea 38 per effettuare

l’operazione.

Nota: Ci sono altre funzioni di cui non abbiamo parlato che sono comuni a tutti i container o a

tutti i container sequenziali. Ne parleremo nelle prossime sezioni. Parleremo anche delle diverse

funzioni specifiche di ciascun container.

2.2 Il container sequenziale list

Il container sequenziale list fornisce un’implementazione efficiente delle operazioni di inserimento

ed eliminazione in qualsiasi posizione del container. Se la maggior parte di queste operazione si

verifica agli estremi del container, conviene però utilizzare l’implementazione più efficiente di deque

(sezione 2.3). La classe list è implementata come lista concatenata doppia, vale a dire ogni nodo

della list contiene un puntatore al nodo precedente e uno al nodo successivo. Ciò consente alla

classe list di supportare gli iteratori bidirezionali, per poter attraversare il container nei due

sensi. Ogni algoritmo che richiede iteratori di input, output, forward o bidirezionali può operare

su una list. Molte delle funzioni membro di list manipolano gli elementi del container come un

insieme ordinato di elementi. Oltre alle funzioni membro dei container della STL in Tabella 2 e alle

funzioni membro di tutti i container sequenziali discussi nella sezione 5, la classe list fornisce altre

front(), remove(), inique(), merge(), reverse() e sort().

funzioni membro: splice(), push

Il programma codice4.cpp illustra diverse caratteristiche della classe list. Ricordate che molte

delle funzioni presentate in codice2.cpp e codice3.cpp possono essere utilizzate con la classe

list. Per utilizzare la classe list occorre includere il file di intestazione <list>.

1 // codice4.cpp

2 // Test della classe list

3 #include <iostream>

4 #include <list>

5 #include <algorithm>

6

7 using namespace std;

8

9 template < class T >

10 void printList( const list< T > &listRef );

11

12 int main()

13 {

14 const int SIZE = 4;

15 int a[ SIZE ] = { 2, 6, 4, 8 };

16 list< int > values, otherValues;

17

18 values.push_front( 1 );

19 values.push_front( 2 );

20 values.push_back( 4 );

21 values.push_back( 3 );

22

23 cout << "values contiene: "; 26

24 printList( values );

25 values.sort();

26 cout << "\nvalues dopo sort() contiene: ";

27 printList( values );

28

29 otherValues.insert( otherValues.begin(), a, a + SIZE );

30 cout << "\notherValues contiene: ";

31 printList( otherValues );

32 values.splice( values.end(), otherValues );

33 cout << "\nDopo splice() values contiene: ";

34 printList( values );

35

36 values.sort();

37 cout << "\nvalues contiene: ";

38 printList( values );

39 otherValues.insert( otherValues.begin(), a, a + SIZE );

40 otherValues.sort();

41 cout << "\notherValues contiene: ";

42 printList( otherValues );

43 values.merge( otherValues );

44 cout << "\nDopo merge():\n values contiene: ";

45 printList( values );

46 cout << "\n otherValues contiene: ";

47 printList( otherValues );

48

49 values.pop_front();

50 values.pop_back(); // per tutti i container sequenziali

51 cout << "\nDopo pop_front() e pop_back() values contiene:\n";

52 printList( values );

53

54 values.unique();

55 cout << "\nDopo unique() values contiene: ";

56 printList( values );

57

58 // il metodo swap() e’ disponibile in tutti i container

59 values.swap( otherValues );

60 cout << "\nDopo swap:\n values contiene: ";

61 printList( values );

62 cout << "\n otherValues contiene: ";

63 printList( otherValues );

64

65 values.assign( otherValues.begin(), otherValues.end() );

66 cout << "\nDopo assign() values contiene: ";

67 printList( values );

68

69 values.merge( otherValues );

70 cout << "\nvalues contiene: "; 27

71 printList( values );

72 values.remove( 4 );

73 cout << "\nDopo remove( 4 ) values contiene: ";

74 printList( values );

75 cout << endl;

76 return 0;

77 }

78

79 template < class T >

80 void printList( const list< T > &listRef )

81 {

82 if ( listRef.empty() )

83 cout << "La list e’ vuota";

84 else {

85 ostream_iterator< T > output( cout, " " );

86 copy( listRef.begin(), listRef.end(), output );

87 }

88 }

Esecuzione:

values contiene: 2 1 4 3

values dopo sort() contiene: 1 2 3 4

otherValues contiene: 2 6 4 8

Dopo splice() values contiene: 1 2 3 4 2 6 4 8

values contiene: 1 2 2 3 4 4 6 8

otherValues contiene: 2 6 4 8

Dopo merge():

values contiene: 1 2 2 2 3 4 4 4 6 6 8 8

otherValues contiene: La list e’ vuota

front() e pop back() values contiene: 2 3 4 6 8

Dopo pop

Dopo swap(): values contiene: La list e’ vuota

otherValues contiene: 2 3 4 6 8

Dopo assign() values contiene: 2 3 4 6 8

values contiene: 2 2 3 3 4 4 6 6 8 8

Dopo remove( 4 ) values contiene: 2 2 3 3 6 6 8 8

La linea 16

list< int > values, otherValues;

istanzia due oggetti list in grado di memorizzare interi. Le linee 18 e 19 utilizzano la funzione

push front() per inserire degli interi all’inizio di values. La funzione push front() è specifica

delle classi list e deque (e non di vector). Le linee 20 e 21 utilizzano la funzione push back()

per inserire degli interi alla fine di values. Ricordate che la funzione push back() è comune a tutti

i container sequenziali.

La linea 25

values.sort(); 28 2

utilizza la funzione sort() membro di list per porre gli elementi della list in ordine crescente .

C’è una seconda versione di sort() che consente di specificare una funzione predicativa binaria che

prende due argomenti (i valori nella list), effettua un confronto e restituisce un valore bool che

indica il risultato. Questa funzione determina l’ordine in cui sono ordinati gli elementi della list.

Questa versione può risultare particolarmente utile per una list che memorizza puntatori anziché

3

valori .

La linea 32

values.splice( values.end(), otherValues );

utilizza la funzione splice() per eliminare gli elementi in otherValues e inserirli in values prima

della posizione specificata dall’iteratore passato come primo argomento. Ci sono altre due versioni

di questa funzione. La funzione splice() con tre argomenti consente di eliminare un elemento dal

container specificato come secondo argomento dalla posizione specificata dall’iteratore passato come

terzo argomento. La funzione splice() con quattro argomenti utilizza gli ultimi due argomenti

per specificare l’intervallo di posizioni da togliere dal container specificato come secondo argomento

e da porre alla posizione specificata dal primo argomento.

Dopo aver inserito altri elementi in otherValues e aver ordinato values e otherValues, la

linea 43

values.merge( otherValues );

utilizza la funzione merge() membro di list per rimuovere tutti gli elementi di otherValues e per

inserirli in sequenza ordinata in values. Entrambe le list devono essere ordinate con lo stesso

criterio prima che venga effettuata questa operazione. Una seconda versione di merge() consente

di fornire una funzione predicativa che prende due argomenti (i valori nella list) e restituisce un

valore bool. La funzione predicativa specifica il criterio di ordinamento utilizzato da merge().

front() per eliminare il primo elemento nella list. La

La linea 49 utilizza la funzione pop

linea 50 utilizza la funzione pop back() (disponibile per tutti i container sequenziali) per eliminare

l’ultimo elemento della list.

La linea 54

values.unique();

utilizza la funzione unique() per eliminare gli elementi duplicati presenti nella list. La list

dovrebbe essere ordinata (in modo che tutti i duplicati siano contigui) prima che sia effettuata

questa operazione, per garantire che siano eliminati tutti i duplicati. Una seconda versione di

unique() consente di fornire una funzione predicativa che prende due argomenti (i valori nella

list) e restituisce un valore bool. La funzione predicativa specifica se due elementi sono uguali.

La linea 59

values.swap( otherValues );

utilizza la funzione swap() (disponibile per tutti i container) per scambiare il contenuto di values

con quello di otherVa1ues.

La linea 65

2 Questa operazione è differente da sort() negli algoritmi della STL.

3 In codice12.cpp mostriamo una funzione predicativa unaria. Una funzione di questo tipo prende un solo

argomento, effettua un confronto utilizzando tale argomento e restituisce un valore bool che indica il risultato.

29

values.assign( otherValues.begin(), otherValues.end() );

utilizza la funzione assign() per sostituire il contenuto di values con quello di otherValues

nell’intervallo di elementi specificato dai due argomenti iteratore. Una seconda versione di assign()

sostituisce il contenuto originario con copie dei valori specificati nel secondo argomento. Il primo

argomento della funzione specifica il numero di copie.

La linea 72

values.remove( 4 );

utilizza la funzione remove() per eliminare tutte le copie del valore 4 dalla list.

2.3 Il container sequenziale deque

La classe deque fornisce diversi dei pregi di un vector e di una list in un unico container. Il

termine deque è una forma abbreviata per “double-ended queue”, coda a due estremi. La classe

deque è implementata per fornire un accesso indicizzato efficiente per la lettura e la modifica dei suoi

elementi, un po’ come un vector. La classe deque è anche implementata per effettuare operazioni

di inserimento ed eliminazione efficienti per entrambi gli estremi, come una list (anche se una

list può anche effettuare inserimenti/eliminazioni efficienti nelle posizioni intermedie). La classe

deque supporta gli iteratori ad accesso casuale, per cui i deque si possono utilizzare con tutti gli

algoritmi della STL. Uno degli usi più comuni di un deque consiste nel mantenere una coda di

elementi FIFO (il primo inserito è anche il primo estratto).

È prevista l’allocazione di ulteriore spazio per un deque ad entrambi gli estremi in blocchi

di memoria che sono mantenuti tipicamente da array di puntatori. Dato che la disposizione in

memoria di un deque non è contigua, i suoi iteratori devono essere più “intelligenti” dei puntatori

che attraversano i vector o gli array.

Quando viene allocato un blocco di memoria per un deque, in diverse implementazio-

Efficienza 12

ni tale blocco non viene deallocato finché il deque non viene distrutto. Ciò ottimizza le operazioni di

un deque rispetto alle implementazioni in cui viene ripetutamente allocato, deallocato e riallocato.

Ma ciò significa anche che una deque utilizzerà la memoria in modo meno efficiente rispetto, ad

esempio, ad un vector.

Inserimenti/eliminazioni nelle posizioni intermedie di un deque sono ottimizzati per

Efficienza 13

minimizzare il numero di elementi copiati, mantenendo la parvenza che gli elementi siano contigui.

La classe deque fornisce le stesse operazioni di base della classe vector, e vi aggiunge le funzioni

front() e pop front() rispettivamente per l’inserimento e l’eliminazione all’inizio

membro push

del deque.

In codice5.cpp vengono mostrate le caratteristiche della classe deque. Ricordate che molte

delle funzioni presentate in codice2.cpp, codice3.cpp e codice4.cpp possono essere utilizzate

con la classe deque. Per utilizzare la classe deque bisogna includere il file di intestazione <deque>.

La linea 11

deque< double > values;

istanzia un deque che può memorizzare valori double. Le linee 14-16 utilizzano le funzioni push front()

e push back() per inserire degli elementi all’inizio e alla fine del deque. Ricordate che push back()

è disponibile per tutti i container sequenziali, mentre push front() è disponibile soltanto per le

classi list e deque. 30

1 // codice5.cpp

2 // Test della classe deque

3 #include <iostream>

4 #include <deque>

5 #include <algorithm>

6

7 using namespace std;

8

9 int main()

10 {

11 deque< double > values;

12 ostream_iterator< double > output( cout, " " );

13

14 values.push_front( 2.2 );

15 values.push_front( 3.5 );

16 values.push_back( 1.1 );

17

18 cout << "values contiene: ";

19

20 for ( int i = 0; i < values.size(); ++i )

21 cout << values[ i ] << ’ ’;

22

23 values.pop_front();

24 cout << "\nDopo pop_front() values contiene: ";

25 copy ( values.begin(), values.end(), output );

26

27 values[ 1 ] = 5.4;

28 cout << "\nDopo values[ 1 ] = 5.4, values contiene: ";

29 copy ( values.begin(), values.end(), output );

30 cout << endl;

31 return 0;

32 }

Esecuzione:

values contiene: 3.5 2.2 1.1

Dopo pop front() values contiene: 2.2 1.1

Dopo values[ 1 ] = 5.4, values contiene: 2.2 5.4

Il costrutto for alla linea 20

for ( int i = 0; i < values.size(); ++i )

cout << values[ i ] << ’ ’;

utilizza l’operatore di indicizzazione per recuperare il valore di ogni elemento del deque e inviarlo in

output. Notare l’uso della funzione size() nella condizione, per evitare di accedere a un elemento

che si trovi oltre i limiti del deque. La linea 23 utilizza la funzione pop front() per eliminare il

primo elemento del deque. Ricordate che la funzione pop front() è disponibile soltanto per le

classi list e deque (non per la classe vector). 31

La linea 27

values[ 1 ] = 5.4;

utilizza l’operatore di indicizzazione per creare un lvalue. Ciò consente di assegnare direttamente i

valori a ogni elemento del deque.

3 I container associativi

I container associativi della STL sono stati progettati per fornire un accesso diretto nelle opera-

zioni di memorizzazione e di recupero di elementi tramite chiavi di ricerca. I quattro container

associativi sono multiset, set, multimap e map. In ogni container le chiavi sono mantenute ordi-

nate. L’attraversamento di un container associativo avviene secondo l’ordinamento previsto su tale

container. Le classi multiset e set forniscono operazioni per la manipolazione di insiemi di valori

in cui i valori sono le chiavi, ovvero non c’è separazione tra valori e chiavi associate. La principale

differenza tra un multiset e un set è che un multiset permette chiavi duplicate mentre un set

no. Le classi multimap e map forniscono operazioni per la manipolazione dei valori associati alle

chiavi. La principale differenza tra un multimap e un map è che un multimap permette chiavi du-

plicate con valori associati e un map permette soltanto chiavi univoche. Oltre alle funzioni membro

comuni a tutti i container presentati in Tabella 2, tutti i container associativi supportano anche

molte altre funzioni membro, tra cui find(), lower bound(), upper bound() e count(). Nelle

sezioni seguenti mostriamo degli esempi per ogni container associativo e per le funzioni membro

comuni.

3.1 Il container associativo multiset

Il container associativo multiset (multinsieme) serve per la memorizzazione e il recupero veloci di

dati permettendo la presenza di chiavi duplicate. L’ordinamento degli elementi è determinato da

un oggetto funzione comparatrice. Per esempio, in un multinsieme di interi gli elementi possono

4

essere posti in ordine crescente ordinando le chiavi per mezzo dell’oggetto funzione less<int> .

Il tipo di dato delle chiavi in tutti i container associativi deve supportare il confronto in maniera

corretta sulla base dell’oggetto funzione comparatrice specificato: le chiavi ordinate con less<int>

devono supportare il confronto con la funzione operator<. Se le chiavi utilizzate nei container

associativi sono tipi di dati definiti dal programmatore, essi devono fornire gli operatori appropriati

di confronto (vedi la nota Ingegneria del Software 3). I multiset supportano iteratori bidirezionali,

ma non ad accesso casuale.

Per motivi di efficienza i multiset e i set sono implementati tipicamente con i

Efficienza 14

cosiddetti red-black trees (alberi rosso-nero) un tipo particolare di alberi di binari di ricerca che

tendono ad essere bilanciati, minimizzando cosi tempi medi di ricerca.

Il programma in codice6.cpp mostra un multiset di interi che si trovano in ordine crescente. Per

utilizzare la classe multiset dovete includere il file <set>. I container multiset e set forniscono

le stesse funzioni membro.

1 // codice6.cpp

2 // Test della classe multiset

4 Vedi sezione 7 32

3 #include <iostream>

4 #include <set>

5 #include <algorithm>

6

7 using namespace std;

8

9 int main()

10 {

11 const int SIZE = 10;

12 int a[ SIZE ] = { 7, 22, 9, 1, 18, 30, 100, 22, 85, 13 };

13 typedef multiset< int, less< int > > ims;

14 ims intMultiset; // ims sta per "integer multiset"

15 ostream_iterator< int > output( cout, " " );

16

17 cout << "Ora ci sono " << intMultiset.count( 15 )

18 << " occorrenze di 15 nel multiset\n";

19 intMultiset.insert( 15 );

20 intMultiset.insert( 15 );

21 cout << "Dopo inserts(), ci sono "

22 << intMultiset.count( 15 )

23 << " occorrenze di 15 nel multiset\n";

24

25 ims::const_iterator result;

26

27 result = intMultiset.find( 15 ); // find rende un iteratore

28

29 if ( result != intMultiset.end() ) // se l’iteratore non e’ alla fine

30 cout << "Trovato il valore 15\n"; // e’ stato trovato 15

31

32 result = intMultiset.find( 20 );

33

34 if ( result == intMultiset.end() ) // sara’ quindi vero

35 cout << "Non trovato il valore 20\n"; // 20 non trovato

36

37 intMultiset.insert( a, a + SIZE ); // aggiunge array a al multiset

38 cout << "Dopo insert(), intMultiset contiene:\n";

39 copy( intMultiset.begin(), intMultiset.end(), output );

40

41 cout << "\nLower bound di 22: "

42 << *( intMultiset.lower_bound( 22 ) );

43 cout << "\nUpper bound di 22: "

44 << *( intMultiset.upper_bound( 22 ) );

45

46 pair< ims::const_iterator, ims::const_iterator > p;

47

48 p = intMultiset.equal_range( 22 );

49 cout << "\nUsando equal_range( 22 )"

33

50 << "\n Lower bound: " << *( p.first )

51 << "\n Upper bound: " << *( p.second );

52 cout << endl;

53 return 0;

54 }

Esecuzione:

Ora ci sono 0 occorrenze di 15 nel multiset

Dopo inserts(), ci sono 2 occorrenze di 15 nel multiset

Trovato il valore 15

Non trovato il valore 20

Dopo insert(), intMultiset contiene: 1 7 9 13 15 15 18 22 22 30 85 100

Lower bound di 22: 22

Upper bound di 22: 30

Usando equal range( 22 ):

Lower bound: 22

Upper bound: 30

Le linee 13 e 14

typedef multiset< int, less< int > > ims;

ims intMultiset; // ims sta per "integer multiset"

creano con typedef un nuovo tipo di dato corrispondente a un multinsieme di interi posti in ordine

crescente utilizzando l’oggetto funzione less<int>. Questo nuovo tipo viene poi utilizzato per

stanziare un oggetto multiset di interi, intMultiset.

Utilizzate typedef per semplificare il codice che contiene nomi lunghi (come

Buona Abitudine 1

multiset).

L’istruzione di output di linea 17

cout << "Ora ci sono " << intMultiset.count( 15 )

<< " occorrenze di 15 nel multiset\n";

utilizza la funzione count() (disponibile per tutti i container associativi) per contare il numero di

occorrenze del valore 15 presenti correntemente nel multiset.

Le linee 19 e 20

intMultiset.insert( 15 );

intMultiset.insert( 15 );

utilizzano una delle tre versioni di insert() per aggiungere il valore 15 al multiset. Una seconda

versione di insert() prende come argomenti un iteratore e un valore e inizia la ricerca del punto di

inserimento dalla posizione specificata dall’iteratore. Una terza versione di insert() prende come

argomenti due iteratori che specificano un intervallo di valori provenienti da un altro container da

aggiungere al multiset.

La linea 27 34

result = intMultiset.find( 15 ); // find rende un iteratore

utilizza la funzione find() (disponibile per tutti i container associativi) per localizzare il valore

15 nel multiset. La funzione find() restituisce un iterator o un const iterator che punta

alla prima posizione in cui è stato trovato il valore cercato. Se il valore non viene trovato, find()

restituisce un iterator o un const iterator uguale al valore restituito dalla funzione end().

La linea 37

intMultiset.insert( a, a + SIZE ); // aggiunge l’array a al multiset

utilizza la funzione insert() per inserire gli elementi dell’array a nel multiset. Alla linea 39,

l’algoritmo copy() copia gli elementi del multiset sull’output standard. Notate che gli elementi

sono visualizzati in ordine crescente.

Le linee 41-44

cout << "\nLower bound di 22: "

<< *( intMultiset.lower_bound( 22 ) );

cout << "\nUpper bound di 22: "

<< *( intMultiset.upper_bound( 22 ) );

utilizzano le funzioni disponibili in tutti i container associativi lower bound() (che sta per limite

bound() (che sta per limite superiore) per determinare la posizione della prima

inferiore) e upper

occorrenza del valore 22 nel multiset e la posizione dell’elemento che si trova dopo l’ultima occor-

renza di 22 nel multiset. Entrambe le funzioni restituiscono degli iterator o const iterator

che puntano alle posizioni appropriate o l’iteratore restituito da end() se il valore non è presente

nel multiset.

La linea 46 iterator, ims::const iterator > p;

pair< ims::const

crea un’istanza della classe pair di nome p. Gli oggetti della classe pair servono a manipo-

iterator

lare coppie di valori. In questo esempio, il contenuto di un pair sono due const

per il nostro multiset di interi. Lo scopo di p è memorizzare il valore restituito dalla funzio-

ne equal range() di multiset, che restituisce un pair contenente i risultati delle operazioni

lower bound() e upper bound(). Il tipo pair contiene due dati membro public di nome first e

second.

La linea 48

p = intMultiset.equal range( 22 );

utilizza la lunzione equal range() per determinare il lower bound e l’upper bound di 22 nel

multiset. La linee 50 e 51 utilizzano p.first() e p.second() rispettivamente per accedere a

lower bound e upper bound. Abbiamo dereferenziato gli iteratori per visualizzare i valori presenti

alle posizioni restituite da equal range().

3.2 Il container associativo set

Il container associativo set è utile per la memorizzazione e il recupero efficiente di chiavi univoche.

L’implementazione di un set è identica a quella di un multiset eccetto il fatto che un set deve

avere chiavi uniche, perciò se si tenta di inserire un duplicato di una chiave in un set, tale duplicato

35

viene ignorato. Infatti, set è l’implementazione del concetto matematico di insieme, ed è questo

il comportamento degli insiemi in matematica, per cui non identificheremo questo comportamento

come errore di programmazione. Un set supporta iteratori bidirezionali, ma non ad accesso casuale.

Il programma in codice7.cpp mostra un set di double. Per utilizzare la classe set bisogna

includere il file di intestazione <set>.

1 // codice7.cpp

2 // Test della classe set

3 #include <iostream>

4 #include <set>

5 #include <algorithm>

6

7 using namespace std;

8

9 int main()

10 {

11 typedef set< double, less< double > > double_set;

12 const int SIZE = 5;

13 double a[ SIZE ] = { 2.1, 4.2, 9.5, 2.1, 3.7 };

14 double_set doubleSet( a, a + SIZE );

15 ostream_iterator< double > output( cout, " " );

16

17 cout << "doubleSet contiene: ";

18 copy( doubleSet.begin(), doubleSet.end(), output );

19

20 pair< double_set::const_iterator, bool > p;

21

22 p = doubleSet.insert( 13.8 ); // valore non presente nel set

23 cout << ’\n’ << *( p.first )

24 << ( p.second ? " e’" : " non e’" ) << " inserito";

25 cout << "\ndoubleSet contiene: ";

26 copy( doubleSet.begin(), doubleSet.end(), output );

27

28 p = doubleSet.insert( 9.5 ); // valore gia’ nel set

29 cout << ’\n’ << *( p.first )

30 << ( p.second ? " e’" : " non e’" ) << " inserito";

31 cout << "\ndoubleSet contiene: ";

32 copy( doubleSet.begin(), doubleSet.end(), output );

33

34 cout << endl;

35 return 0;

36 }

Esecuzione:

DoubleSet contiene: 2.1 3.7 4.2 9.5

13.8 e’ inserito

DoubleSet contiene: 2.1 3.7 4.2 9.5 13.8

9.5 non e’ inserito 36

DoubleSet contiene: 2.1 3.7 4.2 9.5 13.8

La linea 11

typedef set< double, less< double > > double set;

utilizza typedef per creare un nuovo tipo di dato per un set di double posti in ordine crescente

utilizzando l’oggetto funzione less<double>. La linea 14

double set doubleSet( a, a + SIZE );

set per istanziare l’oggetto doubleSet. Il costruttore prende gli

utilizza il nuovo tipo double

elementi nell’array a tra a e a + SIZE (ovvero tutto l’array) e li inserisce nel set. La linea 18

utilizza l’algoritmo copy() per visualizzare il contenuto dell’insieme. Osservate che il valore 2.1,

che compare due volte nell’array a, compare soltanto una volta in doubleSet. Ciò accade perché

il container set non permette chiavi duplicate.

La linea 20

pair< double set::const iterator, bool > p;

dichiara una coppia (in inglese pair) che consiste in un const iterator per un double set e un

valore bool. Questo oggetto memorizza il risultato di una chiamata alla funzione insert() di set.

La linea 22

p = doubleSet.insert( 13.8 ); // valore non presente nel set

utilizza la funzione insert() per porre nell’insieme il valore 13.8. L’oggetto pair restituito, p,

contiene un iteratore p.first() che punta al valore 13.8 nel set e un valore bool che è true se il

valore è stato effettivamente inserito e false in caso contrario (era già presente nel set).

3.3 Il container associativo multimap

Il container associativo multimap si utilizza per la memorizzazione e il recupero efficienti di valori

associati ad una chiave (che prendono anche il nome di coppie chiave/valore). Molti dei metodi

utilizzati con i multiset e i set sono comuni anche a multimap e map. Gli elementi dei multimap e

dei map sono coppie di chiavi e valori, anziché valori individuali. Quando si effettua un inserimento in

un multimap o in un map, si utilizza un oggetto pair che contiene la chiave e il valore. L’ordinamento

delle chiavi è determinato dalla funzione comparatrice. Per esempio, in un multimap che utilizza

gli interi come tipo di chiave, le chiavi possono essere poste in ordine crescente tramite l’oggetto

funzione comparatrice less<int>. In un multimap sono permesse chiavi duplicate, per cui a una

singola chiave si possono associare più valori. Questo è un esempio di relazione uno-a-molti. Per

esempio, in un sistema di elaborazione delle transazioni su carta di credito, un conto relativo a una

sola carta di credito può essere associato a molte transazioni; in un università, uno studente può

iscriversi a molti corsi e un professore può insegnare a molti studenti; nelle forze armate, un grado

(come “soldato semplice”) si riferisce a molte persone. Un multimap supporta iteratori bidirezionali,

ma non ad accesso casuale. Come per i multiset e i set, i multimap sono tipicamente implementati

con alberi di ricerca binaria rosso/nero, in cui i nodi dell’albero sono le coppie chiave/valore. Il

programma in codice8.cpp mostra l’utilizzo del container associativo multimap. Per utilizzare la

classe multimap bisogna includere il file di intestazione <map>.

37

Un multimap è implementato per localizzare in modo efficiente tutti i valori associati

Efficienza 15

a una data chiave.

1 // codice8.cpp

2 // Test della classe multimap

3 #include <iostream>

4 #include <map>

5

6 using namespace std;

7

8 int main()

9 {

10 typedef multimap< int, double, less< int > > mmid;

11 mmid pairs;

12

13 cout << "Ora ci sono " << pairs.count( 15 )

14 << " coppie con chiave 15 nel multimap\n";

15 pairs.insert( mmid::value_type( 15, 2.7 ) );

16 pairs.insert( mmid::value_type( 15, 99.3 ) );

17 cout << "Dopo insert(), ci sono "

18 << pairs.count( 15 )

19 << " coppie con chiave 15\n";

20 pairs.insert( mmid::value_type( 30, 111.11 ) );

21 pairs.insert( mmid::value_type( 10, 22.22 ) );

22 pairs.insert( mmid::value_type( 25, 33.333 ) );

23 pairs.insert( mmid::value_type( 20, 9.345 ) );

24 pairs.insert( mmid::value_type( 5, 77.54 ) );

25 cout << "La multimap contiene:\nKey\tValue\n";

26

27 for ( mmid::const_iterator iter = pairs.begin();

28 iter != pairs.end(); ++iter )

29 cout << iter->first << ’\t’

30 << iter->second << ’\n’;

31

32 cout << endl;

33 return 0;

34 }

Esecuzione:

Ora ci sono 0 coppie con chiave 15 nel multimap

Dopo insert(), ci sono 2 coppie con chiave 15

La multimap contiene:

Key Value

5 77.54

10 22.22

15 2.7

15 99.3

20 9.345 38

25 33.333

30 111.11

La linea 10

typedef multimap< int, double, less< int > > mmid;

utilizza typedef per definire un nuovo tipo multimap in cui il tipo della chiave è int, il tipo del

valore associato è double e gli elementi sono posti in ordine crescente. La linea 11 utilizza il nuovo

tipo per istanziare un multimap di nome pairs.

L’istruzione di linea 13

cout << "Ora ci sono " << pairs.count( 15 )

<< " coppie con chiave 15 nel multimap\n";

utilizza la funzione count() per determinare il numero di coppie chiave/valore per la chiave 15.

La linea 15

pairs.insert( mmid::value_type( 15, 2.7 ) );

utilizza la funzione insert() per aggiungere una nuova coppia chiave/valore al multimap. L’

espressione mmid::value type( 15, 2.7 ) crea un oggetto pair in cui first è la chiave (15) di

tipo int e second è il valore (2.7) di tipo double. Il tipo mmid::value type è definito alla linea

10 come parte del typedef per il multimap.

Il costrutto for di linea 27 visualizza il contenuto del multimap, incluse le chiavi e i valori. Le

linee 29 e 30

cout << iter->first << ’\t’

<< iter->second << ’\n’;

iterator di nome iter per accedere ai membri del pair in ogni elemento del

utilizzano il const

multimap. Osservate nell’output che le chiavi sono in ordine crescente.

3.4 Il container associativo map

Il container associativo map (mappa) è utilizzato per la memorizzazione e il recupero veloci di chiavi

uniche e di valori associati. Una mappa non permette chiavi duplicate, per cui si può associare un

solo valore a ogni chiave. Si tratta della cosiddetta relazione uno-a-uno. Per esempio, un’azienda

che utilizza numeri identificativi unici per i dipendenti come 100, 200 e 300 può porli in un container

map che associa il numero del dipendente con il suo numero telefonico interno (ad esempio 4321,

4115 e 5217, rispettivamente). Con un map si specifica la chiave e si ottiene velocemente il dato

associato. Un map è chiamato comunemente array associativo: fornendo la chiave nell’operatore di

indicizzazione [ ] di map, si localizza il valore associato alla chiave nella mappa. Le operazioni di

inserimento/eliminazione possono essere effettuate ovunque in un map.

Il programma in codice9.cpp mostra l’uso del container associativo map. Questo programma

utilizza le stesse caratteristiche di quello in codice8.cpp eccetto l’operatore di indicizzazione. Per

utilizzare la classe map bisogna includere il file di intestazione <map>. Le linee 29 e 30

pairs[ 25 ] = 9999.99; // cambia il valore esistente per 25

pairs[ 46 ] = 8765.43; // inserisce un nuovo valore per 46

39

utilizzano l’operatore di indicizzazione della classe map. Se l’indice è una chiave già presente nel map,

l’operatore restituisce un riferimento al valore associato. Altrimenti l’operatore inserisce la chiave

nel map e restituisce un riferimento che può essere utilizzata per associare un valore a tale chiave.

La linea 29 sostituisce il valore per la chiave 25 (che valeva precedentemente 33.333 come specifica

la linea 17) con il nuovo valore di 9999.99. La linea 30 inserisce una nuova coppia chiave/valore nel

map: si dice che si crea un’associazione.

1 codice9.cpp

2 Test della classe map

3 #include <iostream>

4 #include <map>

5

6 using namespace std;

7

8 int main()

9 {

10 typedef map< int, double, less< int > > mid;

l1 mid pairs;

12

13 pairs.insert( mid::value_type( 15, 2.7 ) );

14 pairs.insert( mid::value_type( 36, 111.11 ) )

15 pairs.insert( mid::value_type( 5, 1010.1 ) );

16 pairs.insert( mid::value_type( 16, 22.22 ) );

17 pairs.insert( mid::value_type( 25, 33.333 ) );

18 pairs.insert( mid::value_type( 5, 77.54 ) ); // duplicato ignorato

19 pairs.insert( mid::value_type( 26, 9.345 ) );

20 pairs.insert( mid::value_type( 15, 99.3 ) ); // duplicato ignorato

21 cout << "pairs contiene:\nKey\tvalue\n";

22

23 mid::const_iterator iter;

24

25 for ( iter = pairs.begin(); iter pairs.end(); ++iter )

26 cout << iter->first ’\t’

27 << iter->second ’\n’;

28

29 pairs[ 25 ] = 9999.99; // cambia il valore esistente per 25

30 pairs[ 46 ] = 8765.43; // inserisce un nuovo valore per 46

31 cout << "\nDopo pairs[ ], pairs contiene:"

32 << "\nKey\tvalue\n";

33

34 for ( iter = pairs.begin(); iter != pairs.end(); ++iter )

35 cout << iter->first ’\t’

36 << iter->second ’\n’;

37

38 cout << endl;

39 return 0;

40 } 40

Esecuzione:

pairs contiene:

Key Value

5 1010.1

10 22.22

15 2.7

20 9.345

25 33.333

30 111.11

Dopo pairs[ ], pairs contiene:

Key Value

5 1010.1

10 22.22

15 2.7

20 9.345

25 9999.99

30 111.11

40 8765.43

4 Adattatori di container

La STL fornisce tre adattatori di container: stack, queue e priority queue. Gli adattatori non

sono container di prima classe: essi non forniscono l’implementazione effettiva di una struttura

dati in cui memorizzare elementi, perché non supportano gli iteratori. Il questa dispensa non

analizziamo gli adattatori di container.

5 Gli algoritmi

Fino all’avvento della STL, le librerie di container e di algoritmi sviluppate da rivenditori diversi

erano sostanzialmente incompatibili. Le prime librerie di container utilizzavano generalmente l’ere-

ditarietà e il polimorfismo, con l’iperutilizzo di risorse tipico delle chiamate di funzioni virtuali. Le

prime librerie includevano gli algoritmi nelle classi container come comportamenti di tali classi. La

STL separa gli algoritmi dai container. Ciò semplifica notevolmente l’aggiunta di nuovi algoritmi.

La STL è stata implementata con un’attenzione particolare all’efficienza. Perciò evita lo spreco

di risorse tipico delle chiamate di funzioni virtuali. Con la STL, si può accedere agli elementi dei

container tramite gli iteratori.

Gli algoritmi della STL non dipendono dai dettagli di implementazione

Ingegneria del Software 8

dei container su cui operano. Se gli iteratori del container (o dell’array) soddisfano i requisiti

dell’algoritmo, esso può funzionare allo stesso modo su un array in vecchio stile C, basato sui

puntatori, e su un container della STL (e su qualsiasi struttura dati definita dall’utente).

È possibile aggiungere facilmente nuovi algoritmi all’ STL senza dover

Ingegneria del Software 9

modificare le classi container. 41

5.1 fill, fill n, generate e generate n

Il programma in codice10.cpp mostra le funzioni della STL fill(), fill n(), generate() e

generate n(). Le funzioni fill() e fill n() impostano un intervallo di elementi di un container

a un valore specifico. Le funzioni generate() e generate n() utilizzano una funzione generatore

per creare valori per un intervallo di elementi di un container. La funzione generatore non prende

argomenti e restituisce un valore che può essere posto in un elemento di un container.

1 // codice10.cpp

2 // Esempio dei metodi della STL

3 // fill(), fill_n(), generate() e generate_n().

4 #include <iostream>

5 #include <algorithm>

6 #include <vector>

7

8 using namespace std;

9

10 char nextLetter();

11

12 int main()

13 {

14 vector< char > chars( 10 );

15 ostream_iterator< char > output( cout, " ");

16

17 fill( chars.begin(), chars.end(),’5’ );

18 cout << "Il vettore chars dopo fill() con 5:\n";

19 copy( chars.begin(), chars.end(), output );

28

21 fill_n( chars.begin(), 5, ’A’ );

22 cout << "Il vettore chars dopo fill_n() di cinque elementi"

23 uguali ad A:\n";

24 copy( chars.begin(), chars.end(), output );

25

26 generate( chars.begin(), chars.end(), nextLetter );

27 cout << "Il vettore chars dopo generate() lettere A-J:\n";

28 copy( chars.begin(), chars.end(), output );

29

30 generate_n( chars.begin(), 5, nextLetter );

31 cout << "Il vettore chars dopo generate_n() K-O per i"

32 primi cinque elementi:\n";

33 copy(chars.begin(), chars.end(), output );

34

35 cout << endl;

36 return 0;

37 }

38

39 char nextLetter()

48 { 42

41 static char letter = ’A’;

42 return letter++;

43 }

Esecuzione:

Il vettore chars dopo fill() con 5:

5 5 5 5 5 5 5 5 5 5

Il vettore chars dopo fill n() di cinque elementi uguali ad A:

A A A A A 5 5 5 5 5

Il vettore chars dopo generate() lettere A-J:

A B C D E F G H I J n() K-O per i primi cinque elementi:

Il vettore chars dopo generate

K L M N O F G H I J

La linea 17

fill( chars.begin(), chars.end(),’5’ );

utilizza la funzione fill() per porre il carattere ’5’, in ogni elemento del vettore chars da chars.begin()

a chars.end() escluso. Notate che gli iteratori forniti come primo e secondo argomento devono

essere perlomeno iteratori forward (cioè possono essere utilizzati per accedere sequenzialmente ad

un container in avanti).

La linea 21

fill_n( chars.begin(), 5, ’A’ );

utilizza la funzione fill n() per porre il carattere ’A’ nei primi cinque elementi del vettore chars.

L’iteratore fornito come primo argomento deve essere (almeno) un iteratore di output (cioè può

essere utilizzato per l’output su un container in avanti). Il secondo argomento specifica il numero

di elementi da impostare. Il terzo argomento specifica il valore da porre in ogni elemento.

La linea 26

generate( chars.begin(), chars.end(), nextLetter );

utilizza la funzione generate() per porre il risultato di una chiamata alla funzione generatore

nextLetter in ogni elemento del vettore chars da chars.begin() a chars.end() escluso. Gli

iteratori forniti come primo e secondo argomento devono essere (almeno) iteratori forward. La

funzione nextLetter (definita alla linea 39) inizia con il carattere ’A’ mantenuto in una variabile

locale static. L’istruzione di linea 42

return letter++;

restituisce il valore corrente di letter a ogni chiamata di nextLetter, quindi incrementa il valore

di letter.

La linea 30

generate_n( chars.begin(), 5, nextLetter );

n() per porre il risultato di una chiamata alla funzione generatore

utilizza la funzione generate

nextLetter in cinque elementi del vettore chars a partire da chars.begin(). L’iteratore fornito

come primo argomento deve essere (almeno) un iteratore di output.

43

5.2 equal, mismatch e lexicographical compare

Il programma in codice11.cpp mostra il confronto di sequenze di valori tramite le funzioni della

STL equal(), mismatch() e lexicographical compare().

1 // codice11.cpp

2 // Esempio di utilizzo delle funzioni equal(),

3 // mismatch(), lexicographical_compare().

4 #include <iostream>

5 #include <algorithm>

6 #include <vector>

7

8 using namespace std;

9

10 int main()

11 {

12 const int SIZE = 10;

13 int al[ SIZE ] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

14 int a2[ SIZE ] = { 1, 2, 3, 4, 1000, 6, 7, 8, 9, 10 };

15 vector< int > v1( a1, a1 + SIZE ),

16 v2( a1, a1 + SIZE ),

17 v3( a2, a2 + SIZE );

18 ostream_iterator< int > output( cout, " ");

19

28 cout << "Il vettore v1 contiene: ";

21 copy( v1.begin(), v1.end(), output );

22 cout << "\nIl vettore v2 contiene: ";

23 copy( v2.begin(), v2.end(), output );

24 cout << "\nIl vettore v3 contiene: ";

25 copy( v3.begin(), v3.end(), output );

26

27 bool result = equal( v1.begin(), v1.end(), v2.begin() );

28 cout << "\nIl vettore v1 " << ( result ? "e’" : "non e’" )

29 << " uguale al vettore v2.\n";

38

31 result = equal( v1.begin(), v1.end(), v3.begin() );

32 cout << "Il vettore v1 " << ( result ? "e’" : "non e’" )

33 << " uguale al vettore v3.\n";

34

35 pair< vector< int >::iterator,

36 vector< int >::iterator > location;

37 location mismatch( v1.begin(), v1.end(), v3.begin() );

38 cout << "C’e’ un mismatch tra v1 e v3 alla"

39 << "locazione " << ( location.first - v1.begin() )

48 << ", dove v1 contiene " << *location.first

41 << " e v3 contiene " << *location.second

42 << "\n";

43 44

44 char cl[ SIZE ] = "HELLO", c2[ SIZE ] = "BYE BYE";

45

46 result = lexicographical_compare( c1, c1 + SIZE, c2, c2 + SIZE );

48 cout << c1

49 << ( result ? " e’ minore di " : " e’ maggiore di " )

58 << c2;

51

52 cout << endl;

53 return 0;

54 }

Esecuzione:

Il vettore v1 contiene: 1 2 3 4 5 6 7 8 9 10

Il vettore v2 contiene: 1 2 3 4 5 6 7 8 9 10

Il vettore v2 contiene: 1 2 3 4 1000 6 7 8 9 10

Il vettore v1 e’ uguale al vettore v2

Il vettore v1 non e’ uguale al vettore v3

C’e’ un mismatch tra v1 e v3 alla locazione 4, dove v1 contiene 5 e v3 contiene 1000

HELLO e’ maggiore di BYE BYE

La linea 27

bool result = equal( v1.begin(), v1.end(), v2.begin() );

utilizza la funzione equal() per verificare l’uguaglianza di due sequenze di valori. Ogni sequenza

non deve contenere necessariamente lo stesso numero di elementi: equal() restituisce false se

le sequenze non sono della stessa lunghezza. La funzione operator== effettua il confronto degli

elementi. In questo esempio sono confrontati gli elementi in vector v1 a partire da v1.begin() fino

a v1.end() escluso e gli elementi in vector v2 a partire da v2.begin() (in questo esempio v1 e v2

sono uguali). I tre argomenti devono essere (almeno) iteratori di input (cioè possono essere utilizzati

nell’input da una sequenza in avanti). La linea 31 utilizza la funzione equal() per confrontare i

vector v1 e v3, che non risultano uguali.

C’è un’altra versione della funzione equal() che prende una funzione predicativa binaria come

quarto parametro. La funzione predicativa riceve due elementi da confrontare e restituisce un valore

bool che indica se gli elementi sono uguali. Ciò è utile nelle sequenze di puntatori a valori anziché

di valori effettivi, perché è possibile definire un confronto su ciò a cui puntano i puntatori anziché

sugli stessi puntatori (ovvero sugli indirizzi che contengono).

Le linee 35-37

pair< vector< int >::iterator,

vector< int >::iterator > location;

location mismatch( v1.begin(), v1.end(), v3.begin() );

istanziano un pair di iteratori di nome location per un vector di interi. Questo oggetto memo-

rizza il risultato della chiamata a mismatch() alla linea 37. La funzione mismatch() confronta

due sequenze di valori e restituisce un pair di iteratori che indica la posizione in ogni sequenza

degli elementi diversi. Se tutti gli elementi sono uguali, i due iteratori in location sono uguali

all’ultimo iteratore di ogni sequenza. I tre argomenti devono essere (almeno) iteratori di input.

45

Per determinare la posizione effettiva della disuguaglianza nei vector di questo esempio, viene uti-

lizzata l’espressione di linea 39 location.first - v1. begin(). Il risultato di questo calcolo

è il numero di elementi che separano gli iteratori. Ciò corrisponde all’elemento number in questo

esempio, perché il confronto viene effettuato dall’inizio di ciascun vector.

Come per la funzione equal(), c’è un’altra versione di mismatch() che prende una funzione

predicativa binaria come quarto parametro.

Le linea 46

result = lexicographical_compare( c1, c1 + SIZE, c2, c2 + SIZE );

utilizza la funzione lexicographical compare() per confrontare il contenuto di due array di

caratteri. I quattro argomenti di questa funzione devono essere (almeno) iteratori di input.

Come sapete, i puntatori in array sono iteratori ad accesso casuale. I primi due argomenti

iteratore specificano l’intervallo di posizioni nella prima sequenza. Gli ultimi due argomenti iteratore

specificano l’intervallo di posizioni nella seconda sequenza. Nell’attraversamento della sequenza

tramite gli iteratori, se un elemento della prima sequenza è minore dell’elemento corrispondente

nella seconda sequenza, la funzione restituisce true. Se l’elemento nella prima sequenza è maggiore

o uguale all’elemento nella seconda sequenza, la funzione restituisce false. Questa funzione si può

anche utilizzare per porre le sequenze in ordine lessicografico. Sequenze del genere conterranno

tipicamente stringhe.

5.3 remove, remove if, remove copy e remove copy if

Il programma in codice12.cpp mostra l’eliminazione da una sequenza tramite le funzioni della

if(), remove copy() e remove copy if().

STL remove(), remove

1 // codice12.cpp

2 // Esempio di utilizzo delle funzioni remove(), remove_if()

3 // remove_copy() and remove_copy_if()

4 #include <iostream>

5 #include <algorithm>

6 #include <vector>

7

8 using namespace std;

9

10 bool greater9( int );

11

12 int main()

13 {

14 const int SIZE = 10;

15 int a[ SIZE ] = { 10, 2, 10, 4, 16, 6, 14, 8, 12, 10 };

16 ostream_iterator< int > output( cout, " " );

17

18 // Rimuove 10 da v

19 vector< int > v( a, a + SIZE );

20 vector< int >::iterator newLastElement;

21 cout << "Il vettore v prima di rimuovere tutti i 10:\n";

22 copy( v.begin(), v.end(), output );

46

23 newLastElement = remove( v.begin(), v.end(), 10 );

24 cout << "\nIl vettore v dopo aver rimosso tutti i 10:\n";

25 copy( v.begin(), newLastElement, output );

26

27 // Copia da v2 a c, remuove i 10

28 vector< int > v2( a, a + SIZE );

29 vector< int > c( SIZE, 0 );

30 cout << "\n\nIl vettore v2 prima di rimuovere tutti i 10:"

31 << "e copiare:\n";

32 copy( v2.begin(), v2.end(), output );

33 remove_copy( v2.begin(), v2.end(), c.begin(), 10 );

34 cout << "\nIl vettore c dopo aver elim. tutti i 10 da v2:\n";

35 copy( c.begin(), c.end(), output );

36

37 // Rimuove gli elementi maggiori di 9 da v3

38 vector< int > v3( a, a + SIZE );

39 cout << "\n\nIl vettore v3 prima di rimuovere tutti gli"

40 << "\nelementi maggiori di 9:\n";

41 copy( v3.begin(), v3.end(), output );

42 newLastElement =

43 remove_if( v3.begin(), v3.end(), greater9 );

44 cout << "\nIl vettore v3 dopo aver rimosso tutti gli elementi"

45 << "\nmaggiori di 9:\n";

46 copy( v3.begin(), newLastElement, output );

47

48 // Copia degli elementi da v4 a c2,

49 // con rimozione degli elementi maggiori di 9

50 vector< int > v4( a, a + SIZE );

51 vector< int > c2( SIZE, 0 );

52 cout << "\n\nIl vettore v4 prima della rimozione di tutti gli"

53 << "\n elementi maggiori di 9 e copia:\n";

54 copy( v4.begin(), v4.end(), output );

55 remove_copy_if( v4.begin(), v4.end(),

56 c2.begin(), greater9 );

57 cout << "\nIl vettore c2 dopo la rimozione di tutti gli "

58 << "\nelementi maggiori di 9 da v4:\n";

59 copy( c2.begin(), c2.end(), output );

60

61 cout << endl;

62 return 0;

63 }

64

65 bool greater9( int x )

66 {

67 return x > 9;

68 } 47

Esecuzione:

Il vettore v prima di rimuovere tutti i 10:

10 2 10 4 16 6 14 8 12 10

Il vettore v dopo aver rimosso tutti i 10:

2 4 16 6 14 8 12

Il vettore v2 prima di rimuovere tutti i 10 e copiare:

10 2 10 4 16 6 14 8 12 10

Il vettore c dopo aver elim. tutti i 10 da v2:

2 4 16 6 14 8 12 0 0 0

Il vettore v3 prima di rimuovere tutti gli elementi maggiori di 9:

10 2 10 4 16 6 14 8 12 10

Il vettore v3 dopo aver rimosso tutti gli elementi maggiori di 9:

2 4 6 8

Il vettore v4 prima della rimozione di tutti gli elementi maggiori di 9 e copia:

10 2 10 4 16 6 14 8 12 10

Il vettore c2 dopo la rimozione di tutti gli elementi maggiori di 9 da v4:

2 4 6 8 0 0 0 0 0 0

La linea 23

newLastElement = remove( v.begin(), v.end(), 10 );

utilizza la funzione remove() per eliminare dal vettore v tutti gli elementi con valore 10 nell’inter-

vallo da v.begin() a v.end() escluso. I primi due argomenti devono essere iterarori forward, in

modo che l’algoritmo possa modificare gli elementi nella sequenza. Questa funzione non modifica il

numero di elementi nel vector né distrugge gli elementi eliminati, ma sposta tutti gli elementi non

eliminati verso l’inizio del vector. La funzione restituisce un iteratore posizionato dopo l’ultimo

elemento del vector che non è stato eliminato. Gli elementi dalla posizione dell’iteratore alla fine

del vector hanno valori “indefiniti” (in questo esempio, ogni posizione indefinita ha valore 0). La

linea 33

remove_copy( v2.begin(), v2.end(), c.begin(), 10 );

utilizza la funzione remove copy() per copiare dal vector v2 tutti gli elementi che non hanno valore

10 nell’intervallo da v2.begin() a v2.end() escluso. Gli elementi sono posti nel vector c a partire

dalla posizione c.begin(). Gli iteratori forniti come primi due argomenti devono essere iteratori

di input. L’iteratore fornito come terzo argomento deve essere un iteratore di output, in modo che

gli elementi copiati possano essere inseriti nella posizione della copia. Questa funzione restituisce

un iteratore posizionato dopo l’ultimo elemento copiato nel vector c. Notate alla linea 29 l’uso del

costruttore del vector che riceve il numero di elementi del vector ed il valore iniziale di tali elementi.

Le linee 42 e 43

newLastElement =

remove_if( v3.begin(), v3.end(), greater9 );

48

utilizzano la funzione remove if() per eliminare dal vector v3 tutti gli elementi dell’intervallo da

v3.begin() a v3.end() escluso per cui la funzione predicativa unaria definita dall’utente greater9

restituisce true. La funzione greater9 è definita alla linea 64 e restituisce true se il valore passatole

è maggiore di 9 e restituisce false altrimenti. Gli iteratori forniti come primi due argomenti devono

essere iteratori forward, in modo che l’algoritmo possa modificare gli elementi nella sequenza.

Questa funzione non modifica il numero di elementi nel vector, ma sposta verso l’inizio del vector

tutti gli elementi che non sono stati eliminati. Questa funzione restituisce un iteratore posizionato

dopo l’ultimo elemento nel vector che non è stato eliminato. Tutti gli elementi a partire dalla

posizione iteratore fino alla fine del vector hanno valore indefinito.

Le linee 55 e 56

remove_copy_if( v4.begin(), v4.end(),

c2.begin(), greater9 );

utilizzano la funzione remove copy if() per copiare dal vector v4 tutti gli elementi dell’intervallo

da v4.begin() a v4.end() escluso per cui la funzione predicativa unaria greater9 restituisce true.

Gli elementi sono posti nel vector c2 a partire dalla posizione c2.begin(). Gli iteratori forniti come

primi due argomenti devono essere iteratori di input. L’iteratore fornito come terzo argomento deve

essere un iteratore di output, in modo che l’elemento da copiare sia inserito nella posizione di copia.

Questa funzione restituisce un iteratore posizionato dopo l’ultimo elemento copiato nel vector c2.

5.4 replace, replace if, replace copy e replace copy if

Il programma in codice13.cpp mostra la sostituzione di valori da una sequenza tramite le funzioni

if(), replace copy() e replace copy if().

della STL replace(), replace

1 // codice13.cpp

2 // Esempio di utilizzo delle funzioni replace(), replace_if()

3 // replace_copy() and replace_copy_if()

4 #include <iostream>

5 #include <algorithm>

6 #include <vector>

7

8 using namespace std;

9

10 bool greater9( int );

11

12 int main()

13 {

14 const int SIZE = 10;

15 int a[ SIZE ] = { 10, 2, 10, 4, 16, 6, 14, 8, 12, 10 };

16 ostream_iterator< int > output( cout, " " );

17

18 // Sostituisce i 10 in v1 con 100

19 vector< int > v1( a, a + SIZE );

20 cout << "Il vettore v1 prima della sostituzione di tutti i 10:\n";

21 copy( v1.begin(), v1.end(), output );

22 replace( v1.begin(), v1.end(), 10, 100 );

49

23 cout << "\nIl vettore v1 dopo la sostituzione di tutti i 10 con 100:\n";

24 copy( v1.begin(), v1.end(), output );

25

26 // Copia da v2 a c1, sostituendo i 10 con 100

27 vector< int > v2( a, a + SIZE );

28 vector< int > c1( SIZE );

29 cout << "\n\nIl vettore v2 prima della sostitituzione di "

30 << "tutti i 10 e della copia:\n";

31 copy( v2.begin(), v2.end(), output );

32 replace_copy( v2.begin(), v2.end(),

33 c1.begin(), 10, 100 );

34 cout << "\nIl vettore c1 dopo la sostituzione di tutti i 10 in v2:\n";

35 copy( c1.begin(), c1.end(), output );

36

37 // Sostituzione dei valori maggiori di 9 in v3 con 100

38 vector< int > v3( a, a + SIZE );

39 cout << "\n\nIl vettore v3 prima della sostituzione dei valori"

40 << " maggiori di 9:\n";

41 copy( v3.begin(), v3.end(), output );

42 replace_if( v3.begin(), v3.end(), greater9, 100 );

43 cout << "\nIl vettore v3 dopo la sostituzione dei valori "

44 << "\nmaggiori di 9 con 100:\n";

45 copy( v3.begin(), v3.end(), output );

46

47 // Copia da v4 a c2, sostituendo gli elementi maggiori di 9 con 100

48 vector< int > v4( a, a + SIZE );

49 vector< int > c2( SIZE );

50 cout << "\n\nIl vettore v4 prima della sostituzione dei "

51 << "\nvalori maggiori di 9 e di copiare:\n";

52 copy( v4.begin(), v4.end(), output );

53 replace_copy_if( v4.begin(), v4.end(), c2.begin(),

54 greater9, 100 );

55 cout << "\nIl vettore c2 dopo la sostituzione di tutti i "

56 << "\n valori maggiori di 9 in v4:\n";

57 copy( c2.begin(), c2.end(), output );

58

59 cout << endl;

60 return 0;

61 }

62

63 bool greater9( int x )

64 {

65 return x > 9;

66 }

Esecuzione:

Il vettore v1 prima di sostituzione tutti i 10:

50

10 2 10 4 16 6 14 8 12 10

Il vettore v1 dopo la sostituzione di tutti i 10 con 100:

100 2 100 4 16 6 14 8 12 100

Il vettore v2 prima della sostitituzione di tutti i 10 e della copia:

10 2 10 4 16 6 14 8 12 10

Il vettore c1 dopo la sostuzione di tutti i 10 in v2:

100 2 100 4 16 6 14 8 12 100

Il vettore v3 prima della sostituzione dei valori maggiori di 9:

10 2 10 4 16 6 14 8 12 10

Il vettore v3 dopo la sostituzione dei valori maggiori di 9 con 100:

100 2 100 4 100 6 100 8 100 100

Il vettore v4 prima della sostituzione dei valori maggiori di 9 e di copiare:

10 2 10 4 16 6 14 8 12 10

Il vettore c2 dopo la sostituzione di tutti i valori maggiori di 9 in v4:

100 2 100 4 100 6 100 8 100 100

La linea 22

replace( v1.begin(), v1.end(), 10, 100 );

utilizza la funzione replace() per sostituire tutti gli elementi con valore 10 dell’intervallo da

v1.begin() a v1.end() escluso del vector v1 con il nuovo valore 100. Gli iteratori forniti come

primi due argomenti devono essere iteratori forward, in modo che l’algoritmo possa modificare gli

elementi nella sequenza.

Le linee 32 e 33

replace_copy( v2.begin(), v2.end(),

c1.begin(), 10, 100 );

utilizzano la funzione replace copy() per copiare tutti gli elementi nell’intervallo da v2.begin()

a v2.end() escluso dal vector v2 sostituendo tutti gli elementi con valore 10 con il nuovo valore

100. Gli elementi sono copiati nel vector c1 a partire dalla posizione c1.begin(). Gli iteratori

forniti come primi due argomenti devono essere iteratori di input. L’iteratore fornito come terzo

argomento deve essere un iteratore di output, in modo che l’elemento da copiare sia inserito nella

posizione di copia. Questa funzione restituisce un iteratore posizionato dopo l’ultimo elemento

copiato nel vector c2.

La linea 42

replace_if( v3.begin(), v3.end(), greater9, 100 );

if() per sostituire tutti gli elementi dell’intervallo da v3.begin() a

utilizza la funzione replace

v3.end() escluso per cui la funzione predicativa unaria greater9 restituisce true. La funzione

greater9 è definita alla linea 63 e restituisce true se il valore passatole è maggiore di 9 e false

altrimenti. Il valore 100 sostituisce ogni valore maggiore di 9. Gli iteratori forniti come primi due

argomenti devono essere iteratori forward, in modo che l’algoritmo possa modificare gli elementi

nella sequenza.

Le linee 53 e 54 51

replace_copy_if( v4.begin(), v4.end(), c2.begin(),

greater9, 100 );

utilizzano la funzione replace copy if() per copiare tutti gli elementi nell’intervallo da v4.begin()

a v4.end() escluso dal vector v4. Gli elementi per cui la funzione predicativa unaria greater9

restituisce true sono sostituiti con il valore 100. Gli elementi sono posti nel vector c2 a partire

dalla posizione c2.begin(). Gli iteratori forniti come primi due argomenti devono essere iteratori

di input. L’iteratore fornito come terzo argomento deve essere un iteratore di output, in modo che

l’elemento da copiare possa essere inserito nella posizione di copia. Questa funzione restituisce un

iteratore posizionato dopo l’ultimo elemento copiato nel vector c2.

5.5 Gli algoritmi numerici

Il programma in codice14.cpp mostra l’uso di alcuni comuni algoritmi numerici della STL tra cui

shuffle(), count(), count if(), min element(),max element(), accumulate(), for each()

random

e transform().

1 // codice14.cpp

2 // Esempi di algoritmi numerici nella STL.

3 #include <iostream>

4 #include <algorithm>

5 #include <numeric> // accumulate e’ definita qui

6 #include <vector>

7

8 using namespace std;

9

10 bool greater9( int );

11 void outputSquare( int );

12 int calculateCube( int );

13

14 int main()

15 {

16 const int SIZE = 10;

17 int a1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

18 vector< int > v( a1, a1 + SIZE );

19 ostream_iterator< int > output( cout, " " );

20

21 cout << "Il vettore v prima di random_shuffle(): ";

22 copy( v.begin(), v.end(), output );

23 random_shuffle( v.begin(), v.end() );

24 cout << "\nIl vettore v dopo random_shuffle(): ";

25 copy( v.begin(), v.end(), output );

26

27 int a2[] = { 100, 2, 8, 1, 50, 3, 8, 8, 9, 10 };

28 vector< int > v2( a2, a2 + SIZE );

29 cout << "\n\nIl vettore v2 contiene: ";

30 copy( v2.begin(), v2.end(), output );

31 int result = count( v2.begin(), v2.end(), 8 );

52


PAGINE

67

PESO

291.82 KB

AUTORE

Atreyu

PUBBLICATO

+1 anno fa


DESCRIZIONE DISPENSA

Il presente documento rappresenta una dispensa didattica. Il suo scopo è quello di fornire allo studente una introduzione alla Standard Template Library del C++. La dispensa pu`o essere considerata come materiale didattico integrativo per il corso di Programmazione ad Oggetti. Vengono trattati i seguenti argomenti. Container, iteratori, algoritmi. Adattatori di container. La classe bitset. Gli oggetti funzione. Specializzare i container mediante ereditarità.


DETTAGLI
Corso di laurea: Corso di laurea in ingegneria informatica e automatica
SSD:
Università: L'Aquila - Univaq
A.A.: 2011-2012

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Atreyu di informazioni apprese con la frequenza delle lezioni di Programmazione a oggetti e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università L'Aquila - Univaq o del prof Di Stefano Gabriele.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Programmazione a oggetti

Gestione File in C++
Dispensa
Tecnologia oggetti - Fondamenti
Dispensa
Ethernet - Le diverse famiglie di reti Ethernet
Dispensa
Tecnologia oggetti - Fondamenti
Dispensa