векторные итераторы несовместимы - PullRequest
Новая
       27

векторные итераторы несовместимы

4 голосов
/ 31 мая 2011

В настоящее время я работаю над библиотекой графов для C ++, и теперь застрял в точке, когда во время выполнения я получаю ошибку подтверждения в режиме отладки.Я также посмотрел на SO другой вопрос, но ни один из вопросов и ответов не привел меня к решению.После прочтения на некоторых форумах у меня сложилось впечатление, что эта ошибка возникает из-за того, что итераторы становятся недействительными, как только векторный контент изменяется.(например, при использовании erase()) Но, как вы можете видеть из моего кода, я не изменяю вектор, а просто повторяю.

Ошибка в строке, помеченной //ASSERTION.Странно то, что neighbor_it указывает не на первый объект в (*vertex_it)->neighbors(), а на 0xfeeefeee.При отладке по коду я ясно вижу, что соседний вектор содержит хотя бы один элемент.Разве neighbor_it не должен указывать на первый объект в этом векторе?

Для получения дополнительной информации: m_vertices - это вектор всех вершин графа, а vertex::neighbors() возвращает вектор ребер (которые имеютуказатель на соседнюю / целевую вершину).В этом методе я хочу удалить все ребра, указывающие на определенную вершину.Возвращает true, если соответствующий край был найден и удален, false, если нет края, указывающего на p_vertex. 

bool graph::remove_edges_pointing_to( vertex* p_vertex )
{
    bool res = false;

    std::vector<vertex*>::iterator vertex_it = m_vertices.begin();

    // iterate through all vertices
    while( vertex_it != m_vertices.end() )
    {
        // iterator on first element of neighbors of vertex
        std::vector<edge*>::iterator neighbor_it = (*vertex_it)->neighbors().begin();

        // iterate through all successors of each vertex
        while( neighbor_it != (*vertex_it)->neighbors().end() ) //ASSERTION
        {
            if( (*neighbor_it)->dest() == p_vertex )
            {
                if( (*vertex_it)->remove_edge( *neighbor_it ) )
                {
                    res = true;
                }
            }

            neighbor_it++;
        }

        vertex_it++;
    }

    return res;
}

РЕДАКТИРОВАТЬ: (Решение)

Хорошо, вот мой новый код, который работает правильно.remove_edge() теперь возвращает итератор для следующего объекта в векторе, из которого он удалил ребро.Кроме того, neighbors() теперь возвращает ссылку на соответствующий вектор. 

bool graph::remove_edges_pointing_to( vertex* p_vertex )
{
    bool res = false;

    std::vector<vertex*>::iterator vertex_it = m_vertices.begin();

    // iterate through all vertices
    while( vertex_it != m_vertices.end() )
    {
        // iterator on first element of neighbors of vertex
        std::vector<edge*>::iterator neighbor_it = (*vertex_it)->neighbors().begin();

        // iterate through all successors of each vertex
        while( neighbor_it != (*vertex_it)->neighbors().end() )
        {
            if( (*neighbor_it)->dest() == p_vertex )
            {
                neighbor_it = (*vertex_it)->remove_edge( *neighbor_it );
                res = true;
            }
            else
            {
                neighbor_it++;
            }
        }

        vertex_it++;
    }

    return res;
}

Еще раз спасибо за ваши ответы!:)

Ответы [ 2 ]

11 голосов
/ 31 мая 2011

Мое предположение, учитывая предоставленный вами ограниченный контекст, заключается в том, что neighbours() возвращает копию std::vector<edge*> вместо ссылки, то есть std::vector<edge*>&.Поэтому после begin() вызов временного объекта удаляется, а полученный итератор указывает на мусор.

1 голос
/ 31 мая 2011

Я бы предположил, что remove_edge изменяет базовый контейнер neighbor_it, тем самым делая его недействительным, но я не могу быть уверен, не увидев больше вашего кода.

Если это так, возможное решениебудет возвращать итератор к следующему элементу после удаленного, как, например, с помощью std::vector::erase.

...