Understanding Java Collections: Overview and Implementation

Map : interface qui d finit des m thodes pour des objets qui g rent des collections

sous la forme cl /valeur. Attention, ce nest pas un sous-type de collection !

SortedMap : interface qui tend l'interface Map et permet d'ordonner l'ensemble.

Un tableau associatif avec une relation d'ordre sur les cl s.

ConcurrentMap : interface qui tend l'interface Map pour une association acc s

concurrent

http://docs.oracle.com/javase/7/docs/api/java/util/Collection.html

http://docs.oracle.com/javase/tutorial/collections/interfaces/index.html

S

8

Collection<E> et types param tr s

• Toutes les collections sont des types param tr s par le type des l ments

(E) qu'elles contiennent

• Les collections sont des conteneurs homog nes
• Si l'on veut stocker des l ments de types diff rents, on utilise le super-

type commun, voir Object

9

Propri t s des collections

Sauf exceptions :

• Toutes les collections acceptent null comme un l ment valide
• Toutes les collections testent si un objet existe ou non par rapport la m thode

equals() de l'objet

• Toutes les collections ne permettent pas les acc s concurrents

Op rations optionnelles

• Certaines m thodes des collections sont des op rations optionnelles (signal es

par un - exemple : boolean add(E e))

• Celles-ci peuvent ne pas tre implant es par exemple pour d finir des collections

immutables exemple : ImmutableList

• Les op rations optionnelles non implant es l vent l'exception

UnsupportedOperationException

10

Les types g n riques

Les types g n riques permettent de sp cifier le type d'objets que l'on va

placer dans une collection d'objets (List, Vector,...)

Avantages:

• meilleure lisibilit : on conna t la lecture du programme quel type

d'objets seront plac s dans la collection.

• La v rification peut tre faite la compilation.
• Le cast pour r cup rer un objet de la collection est devenu implicite

(sans cette fonctionnalit , il fallait faire un cast explicite, sachant que

celui-ci peut chouer mais cela n' tait d tectable qu'a l'ex cution)

La syntaxe pour utiliser les types g n riques utilise les symboles < et >.

11

La g n ricit

• Une m thode peut tre param tr e avec des valeurs.

• La g n ricit permet de param trer du code avec des types de donn es.

Exemple :

class ArrayList<T>

• Ici le code est param tr par un type T

• Pour l'utiliser il faut passer un type en argument :

new ArrayList<Employe>()

S

12

L'interface java.util.Collection

Collection : super-type des structures de donn es de Java (sauf Map)

Avant Java 1.5, les l ments dune collection taient du type Object

Depuis 1.5, les collections sont param tr es par E, type des l ments

Une collection peut autoriser ou non plusieurs occurrences dun m me

l ment (List vs Set)

Les l ments peuvent tre ordonn s (position) ou non (List vs Set)

Les l ments peuvent tre tri s ou non (Set vs SortedSet)

Pour limiter le nombre dinterfaces, certaines m thodes peuvent :

*ne pas tre d finies sur un sous-type (UnsupportedOperationException)

*lever ClassCastException (cf checkedList, etc.)

Toute r alisation dune Collection devrait d finir :

• un constructeur par d faut (qui cr e une collection vide) et
• un constructeur qui prend en param tre une collection (conversion)

13

Linterface java.util.Collection<E>

public interface Collection<E> extends Iterable<E> {

// Basic operations

int size();

boolean isEmpty();

boolean contains(Object element);

// optional

boolean add(E element);

// optional

boolean remove(Object element);

Iterator<E> iterator();

// Bulk operations

boolean containsAll(Collection<?> c);

// optional

boolean addAll(Collection<? extends E> c);

// optional

boolean removeAll(Collection<?> c);

// optional

boolean retainAll(Collection<?> c);

// optional

void clear();

// Array operations

Object[] toArray();

<T> T[] toArray(T[] a);

}

http://docs.oracle.com/javase/tutorial/collections/interfaces/collection.html

14

Taille et effacement

• L'interface d finit les m thodes :

int size() indiquant la taille d'une collection

boolean isEmpty() indiquant si une collection est vide.

void clear*() permettant d'effacer les donn es de la collection

Modification et test de contenue

• Les modifications et tests sont effectu es par :

boolean add*(E e) ajoute un l ment la collection, true si la collection

est modifi e

boolean remove*(Object o) retire un objet, true si la collection est

modifi e

boolean contains(Object) renvoie si la collection contient

l'objet

• remove() et contains() prennent en param tre des Object et non des E par

compatibilit

15

l ments et equals

Toutes les collections sauf exception (AbstractCollection par exemple)

testent si un objet existe en utilisant la m thode equals() de l'objet

16

Iterator

Supposons que nous ayons rang des tudiants dans un tableau. L'affichage de

l'ensemble des tudiants se ferait de la mani re suivante :

for (int i=0; i< tabEtuds.length; i++)

System.out.println(tabEtuds );

Supposons que nous ayons cr un type liste d' tudiants . Nous le parcourrions

de la mani re suivante :

for (ListeEtud l= listeEtuds; l != null; l= l.next)

System.out.println(l.getEtud());

Du point de vue de l'impl mentation, ces deux approches sont tr s diff rentes. Par

contre, du point de vue de l'utilisation, on remarque que l et i sont similaires. Ils

disposent chacun des fonctionnalit s suivantes :

on les initialise au d but de l'ensemble (i=0, l= listeEtuds) ;

on dispose d'un op rateur pour passer l' l ment suivant : (i++ et l=

l.next) ;

on dispose d'un test d'arr t : i < tabEtuds.length et l != null ;

on dispose d'une op ration pour r cup rer l' l ment courant : tabEtuds et

l.getEtud().

17

suite ...

De plus, ces quatre op rations permettent conceptuellement de parcourir n'importe

quel ensemble.

En java, ce concept est actualis par l'interface Iterator. Le code pr c dent peut

alors s' crire, pour n'importe quelle collection, de la mani re suivante :

for (Iterator i= promotion.iterator(); i.hasNext(); )

{

Etudiant e= (Etudiant) i.next();

System.out.println(e);

}

Remarquez que c'est promotion qui construit l'it rateur. C'est encore un usage de

l'h ritage !

Les op rations vues pr c demment tant repr sent es comme suit :

Cr ation, initialisation La cr ation d'un it rateur est effectu e par la collection elle-

m me, par l'appel de la m thode iterator() ;

R cup ration de l' l ment courant et avancement La m thode next() renvoie

la valeur de l' l ment courant, puis avance d'un cran.

Test d'arr t La m thode hasNext retourne vrai s'il est possible d'appeler next()

18

Pour r sumer

• Pour parcourir une collection, on utilise un objet permettant de passer en revue

les diff rents l ments de la collection

• java.util.Iterator<E> :

boolean hasNext() qui renvoie vrai s'il y a un suivant

E next() qui renvoie l' l ment courant et d cale sur l' l ment suivant

void remove() qui retire un l ment pr c demment envoy par next()

next() et NoSuchElementException

L'op ration next() est s curis e et l ve une exception dans le cas o on

d passe la fin de la collection (c-a-d si hasNext() renvoie false)

19

Organisation des interfaces

L'organisation de l'arbre d'h ritage pour les collections est le suivant :

(les interfaces d finissent les grandes lignes de ce que peut faire une collection)

interface java.util.Collection

interface java.util.List

interface java.util.Queue

interface java.util.Deque

interface java.util.Set

interface java.util.SortedSet

interface java.util.Map

interface java.util.SortedMap

interface java.util.ConcurrentMap

.

.

.

20

Organisation des classes

class java.util.AbstractCollection (implements

java.util.Collection)

class java.util.AbstractList (implements java.util.List)

class java.util.AbstractSequentialList

class java.util.LinkedList (implements java.util.List)

class java.util.ArrayList (implements java.util.List)

class java.util.Vector (implements java.util.List)

class java.util.Stack

class java.util.AbstractSet (implements java.util.Set)

class java.util.HashSet (implements java.util.Set)

class java.util.TreeSet (implements java.util.SortedSet)

class java.util.AbstractMap (implements java.util.Map)

class java.util.HashMap (implements java.util.Map)

class java.util.TreeMap (implements java.util.SortedMap)

class java.util.WeakHashMap (implements java.util.Map)

.

.

.

21

Pour comprendre

les listes (List) sont des suites d' l ments. On peut, soit les parcourir du

premier au dernier, soit acc der au i me l ment ;

les ensembles (Set) ne comportent pas de doublets. Un l ment appartient un

ensemble ou ne lui appartient pas. Contrairement aux listes, on ne peux pas choisir

o ins rer un l ment. Les SortedSet sont des ensembles tri s, c'est- -dire que

les l ments seront rang s du plus petit au plus grand (selon la m thode

compareTo).

les dictionnaires (Map) sont des tableaux associatifs. C'est- -dire des tableaux

dont les indices sont d'un type quelconque. On peut par exemple avoir comme

indice une cha ne de caract res, et crire des choses comme :

definitions.put("chauve-souris", "mammif re insectivore volant");

Map.Entry, permet de manipuler un dictionnaire comme un ensemble (Set) de

d nitions.

22

En ce qui concerne les classes, elles fournissent des impl mentations de ces

interfaces. Le choix de la classe utilis e d pend de l'usage que l'on veut en

faire.

LinkedList fournit une liste doublement cha n e. L'ajout d'un l ment est

rapide, mais la recherche d'une valeur donn e et l'acc s au ie l ment sont en

O(n).

ArrayList est une impl mentation base de tableau. L'ajout d'un l ment

peut tre plus co teux que dans le cas d'une LinkedList si le tableau doit

grossir, mais par contre l'acc s au i me l ment est en temps constant.

Vector est un quivalent de ArrayList datant du jdk1.0. Les diff rences

entre les deux se situent surtout lorsque l'on utilise le multit che (Vector est

synchronis , c.f. cours Threads).

Stack est un type sp cial de vecteur, utilis pour r aliser des piles. Les

piles sont des structures de donn es tr s utiles.

23

Pour le reste :

Hash signifie que l'impl mentation utilise un algorithme de hachage : elle

associe chaque l ment un nombre (par exemple, on pourrait associer

une cha ne de caract res la somme des codes des caract res qu'elle

contient), et elle utilise ce nombre comme indice dans un tableau. Les

impl mentations par hachage sont g n ralement tr s rapides pour des

volumes moyens de donn es. Par contre, elles ne permettent pas de

r cup rer les l ments dans l'ordre.

Tree signifie que l'impl mentation utilise un arbre. Les arbres sont des

structures tr s robustes, adapt es de grands volumes de donn es. De

plus, ils permettent de r cup rer les l ments dans l'ordre croissant.

24

L'interface java.util.List<E>

25

La classe ArrayList<E>

Tout comme LinkedList<E> (liste cha n e), ArrayList<E> implante

l'interface List. Elle est utiliser pour les tableaux taille variable.

Constructeurs

" ArrayList()

" ArrayList(int taille_initiale) : peut tre utile si on conna t la

taille finale ou initiale (apr s les premiers ajouts) la plus probable car vite

les op rations daugmentation de la taille du tableau sous-jacent

" ArrayList(Collection c) : pour linterop rabilit entre les diff rents

types de collections

M thodes principales

• boolean add(E elt)
• void add(int indice, E elt)
• boolean contains(Object obj)
• E get(int indice)
• int indexOf(Object obj)
• Iterator<E> iterator()
• E remove(int indice)
• E set(int indice, E elt)
• int size()

26

Exemple

List<Employe> le = new ArrayList<>();

Employe e = new Employe("Dupond");

le.add(e);

// Ajoute dautres employ s

//. . .

// Affiche les noms des employ s

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

System.out.println(le.get(i).getNom());

}

Pour aller plus vite :

for (Iterator i=le.iterator(); i.hasNext(); )

i.next().getNom();

27

La classe java.util.Vector<E>

28

La classe java.util.Vector<E>, suite ...

29

La classe java.util.Vector<E>, suite ...

" La manipulation des objets Vector est plus lente que celle des tableaux

" On ne peut y stocker que des objets (Object). Ils ne peuvent pas contenir

des primitifs.

" L'insertion d'un objet entra ne un sur-casting implicite

" L'utilisation d'un l ment du vecteur n cessite un sous-casting

Cr ation d'un vecteur

" Vector<Fraction> v ;

" v = new Vector<Fraction>();

v est de taille 10 et d'incr ment 1

l'incr ment est l'augmentation de la taille du vecteur une fois plein

" v = new Vector<Fraction>(int n);

v est de taille n

" v = new Vector<Fraction>(int n, int inc);

v est de taille n et d'incr ment inc

un incr ment 0 double la taille du vecteur

30

M thodes de Vector

" v.size() donne la taille du vecteur

" v.setSize(int n) modifie la taille de v

" v.addElement (Object obj) ajoute l' l ment obj

" v.setElementAt (Object obj,int n) modifie l' l ment n

" Object obj = v.elementAt(int n) extrait l' l ment n

31

Exemple

import java.util.*;

class DesEntiers {

static Vector<Integer> v;

static Random r = new Random();

public static void main (String [] args){

v = new Vector<Integer>();

for(int i =0; i<20;i++)

v.addElement( new Integer(r.nextInt()));

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

Integer obj = v.elementAt(i);

System.out.println(""+ obj.intValue());

}

}

}

32

Exercices

" Modifier l'exemple pr c dent pour cr er un vecteur de Boolean et Integer

al atoirement (le vecteur contient un m lange de ces objets) Imprimer les

l ments du vecteur

" Cr er un Vector de Voiture en cr ant al atoirement le nombre et les attributs

des objets Voiture

33

import java.util.*;

class DesEntiersEtBool ens {

static Vector v;

static Random r = new Random();

public static void main (String [] args){

v = new Vector(20, 0);

int n = r.nextInt(30);

for(int i =0; i<n;i++){

if(r.nextBoolean())

v.addElement( new Integer(r.nextInt()));

else

v.addElement( new Boolean(r.nextBoolean()));

}

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

Object obj = v.elementAt(i);

if(obj.getClass().getName().equals("java.lang.Integer")) {

System.out.println(""+ ((Integer)obj).intValue());

}

else {

System.out.println(""+ ((Boolean)obj).booleanValue());

}

}

}

}

}

34

import java.util.*;

class DesV hicules {

Vector<Voiture> v;

public static void main (String [] args){

Random r = new Random();

int n = 1+ r.nextInt(100);

for(int i =0; i<n;i++)

if(r.nextBoolean()){

Voiture f = new Voiture(3*r.nextFloat(),

3r.nextFloat(), 3r.nextFloat(),3*r.nextFloat());

v.addElement(f);

}

System.out.println(v);

}

}

35

36

37

38