1

Есть такой код(Обычный алгоритм Крускала):

void read_from_file(const char* file_name)
{
    ifstream inf(file_name);

    inf >> count_town >> count_road;
    graph.resize(count_town);

    int from_, to_, weight_;

    while (!inf.eof())
    {
        inf >> from_ >> to_ >> weight_;
        from_--;
        to_--;
        edges.push_back(make_pair(weight_, make_pair(from_, to_) ) );
    }

    inf.close();
}

//все вершины графа
vector <int> marks;

void change_mark(int mark1, int mark2)
{
    if (mark2 < mark1)
    {
        int t = mark1;
        mark1 = mark2;
        mark2 = t;
    }

    for (size_t i = 0; i < count_town; i++)
        if (marks[i] == mark2)
            marks[i] = mark1;
}

void cruskal_algo(vector<pair<int, pair<int, int> > >& tree, vector<pair<int, pair<int, int> > >& edges)
{
    marks.resize(count_town);
    for (size_t i = 0; i < count_town; i++)
        marks[i] = i;
    sort( edges.begin(), edges.end() );

    remaining_edges = edges;

    int k = 0;
    int t = count_road;
    int i;

    while (k < count_town - 1)
    {
        i = 0;
        while ((i <= t) && (marks[edges[i].second.first] == marks[edges[i].second.second]) && (edges[i].first != 0))
            i++;
        k++;
        pair<int, pair<int, int> > p = edges.at(i);
        tree.push_back(p);
        vector<pair<int, pair<int, int> > >::iterator it = find(remaining_edges.begin(), remaining_edges.end(), p);
        remaining_edges.erase(it);
        change_mark(p.second.first, p.second.second);
    }
}

Граф задан списком рёбер с именем edges. Edges - это вектор пар. Первое значение в паре - это вес ребра, второе значение - пара - первое значение - первая вершина ребра, второе значение в паре - вторая вершина ребра. Всё это дело(дерево минимальное) записывается в tree. Еще я хочу найти список оставшихся рёбер, не вошедших в дерево. Список оставшихся рёбер - remaining_edges(имеет такой же тип как edges и tree). Я просто-напросто взял скопировал в remaining_edges вектор edges и получил копию edges. Далее, в строках

vector<pair<int, pair<int, int> > >::iterator it = find(remaining_edges.begin(), remaining_edges.end(), edges[i]);
    remaining_edges.erase(it);

я нахожу в копии edges, т.е в remaining_edges элемент edges[i](то, что добавили в дерево) и удаляю его из remaining_edges. Но проблема в том, что здесь

remaining_edges.erase(it);

выдаёт ошибку

"vector erase iterator outside range"

Вроде бы ошибка тривиальная, но у меня уже битый час не получается её исправить. Спасибо.

4
  • Для начала, для удаления из вектора используется не erase, а пара erase/remove.
    – VladD
    18 фев 2014 в 15:47
  • @rekrut1: Можете предоставить минимальный код, воспроизводящий проблему?
    – VladD
    18 фев 2014 в 15:49
  • Вот, я добавил код. Читается файл, в котором граф задан рёбрами с весом: 7 8 1 2 1 1 3 6 2 3 3 2 4 12 4 7 4 4 5 5 5 6 2 7 6 7 в первой строке файла содержится кол-во вершин(в коде - count_town) и кол-во рёбер(count_road). Дальше идут рёбра с весом начиная со второй строки в файле. Первое число - начало ребра, второе - конец ребра, третье - вес этого ребра. Граф неориентированный.
    – rekrut
    18 фев 2014 в 15:58
  • 1
    @rekrut1: А можно и вправду минимальный пример? Уберите read_from_file, задайте что, что нужно, в коде. Обязателен такой большой граф, или на меньшем тоже воспроизводится? Нужна ли часть cruskal_algo до цикла while для того, чтобы воспроизвести проблему? Нужен ли сам цикл? Укоротите пример до 5 строчек, оставьте только нужное.
    – VladD
    18 фев 2014 в 16:06

1 ответ 1

2

Вы проверяете it != remaining_edges.end() ? Возможно, std::find ничего не находит и вы пытаетесь удалить элемент по итератору, указывающему за конец вектора.

9
  • как раз таки find находит то, что нужно. Даже ptr указатели совпадают.
    – rekrut
    18 фев 2014 в 12:26
  • 1
    @rekrut1 Каким образом совпадают указатели на два разных объекта? Чую беды от семантики перемещения
    – free_ze
    18 фев 2014 в 12:48
  • @rekrut1 Встречаю такую информацию, что после вызова move-присваивания, вектор-оригинал находится в неопределенном состоянии. Попробуй воспользоваться std::copy.
    – free_ze
    18 фев 2014 в 13:05
  • Не могу скрин из отладчика скинуть Вам.(
    – rekrut
    18 фев 2014 в 13:09
  • Неа. copy тоже не помогает.
    – rekrut
    18 фев 2014 в 13:27

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.