2011/2012 F. Mallet 4-1
Tableaux et Collections
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