Supprimer les doublons dans un vecteur

Version imprimable

29/11/2007, 15h27
ecthelion

Supprimer les doublons dans un vecteur

Bonjour,

J'aurai aimé savoir si il y avait une méthode qui permettait de supprimer les doublons dans un vector.

Merci d'avance pour vos réponses!

Salut,

Non, ca n'existe pas.

deux solutions :
- faire une petite procedure qui recherce les doublons et les supprimes genre :
Code:

1 2 3 4 5 6 7 8 9 // code fait à l'arrache... faut sans doute retoucher. for(int i = vect.length-1;i>0;i--){ for(int j = vect.length-1;j>i;j--){ if(vect.get(i).equals(vect.get(j)) { vect.remove(j); } } }
- copier le vecteur dans un HashSet. Le hashset n'accepte pas de doublons (cette solution est peut etre plus rapide si le tableau est énorme).

bonne chance.

Tu peu effectuer une suppression des doublons comme ceci:

Attention: ce type de méthode ne convient pas pour tout les objets, il faut des objets comparable avec les méthodes compareTo() et equals() consistent...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
package xxxxxxxxxxx;
 
import java.util.Arrays;
import java.util.Vector;
 
public class TestVector {
 
    /** Creates a new instance of TestVector */
    public TestVector() {
 
 
 
    }
 
    /** Supprime les doublons d'un Vector 
     *  Deux objets sont considéré comme doublons si et seulement si la méthode equals() retourne true
     *  Attention, cette méthode nécessite une consistence entre la méthode compareTo() et equals()
     *  @param vector Vector dont on doit supprimer les doublons
     */
    public static void removeDuplicateEntries( Vector vector ) {
        synchronized(vector) {
 
            /** Index tout les objets tout en les triants
             */
            Indexer indexers[] = new Indexer[ vector.size() ]; 
            for(int i = 0 ; i < vector.size() ; i++ ) {
                Object o = vector.get(i);
                indexers[i] = new Indexer(i,o);
            }
            Arrays.sort( indexers );
 
            /** Génere un rapport des doublons
             */
            int[] doublons = new int[ vector.size() ];
            int doublonIndex = 0;
            for(int i = 0 ; i < indexers.length  - 1; i++ ) {
                if( indexers[i].equals( indexers[i+1] ) ) {
                    doublons[ doublonIndex ] = indexers[i+1].getIndex();
                    doublonIndex++;
                }
            }
 
            /** Tri des doublons
             */
            int[] doublonsTries = new int[ doublonIndex ];
            System.arraycopy(doublons , 0 , doublonsTries , 0 , doublonIndex );
            Arrays.sort(doublonsTries);
 
            /** Supprime les doublons dans le vecteur
             */
            for(int i = doublonsTries.length - 1 ; i >= 0 ; i-- ) {
                System.out.println("Suppression de l'entrée " + doublonsTries[i] );
                vector.removeElementAt( doublonsTries[i] );
            }
        }
    }
 
    /** Classe Indexer permettant de trier les objets entre eux
     */
    private static class Indexer<T> implements Comparable<Indexer>
    {
        private int index    = 0;
        private T   object   = null;
 
 
        public Indexer(int index , T o ) {
            this.index = index;
            this.object = o;
        }
 
        public int getIndex() {
            return this.index;
        }
 
        public T getObject() {
            return this.object;
        }
 
        public int compareTo(Indexer other) {
            if( this.getObject() == other.getObject() ) return 0;
            if( this.getObject() == null ) return -1;
            if( other.getObject() == null ) return 1;
            if( ! (getObject() instanceof Comparable) || other.getObject() instanceof Comparable) {
                int a = System.identityHashCode( getObject() );
                int b = System.identityHashCode( other.getObject() );
                if( a == b ) return 0;
                return a-b;
            }
            return ((Comparable)getObject()).compareTo( other.getObject() );
        }
 
        public boolean equals(Object obj) {
            if( obj == null ) return false;
            if( ! ( obj instanceof Indexer ) ) return false;
            Indexer other = (Indexer)obj;
 
            if( this.getObject() == other.getObject() ) return true;
            if( this.getObject() == null ) return false;
            if( other.getObject() == null ) return false;
 
            return this.getObject().equals( other.getObject() );
        }
 
    }
 
 
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Vector v = new Vector();
        v.add( "Coucou");
        v.add( "Bonjour");
        v.add( "Comment");
        v.add( "Coucou");
        v.add( "Azerty");
        v.add( "Comment");
 
        removeDuplicateEntries(v);
        for(int i = 0 ; i < v.size() ; i++ ) {
            System.out.println("==>" + v.get(i) );
        }
 
    }
 
}

Bonjour,

la classe HashSet évite les doublons (mais n'a pas de notion d'ordre).
on peut (si la notion d'autre est secondaire) filtrer les doublons d'un vecteur (idéalement d'une List)

Code:

v = new java.util.Vector(new java.util.HashSet(v));

par exemple si on fait
Code:

1 2 3 4 5 6 7 8 9 10 java.util.Vector v = new java.util.Vector(); v.add( "Coucou"); v.add( "Bonjour"); v.add( "Comment"); v.add( "Coucou"); v.add( "Azerty"); v.add( "Comment"); System.out.println("Avant filtre : "+v); v = new java.util.Vector(new java.util.HashSet(v)); System.out.println("Après filtre : "+v);
on obtient comme affichage
Code:

1 2 Avant filtre : [Coucou, Bonjour, Comment, Coucou, Azerty, Comment] Après filtre : [Coucou, Comment, Bonjour, Azerty]

29/11/2007, 17h04
herve91
A mon avis le plus simple et le plus sûr est de faire :
Code:

1 2 3 Set set = new HashSet(vecteur); vecteur.clear(); vecteur.addAll(set);
29/11/2007, 17h08
divxdede
Citation:
Envoyé par herve91

A mon avis le plus simple et le plus sûr est de faire :

Code:

1 2 3 Set set = new HashSet(vecteur); vecteur.clear(); vecteur.addAll(set);
A l'exception pret que tu ne respectes plus l'ordre du vecteur d'origine.
29/11/2007, 17h13
herve91

Déjà s'il y a des doublons on peut se demander si une relation d'ordre est définie ;)
29/11/2007, 17h14
divxdede

Citation:

Envoyé par herve91

Déjà s'il y a des doublons on peut se demander si une relation d'ordre est définie ;)

ne serait-ce que l'insert-order qui peut avoir un sens
29/11/2007, 17h42
natha
Et utiliser LinkedHashSet pour conserver l'ordre initial ?
Code:

1 2 3 Set set = new LinkedHashSet(vecteur); vecteur.clear(); vecteur.addAll(set);

Citation:
Envoyé par natha
Et utiliser LinkedHashSet pour conserver l'ordre initial ?
Code:

1 2 3 Set set = new LinkedHashSet(vecteur); vecteur.clear(); vecteur.addAll(set);
Effectivement, a l'exception de la synchronisation.
Code:

1 2 3 4 5 6 synchronized(vecteur) { Set set = new LinkedHashSet(vecteur); vecteur.clear(); vecteur.addAll(set); }

30/11/2007, 10h13
divxdede

Je voulais également insister sur deux points.

Nous avons deux solutions differentes:

la 1ere: celle que j'avais faite est plus compliquée en terme de code et donc beaucoup moins éléguante. A mon sens cette solution est la moins bonne. De plus elle nécessite que les objets soient comparable et de ce fait la méthode compareTo() doit être consistente avec la méthode equals().

La 2ème: Solution avec la LinkedHashSet est trés simple et fonctionnelle. Cependant elle posséde également une contrainte: La méthode hashCode() doit être consistante avec la méthode equals().

Si pour un objet tu as redefinie la méthode equals(), il faut faire de même avec la méthode hashCode() (ce qui devrait être fait en tout hypothése) de façon a ce que deux objets identiques (par la méthode equals) aient le même hashCode

Il n'est pas rare que des developpeurs oublient de surcharger les méthodes hashCode lorsqu'ils definissent l'intelligence de la méthode equals(). De ce fait ces objets là sont globalement inutilisables dans des collections hashées et ne fonctionnerait pas avec la 2ème solution.

C'etait juste pour dire qu'il est important de garder cette problèmatique à l'esprit.
30/11/2007, 10h27
natha

Citation:

Envoyé par divxdede

Il n'est pas rare que des developpeurs oublient de surcharger les méthodes hashCode lorsqu'ils definissent l'intelligence de la méthode equals(). De ce fait ces objets là sont globalement inutilisables dans des collections hashées et ne fonctionnerait pas avec la 2ème solution.

Faut mettre un warning là-dessus dans les IDE qui le permettent !
Avec CheckStyle c'est vite vérifié ;)