не уверен в причине для ConcurrentModificationException

Question

Это мой код для построения возможной экскурсии по городам за Locale l (это не оптимально, это просто начало поиска AI).

Я получаю ConcurrentModificationException, что, насколько мне известно, происходит, когда более одного фрагмента кода обращается к переменной / коллекции и пытается ее изменить. Вызывает недовольство этим кодом:

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

Я изменяю его, когда добавляю элемент, но поскольку у Итератора нет метода добавления (только удаления), я использую метод коллекции.

Итак, мои вопросы:

1. Является ли мое добавление элемента причиной проблемы?
2. Если это так, как мне правильно добавить его, чтобы modCount был верным, а я не получил ConcurrentModificationException?

Полный метод ниже, с комментарием к строке, где происходит ConcurrentModificationException:

public void construct() {
    tour = new ArrayList();
    ArrayList<City> lcl = new ArrayList(l.getCitys());

    tour.add(lcl.remove(0));
    tour.add(lcl.remove(1));

    while (!this.tourComplete()) {
        System.out.println(tour.size());
        Iterator tourit = tour.iterator();
        City g1 = (City) tourit.next();
        City g2 = (City) tour.get(lcl.indexOf(g1)+1);

        int gapDist = l.distanceBetweenCitys(g1, g2);

        while (tourit.hasNext()) {
            City C = null;
            int best = Integer.MAX_VALUE;

            for (Iterator lclit = lcl.iterator(); lclit.hasNext(); ) {
                City c = (City) lclit.next();
                int avg = (l.distanceBetweenCitys(g1,c) + 
                           l.distanceBetweenCitys(g2, c))/2 ;

                if ( (avg<gapDist) && (avg<best) ) {
                    C = c;
                    best = avg;
                }
            }

            if (C != null) {
                assert(best == Integer.MAX_VALUE);
                City A = tour.get(0);
                City Z = tour.get(tour.size()-1);

                boolean begin = true;

                for (Iterator lclit = lcl.iterator();   lclit.hasNext(); ) {
                    City c = (City) lclit.next();
                    int dist = l.distanceBetweenCitys(A,c);

                    if ( dist<best ) {
                        begin = true;
                        C = c;
                        best = dist;
                    }
                }

                for (Iterator lclit = lcl.iterator();   lclit.hasNext(); ) {
                    City c = (City) lclit.next();
                    int dist = l.distanceBetweenCitys(Z,c);

                    if ( dist<best ) {
                        begin = false;
                        C = c;
                        best = dist;
                    }
                }

                if (begin) {
                    // one of these is causing the problem
                    tour.add(0,C);
                }
                else {
                    // one of these is causing the problem
                    tour.add(C);
                }
            }
            else {
                // one of these is causing the problem
                tour.add(tour.indexOf(g2),C);
            }

            g1 = (City) tourit.next(); // this is where it all goes wrong 
            g2 = (City) tour.get(lcl.indexOf(g1)+1);
            gapDist = l.distanceBetweenCitys(g1, g2);
        }
    }
}

Answer 1

Вы не можете изменять базовую коллекцию при использовании итератора (кроме как через сам итератор).

Я не изучил ваш алгоритм (кажется, вы хотите вставить в произвольные позиции, что может быть сложно), но, возможно, вы можете сделать одно из следующих действий:

1. собирать все, что вы хотите добавить во вторую коллекцию, и делать addAll после того, как вы закончите.

2. Вместо этого переберите копию коллекции.

3. Используйте ListIterator , который имеет метод add в дополнение к remove.

4. Не использовать итератор вообще, а просто получить доступ к ArrayList по индексу (который вы в любом случае уже делаете в других местах)

Кроме того, вы можете покончить с большим количеством типов, указав тип итератора (так же, как вы сделали со списком).

Answer 2

Вы можете легко обойти это, используя переменную индекса вместо итератора:

int i = 0;
while (i < tour.size()) {
    ....
    i++;
}

Однако вы заметите, что вставка элементов в список, по которому вы выполняете итерацию, поднимает некоторые хитрые вопросы. Существует причина, по которой Iterator создает исключение ConcurrentModificationException, заключающаяся в том, что логика продолжения итерации не является четко определенной. Если вы вставляете элемент перед позицией индекса, индекс больше не указывает на тот же «текущий» элемент, и вам нужно увеличить индекс на два, чтобы найти следующий элемент. Если вы вставите после, то ничего не изменится, кроме условия остановки (но tour.size () будет расти правильно, так что все в порядке). Если вы делаете несколько вставок / удалений в разных позициях, становится трудно отследить ...

Я чувствую, что ваш алгоритм также может быть упрощен, хотя мне не совсем понятно, что он должен делать.

Answer 3

Внутри цикла Итератора вы пытаетесь изменить Список
Выдержка из вашего кода

if (begin) {
                    // one of these is causing the problem
                    tour.add(0,C);
                }
                else {
                    // one of these is causing the problem
                    tour.add(C);
                }

Это недопустимо. Согласно javaDoc http://java.sun.com/j2se/1.4.2/docs/api/java/util/ConcurrentModificationException.html

Это исключение может быть вызвано методы, которые обнаружили одновременное модификация объекта, когда такой модификация не допускается. За Например, это не так допускается для одного потока изменить Коллекция в то время как другая нить перебирая это. В общем, результаты итерации не определены при этих обстоятельствах. Немного Реализация итераторов (включая те из всей коллекции реализации, предоставленные JRE) может выбрать, чтобы бросить это исключение, если это поведение обнаружено. итераторы которые делают это известны как отказоустойчивые итераторы, поскольку они быстро и чисто, скорее рискуя произвольное недетерминированное поведение в неопределенное время в будущем.

Answer 4

Это мой уродливый, но сейчас работающий код для тех, кто хочет посмотреть, как я его получил, в конце концов, я намереваюсь немного его раскрасить, но на данный момент я доволен тем, что он работает

    public void construct()
{
tour = new ArrayList();
ArrayList<City> lcl = new ArrayList(l.getCitys());

tour.add(lcl.remove(0));
tour.add(lcl.remove(1));
tour.add(lcl.remove(2));

while (!this.tourComplete())
{

System.out.println(tour.size());
ListIterator<City> tourit = tour.listIterator();
City g1 = (City) tourit.next();
City g2 = (City) tour.get(tour.indexOf(g1)+1);

int gapDist = l.distanceBetweenCitys(g1, g2);

    while ((tourit.nextIndex()!=tour.size()-1) && !this.tourComplete())
    {
    System.out.println("x");
    City C = null;
    int best = Integer.MAX_VALUE;

        for (ListIterator<City> lclit = lcl.listIterator();   lclit.hasNext(); )
        {
        City c = (City) lclit.next();
        int avg = (l.distanceBetweenCitys(g1,c)+ l.distanceBetweenCitys(g2, c))/2 ;

        if ( (avg<gapDist) && (avg<best) )
        {
        C=c;
        best=avg;
        }

        }

    if (C==null)
    {
    System.out.println("C null");
        assert(best==Integer.MAX_VALUE);
        City A = tour.get(0);
        City Z = tour.get(tour.size()-1);

        boolean begin = true;

        for (ListIterator<City> lclit = lcl.listIterator();   lclit.hasNext(); )
        {
            City c = (City) lclit.next();
            int dist = l.distanceBetweenCitys(A,c);

            if ( dist<best )
            {
            begin=true;
            C=c;
            best=dist;
            }

        }

        for (ListIterator<City> lclit = lcl.listIterator();   lclit.hasNext(); )
        {
            City c = (City) lclit.next();
            int dist = l.distanceBetweenCitys(Z,c);

            if ( dist<best )
            {
            begin=false;
            C=c;
            best=dist;
            }

        }

        if(begin)
        {
        System.out.println("add at begining");
        System.out.println(this.TourtoString());
         // add in at 0

            int itpos = tourit.nextIndex();
            //move iterator to 0
            while (tourit.hasPrevious())
            {
            tourit.previous();
            }

            lcl.remove(C);
            // add in C
            tourit.add(C);

            // move iterator back
            while(tourit.nextIndex()!=(itpos+1))
            {
            tourit.next();
            }
        System.out.println(this.TourtoString());
        }
        else
        {
         // add in at end
            int itpos = tourit.nextIndex();
            //move iterator to end
            while (tourit.hasNext())
            {
            tourit.next();
            }

            lcl.remove(C);
            // add in C
            tourit.add(C);

            // move iterator back
            while(tourit.nextIndex()!=itpos)
            {
            tourit.previous();
            }
        }

    }
    else
    {
    System.out.println("C not null");

    // add in at g2
    int moveto = tour.indexOf(g2);
    int itpos = tourit.nextIndex();

    System.out.println("add at: "+ moveto);
    System.out.println(this.TourtoString());


    if (itpos>=moveto)
    {
    itpos++;
    }

    //move iterator to 0
    while (tourit.hasPrevious())
    {
    tourit.previous();
    }

    // move iterator to insertion location
    while (tourit.nextIndex()!=moveto)
    {
    tourit.next();
    }

    lcl.remove(C);
    // add in C
    tourit.add(C);

    //move iterator to 0
    while (tourit.hasPrevious())
    {
    tourit.previous();
    }


    // move iterator back
    while(tourit.nextIndex()!=itpos)
    {
    tourit.next();
    }

     System.out.println(this.TourtoString());
    }


    g1 = (City) tourit.next(); 
    g2 = (City) tour.get(tour.indexOf(g1)+1);
    gapDist = l.distanceBetweenCitys(g1, g2);
    }

}

}

Answer 5

Из javadoc для ArrayList:

Итераторы, возвращаемые методами итератора этого класса и listIterator, работают без сбоев: если список структурно изменяется в любое время после создания итератора, любым способом, кроме использования собственных методов удаления или добавления итератора, итератор будет исключение ConcurrentModificationException. Таким образом, перед одновременной модификацией итератор быстро и чисто дает сбой, вместо того чтобы рисковать произвольным недетерминированным поведением в неопределенное время в будущем.