2011/2012 F. Mallet 4-1

Tableaux et Collections

F. MalletFrederic.Mallet@unice.fr

http://deptinfo.unice.fr/~fmallet/java/gse.html

Tableaux et collectionsTableaux et collections

2011/2012 F. Mallet 2

Chapitre IV – Objectifs

�Réutilisation� Types génériques

�Structures de contrôle� for-each

�Structures de données� Tableaux� Collections

• ArrayList

Tableaux et collectionsTableaux et collections

Tableaux

�Ensemble ordonnés d’éléments� Accès (lecture/écriture) en temps constant� Type unique choisi à la déclaration

• Type primitif• Classe (polymorphisme)

� Longueur statique choisie à la construction� Les tableaux sont des objets

• Tableaux de tableaux (≠ matrice)

2011/2012 F. Mallet 3

Tableaux et collectionsTableaux et collections

Tableaux : syntaxe

�Déclaration (référence)

� int [] t1; ou int t1[] ;� Compteur [] t2;

�Construction du tableau (pas de ses éléments)

� t1 = new int [ 10] ;

� t2 = new Compteur [ 5] ;

�Affectation de tableaux (pas de copie globale)

� Compteur [] t3 = t2;

�Longueur (statique)

� t3.length → 5

2011/2012 F. Mallet 4

Tableaux et collectionsTableaux et collections

Indice: accès aux éléments

�Lecture ou écriture� t1[ 0] = 24; t2[ 0] = new Compteur();

� t2[ 1] = new Compteur();

� t2[ 2] = new CompteurModulo( 12);

� t2[ 4] = t2[ 2] ; // copie de référence

2011/2012 F. Mallet 5

Tableaux et collectionsTableaux et collections

ArrayIndexOutOfBoundsException

�A chaque accès (lecture/écriture)� Les bornes sont vérifiées� => Pas d’accès non autorisé à la mémoire

�Example� int[] t = new int[ 5];

� t[ -1] => ArrayIndexOutOfBoundsException -1<0

� t[ 5] => ArrayIndexOutOfBoundsException 5>=5

2011/2012 F. Mallet 6

Tableaux et collectionsTableaux et collections

Parcourir les éléments

Compteur[] tab;

�Itération: forfor (int i = 0; i<tab.length ; i++)

tab[ i]. incrementer();

�Itération: for -eachfor (Compteur c : tab)

c. incrementer();

2011/2012 F. Mallet 7

Tableaux et collectionsTableaux et collections

Tableaux à plusieurs dimensions

�Déclaration� int [][] t4; // tableau de tableaux d’entiers

�Construction du tableau� t4 = new int [ 5][] ; // 5 tableaux d’entiers

�Utilisation� t4[ 0] = t1; // copie de références

� t4[ 1] = new int [ 3] ;

�Remarque� t4.length → 5� t4[ 0].length → 10 t4[ 1].length → 3

2011/2012 F. Mallet 8

Tableaux et collectionsTableaux et collections

Paramètres variables

Operation binaireinterface IOpBinaire{

int calcule(int v1, int v2);

}

class Addition

implements IOpBinaire {

int calcule(int v1, int v2){

return v1+v2;

}

}

new Addition().calcule( 5, 12 );

Opération N -aireinterface IOpNaire{

int calcule(int [] valeurs);

}

class Add implements IOpNaire {

int calcule(int [] valeurs){

int somme = 0;

for(int v : valeurs)

somme += v;

return somme;

}

}

new Add().calcule( new int[]{5,12} );

2011/2012 F. Mallet 9

Tableaux et collectionsTableaux et collections

Paramètres variables

Operation binaireinterface IOpBinaire{

int calcule(int v1, int v2);

}

class Addition

implements IOpBinaire {

int calcule(int v1, int v2){

return v1+v2;

}

}

new Addition().calcule( 5, 12 );

Opération N -aireinterface IOpNaire{

int calcule(int … valeurs);

}

class Add implements IOpNaire {

int calcule(int … valeurs){

int somme = 0;

for(int v : valeurs)

somme += v;

return somme;

}

}

new Add().calcule( 5,12,40,-5 );

2011/2012 F. Mallet 10

Tableaux et collectionsTableaux et collections

Classe utilitaire : java.util. Arrays

�Manipulations courantes de tableaux� Recherche: int binarySearch (T[] tab, T val);

� Copy: T[] copyOf (T[] tab, int newLength);

� Comparaison: boolean equals (T[] t1, T[] t2);

� Remplissage: void fill (T[] tab, T val);

� Trie: void sort (T[] tab)

� Affichage: String toString (T[] tab);

�Remplacer T selon le type� boolean, char, byte, short, int, long, float,

double, Object

2011/2012 F. Mallet 11

Tableaux et collectionsTableaux et collections

java.util.Collection

�Groupe d’éléments� capacité extensible� taille dynamique� Les collections sont des objets

�Différentes interfaces� Ensemble java.util. Set

� Liste java.util. List

• Ensemble ordonné, accès par indice

� Files (double sens) java.util. Queue (Deque)

� Table association (clé/valeur) java.util. Map

2011/2012 F. Mallet 12

Tableaux et collectionsTableaux et collections

Classes concrètes

�Ensemble java.util. Set java.util. SortedSet

� Table de hachage : java.util. HashSet

� Arbre balancé : java.util. TreeSet

� Hachage + liste chaînée : java.util. LinkedHashSet

�Liste java.util. List

� Tableau à capacité variable : java.util. ArrayList

� Liste chaînée : java.util. LinkedList

2011/2012 F. Mallet 13

Tableaux et collectionsTableaux et collections

Classes concrètes

�File java.util. Queue java.util. Deque

� Tableau à capacité variable : java.util. ArrayDeque

� Liste chaînée : java.util. LinkedList

�Table d’association java.util. Map,java.util. SortedMap

� Table de hachage : java.util. HashMap

� Arbre balancé : java.util. TreeMap

� Hachage + liste chaînée : java.util. LinkedHashMap

2011/2012 F. Mallet 14

Tableaux et collectionsTableaux et collections

Collections : syntaxe

�Déclaration (référence)

� java.util.ArrayList liste1;

�Construction d’une liste (pas de ses éléments)

� t1 = new java.util.ArrayList () ;

�Affectation de collections (pas de copie globale)

� java.util.ArrayList liste2 = liste1;

�Taille (dynamique)

� liste1.size() → 0

2011/2012 F. Mallet 15

Tableaux et collectionsTableaux et collections

Opérations

�Ajout� liste1. add( new Compteur() ) ;

� liste1. add( new ComplexeCartesien( 0,1) ) ;

�Accès en lecture (par indice)� Object o1 = liste1. get( 0) ;

� ((Compteur) o1) .incrementer();

� Object o2 = liste1. get( 1) ;

� ((Compteur) o2) .incrementer();

�Accès en écriture (par indice)� liste1. set( 0, new CompteurRapide( o1, 10) ) ;

� liste1. set( 1, o1) ;

2011/2012 F. Mallet 16

ClassCastException

Tableaux et collectionsTableaux et collections

Paquetage

�Classes regroupées par thèmes� java.util, java.awt, java.lang, …

�La directive import

� Avant le bloc de déclaration de classe

� Example:import java.util.ArrayList;

class Toto {

ArrayList liste1 = new ArrayList();

}

2011/2012 F. Mallet 17

Tableaux et collectionsTableaux et collections

Collections génériques : syntaxe

�Déclaration (référence)� ArrayList <ICompteur> compteurs;

�Construction� compteurs = new ArrayList <ICompteur>() ;

�Ajout� compteurs. add( new Compteur() ) ;

� compteurs. add( new ComplexeCartesien( 0,1) ) ;

�Accès en lecture (par indice)� ICompteur c1 = compteurs. get( 0) ;

� c1.incrementer();

2011/2012 F. Mallet 18

ICompteur c

Tableaux et collectionsTableaux et collections

Parcours des élémentsArrayList compteurs = new ArrayList(); …

�Par indice (seulement pour les listes)for(int i = 0; i<compteurs.size(); i++) {

ICompteur c = (ICompteur) compteurs.get( i);

c.incrementer();

}

�For-each : itérateursfor(Object c : compteurs) {

((ICompteur) c).incrementer();

}

2011/2012 F. Mallet 19

Tableaux et collectionsTableaux et collections

Parcours des élémentsArrayList<ICompteur> compteurs; …

�Par indice (seulement pour les listes)for(int i = 0; i<compteurs.size(); i++) {

ICompteur c = compteurs.get( i);

c.incrementer();

}

�For-each : itérateursfor(ICompteur c : compteurs) {

c.incrementer();

}

2011/2012 F. Mallet 20

Tableaux et collectionsTableaux et collections

Parcours des éléments

�Interface java.util. Iterator

interface Iterator< T> {

boolean hasNext();

T next();

void remove();

}

�UsageCollection<ICompteur> compteurs = …;

Iterator<ICompteur> it = compteurs.iterator();

while( it.hasNext()) {

ICompteur c = it.next();

c.incrementer();

}

2011/2012 F. Mallet 21

Tableaux et collectionsTableaux et collections

Auto (un)boxing

�Avec les types primitifs ?� ArrayList<int> listeEntiers;

� ArrayList<Integer> listeEntiers;

�Ajout d’éléments� listeEntiers.add(new Integer( 12));

� listeEntiers.add( 12);

�Lecture� int v = listeEntiers.get(0).intValue();

� int v = listeEntiers.get(0);

2011/2012 F. Mallet 22

Auto boxing

Integer

Auto unboxing

Tableaux et collectionsTableaux et collections

Classe utilitaire : java.util. Collections

�Manipulations courantes de tableaux� Recherche: int binarySearch (List<T> li, T val);

T min (Collection<T> c);

T max(Collection<T> c);

� Copy: void copy (List<T> l1, List<T> l2);

� Comparaison: boolean disjoint (List<T> l1, List<T> l2);

� Remplissage: void fill (List<T> li, T val);

� Divers: void replaceAll (List<T> li, T old, T new);

void reverse (List<T> li);

void rotate (List<T> li, int distance);

void shuffle (List<T> li);

� Trie: void sort (List<T> li)

2011/2012 F. Mallet 23

Tableaux et collectionsTableaux et collections

Collections: JDK 1.1

�JDK 1.1� java.util. Vector => java.util. ArrayList

� java.util. Enumeration => java.util. Iterator

� java.util. HashTable => java.util. HashMap

� Thread-safeList<T> Collections.synchronizedList(List<T> l)

�Types génériques� Java 5(JDK 1.5)

2011/2012 F. Mallet 24