Analyse ArrayList 3: suppression d'éléments

ArrayListAnalyse3 : Supprimer l'élément

Veuillez indiquer la source de la réimpression.：https://www.cnblogs.com/funnyzpc/p/16421743.html

Il est souvent nécessaire de supprimer des éléments d'une classe de collection,Très fréquent;Si c'est la façon habituelle de supprimer, il n'y a pas besoin d'écrire ce blog.,Ce blog ne se contente pas d'analyser les problèmes que la suppression peut causer,La raison pour laquelle la suppression de l'Itérateur d'emprunt est nécessaire est également analysée au niveau du code source.,En même temps, les méthodes de suppression sous différents modes d'affaires seront également données.,Jetez un coup d'oeil en bas🥸

Un..Suppression en boucle et hors boucle

Il s'agit de deux modèles d'affaires différents,Si l'emplacement de l'index ou la valeur de l'élément à supprimer est déterminé et qu'un seul élément est supprimé,Généralement un appel directArrayListEn basremoveMéthode de suppression,Mais ce n'est pas le but.

    public static void main(String[] args) {
        ArrayList arr  = new ArrayList();
        arr.add("a");
        arr.add("b");
        arr.add("c");
        arr.add("d");
        arr.add("e");
        System.out.println(arr);
        arr.remove("c");// remove c
        arr.remove(3);// remove d
        System.out.println(arr);
    }

Un autre cas est de supprimer plusieurs éléments , L'emplacement de l'index de l'élément à supprimer ne peut généralement pas être déterminé , Ceci doit être supprimé dans la boucle ;

    public static void main(String[] args) {
        ArrayList arr  = new ArrayList();
        arr.add("a");
        arr.add("b");
        arr.add("c");
        arr.add("d");
        arr.add("e");
        arr.add("d");
        System.out.println(arr);
        for(int i=0;i<arr.size();i++){
            if("d".equals(arr.get(i))){
                arr.remove("d");
            }
        }
        System.out.println(arr);
    }

2.. Utilisation incorrecte supprimée

(Mauvaise utilisation I)

    public static void main(String[] args) {
        ArrayList arr  = new ArrayList();
        arr.add("a");
        arr.add("b");
        arr.add("c");
        arr.add("d");
        arr.add("e");
        arr.add("d");
        System.out.println(arr);
        for(Object item:arr){
            if("d".equals(item)){
                arr.remove(item);
            }
        }
    }

(Mauvaise utilisation II)

    public static void main(String[] args) {
        ArrayList arr  = new ArrayList();
        arr.add("a");
        arr.add("b");
        arr.add("c");
        arr.add("d");
        arr.add("e");
        arr.add("d");
        System.out.println(arr);
        arr.forEach(item->{
            if("d".equals(item)){
                arr.remove("d");
            }
        });
    }

Bien que les deux soient supprimés , Mais la version simplifiée for Les boucles et les boucles fonctionnelles ne peuvent pas être supprimées ？Regarde en bas....

Trois. Qu'est - ce que l'effacement normal a fait

C'estArrayListDeremoveCode source：

    public E remove(int index) {
        rangeCheck(index);
        modCount++;
        E oldValue = elementData(index);
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                    numMoved);
        elementData[--size] = null; // clear to let GC do its work   Clair. GC Faire son travail （ C'est - à - dire qu'une position est rétrécie et mise en parallèle à null, Les citations coupées sont naturellement gcLaisse tomber.）
        return oldValue;
    }

Voici l'Itérateur removeCode source：

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();
            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

PourArrayListDeremove, Ce qui est important, c'est que --size , Et pour l'Itérateur remove Plus qu'un simple appel ArrayList La suppression de doit également mettre à jour le curseur (cursor) Et l'emplacement actuel de l'index des éléments (lastRet), C'est là que vient l'inspiration ,C'est ça?Version simplifiéeforCycleEtFonctionforEachCycleEn bassizeEst devenuConstanteEt voilà.？C'est exact., En fait, c'est comme ça , Si je changeais la logique de suppression de boucle pour qu'elle so it compréhensible ：

    public static void main(String[] args) {
        ArrayList arr  = new ArrayList();
        arr.add("a");
        arr.add("b");
        arr.add("c");
        arr.add("d");
        arr.add("e");
        arr.add("d");
        System.out.println(arr);
        for(int i=0;i<6;i++){
            if( i==(arr.size()-1) ){
                break;
            }
            if(arr.get(i).equals("d")){
                arr.remove(i);
            }
        }
        System.out.println(arr);
    }

Donc chaque fois que vous entrez dans une boucle, vous devez voir le tableau suivant sizeY a - t - il eu un changement?,Sinon, on franchit la ligne., Donc, quelle que soit la méthode de suppression, vous devez obtenir Dernière mise à joursize Ceci garantit une suppression sécurisée

Quatre. Supprimer la logique sous différentes exigences

S'il est nécessaire d'assurer une suppression complète et sécurisée , Il est recommandé d'utiliser un Itérateur iterator Ou listIterator：

public static void main(String[] args) {
        ArrayList arr  = new ArrayList();
        arr.add("a");
        arr.add("b");
        arr.add("c");
        arr.add("d");
        arr.add("e");
        arr.add("d");
        System.out.println(arr);
        Iterator itr = arr.iterator();
        while(itr.hasNext()){
            Object item = itr.next();
            if("d".equals(item)){
                itr.remove();
            }
        }
        System.out.println(arr);
    }

    public static void main(String[] args) {
        ArrayList arr  = new ArrayList();
        arr.add("a");
        arr.add("b");
        arr.add("c");
        arr.add("d");
        arr.add("e");
        arr.add("d");
        System.out.println(arr);
        ListIterator itr = arr.listIterator();
        while(itr.hasNext()){
            Object item = itr.next();
            if("d".equals(item)){
                itr.remove();
            }
        }
        System.out.println(arr);
    }

Si vous devez obtenir l'index de l'élément d'itération courant dans l'Itérateur, ou

public static void main(String[] args) {
        ArrayList arr  = new ArrayList();
        arr.add("a");
        arr.add("b");
        arr.add("c");
        arr.add("d");
        arr.add("e");
        arr.add("d");
        System.out.println(arr);
        ListIterator lst_itr = arr.listIterator();
        while(lst_itr.hasNext()){
            int idx = lst_itr.nextIndex();
            Object item = lst_itr.next();
            System.out.println(idx+"->"+item);
            if("d".equals(item)){
                lst_itr.remove();
            }
        }
        System.out.println(arr);
    }

Bien sûr, Si vous voulez utiliser l'Itérateur et obtenir l'emplacement de l'index de l'élément courant de la boucle , J'essaie encore d'obtenir le tableau original (Avant de supprimer)Emplacement de l'index pour, On peut essayer ：

    public static void main(String[] args) {
        ArrayList arr  = new ArrayList();
        arr.add("a");
        arr.add("b");
        arr.add("c");
        arr.add("d");
        arr.add("e");
        arr.add("d");
        System.out.println(arr);
        int i = 0;
        for(ListIterator lst_itr = arr.listIterator();lst_itr.hasNext();i++){
            int idx = lst_itr.nextIndex();
            Object item = lst_itr.next();
            System.out.println(i+" -> "+idx+":"+item);
            if("d".equals(item)){
                lst_itr.remove();
            }
        }
        System.out.println(arr);
    }

Cinq. Méthode simplifiée de suppression

    public static void main(String[] args) {
        ArrayList arr  = new ArrayList();
        arr.add("a");
        arr.add("b");
        arr.add("c");
        arr.add("d");
        arr.add("e");
        arr.add("d");
        System.out.println(arr);
        arr.removeIf(item->"d".equals(item));
        System.out.println(arr);
    }

Simplifier la suppression des sources internes ：

    @Override
    public boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        // figure out which elements are to be removed
        // any exception thrown from the filter predicate at this stage
        // will leave the collection unmodified
        int removeCount = 0;
        final BitSet removeSet = new BitSet(size);
        final int expectedModCount = modCount;
        final int size = this.size;
        for (int i=0; modCount == expectedModCount && i < size; i++) {
            @SuppressWarnings("unchecked")
            final E element = (E) elementData[i];
            if (filter.test(element)) {
                removeSet.set(i);
                removeCount++;
            }
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }

        // shift surviving elements left over the spaces left by removed elements
        //  Déplacer les éléments restants dans l'espace laissé par les éléments supprimés  , C'est - à - dire que le tableau est mince 
        final boolean anyToRemove = removeCount > 0;
        if (anyToRemove) {
            final int newSize = size - removeCount;
            for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
                i = removeSet.nextClearBit(i);
                elementData[j] = elementData[i];
            }
            for (int k=newSize; k < size; k++) {
                elementData[k] = null;  // Let gc do its work
            }
            this.size = newSize;
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            modCount++;
        }

        return anyToRemove;
    }

Ha Ha!, C'est trop compliqué , L'intérieur ne se limite pas à l'entretien removeCountJ'en ai besoin.Version de maintenance, L'emplacement de l'élément est également spécial Bouge, Ce n'est pas si efficace. , Donc l'utilisation apparemment simple n'est pas du tout simple à l'intérieur ...