Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.57/7: Рейтинг темы: голосов - 7, средняя оценка - 4.57
peoplep8
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 37
1

Ошибка "Segmentation fault" при вызове метода erase() контейнера vector

05.02.2019, 16:28. Просмотров 1280. Ответов 34

Хочу убрать изолированные вершины в графе. На строке 75 выдает "Segmentation fault".

C++
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
#include <iostream>
#include <vector>
#include <forward_list>
 
using namespace std;
 
struct Node
{
    int weight;
    int vertex;
};
 
int main()
{
    vector<forward_list<Node> > g;
    int nvertex, nedges;
    cin >> nvertex >> nedges;
    g.reserve(nvertex);
    int nv1, nv2, edgeWeight;
    Node *inode = new Node;
    // ввожу граф
    for(int i = 0; i < nedges; ++i)
    {
        cin >> nv1 >> nv2 >> edgeWeight;
        // пусть вершины с 0 нумеруются
        --nv1;
        --nv2;
        bool isEdgeUnique = true;
        // проверка ребра на уникальность
        // (если ребро (nv1, nv2) или (nv2, nv1) уже есть в графе g и его вес больше, чем edgeWeight, то меняем его вес на edgeWeight 
        for(forward_list<Node>::iterator itv1 = g[nv1].begin(); itv1 != g[nv1].end(); ++itv1)
        {
            if(itv1->vertex == nv2)
            {
                isEdgeUnique = false;
                if(edgeWeight < itv1->weight)
                {
                    itv1->weight = edgeWeight;
                    for(forward_list<Node>::iterator itv2 = g[nv2].begin(); itv2 != g[nv2].end(); ++itv2)
                        if(itv2->vertex == nv1)
                            itv2->weight = edgeWeight;
                }
            }
        }
        if(isEdgeUnique) // если ребро уникально
        {
            inode->vertex = nv2;
            inode->weight = edgeWeight;
            g[nv1].push_front(*inode);
            inode->vertex = nv1;
            if(nv1 != nv2)
                g[nv2].push_front(*inode);
        }
    }
    delete inode;
    inode = 0;
    
    // вывожу граф
    cout << endl;
    for(int j = 0; j < nvertex; ++j)
    {
        cout << j << ":";
        for(forward_list<Node>::iterator it = g[j].begin(); it != g[j].end(); ++it)
            cout << " " << it->vertex;
        cout << endl;
    }
    
    // пытаюсь коряво убрать изолированные вершины
    vector<forward_list<Node> >::iterator bi = g.begin();
    for(int i = 0; i < nvertex; ++i)
    {
        if(g[i].empty())
        {
            advance(bi, i);
            g.erase(bi);
           --nvertex;
        }
    }
    
    // вывожу граф
    cout << endl;
    for(int j = 0; j < nvertex; ++j)
    {
        cout << j << ":";
        for(forward_list<Node>::iterator it = g[j].begin(); it != g[j].end(); ++it)
            cout << " " << it->vertex;
        cout << endl;
    }
    return 0;
}
Например, ввожу такой граф:

5 4
1 2 5
1 2 3
2 3 4
1 4 10

Выводит:

0: 3 1
1: 2 0
2: 1
3: 0
4:
Segmentation fault

Метод empty() нормально определяет, что вершина с номером 4 изолирована, но удалить её не получается.
0
Лучшие ответы (1)
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.02.2019, 16:28
Ответы с готовыми решениями:

Segmentation fault при вызове метода
Собственно такое дело, имеется следующий код: Item* m_items; Player::Player() { ... ...

Ошибка "Segmentation fault" при организации дерева
Есть следующие функции Three сreateThree(Node **q) { if((*q)-&gt;p) { Three...

[C/C++] "Segmentation fault" при попытке передачи параметра командной строки.
Прога вылетает при попытке передачи параметра через командную строку.Такой код: #include...

Найти причины возникновения ошибки "Segmentation fault" в шаблонном лямбда-выражении (C++11)
Добрый день. Есть такой код:template&lt;typename ChipSelect, typename T = uint8_t&gt; static T...

Найти причины и способы исправления ошибки "Segmentation fault" в заданном коде
Здравствуйте. С языком c++ и программировании в целом только знакомлюсь. Получил задание написать...

34
peoplep8
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 37
05.02.2019, 18:09  [ТС] 21
Azazel-San, вроде эту использую http://www.cplusplus.com/reference/iterator/advance/
Правда я забыл подкоючить <algorithm>, но сейчас подключил, все равно Seg fault
0
LegionK
Че,пацаны,аниме?
218 / 162 / 146
Регистрация: 02.05.2017
Сообщений: 657
Завершенные тесты: 2
05.02.2019, 18:13 22
Цитата Сообщение от peoplep8 Посмотреть сообщение
да, возможно их и не нужно удалять
Ура!

peoplep8, я кстати, вам похоже просчитался с вашим удалением, если вы делаете erase из списка смежности
Допустим вершина соеденина со всеми остальными n-1. И допустим k == n . И n пусть будет 10^5.
Смотрите для каждой вершины из списка смежности ( это уже n) мы проходим по всем соединенным вершинам (уже n^2),потом проходим по массиву k и ищем там каждую вершину,проверяя,чтобы это был город не со складом (k == n, так что это уже n^3) и наконец удаляем, удаление - за линейную сложность от размера массива (n^4)
А n^4 уже некисло даже для 1000, а не 10^5
Короче надеюсь сейчас норм посчитал и не бред
А если так, то это даже вредно
1
peoplep8
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 37
05.02.2019, 18:20  [ТС] 23
Azazel-San, да, можно агл Дейкстры в отдельной функции написать

Добавлено через 2 минуты
LegionK, я хочу сначала сам додуматься до решения, а потом смотреть на решения остальных

Добавлено через 3 минуты
LegionK, значит эта задача решается не Дейкстрой, а проще
0
LegionK
Че,пацаны,аниме?
218 / 162 / 146
Регистрация: 02.05.2017
Сообщений: 657
Завершенные тесты: 2
05.02.2019, 18:20 24
peoplep8, Хорошо,это просто был совет, просто понимаете,я считаю,что лучше сначала кинуть гранату, а потом уже идти оглушенных противников добивать, а не наоборот
Извиняюсь, придется вас оставить, у самого дела, как ни странно тоже с графами, но удачи вам, если все же решите взять листочек ,ручку и крепко подумать
1
05.02.2019, 18:20
peoplep8
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 37
05.02.2019, 18:21  [ТС] 25
LegionK, https://codeforces.com/blog/entry/46662
я посмотрел разбор, я до такого решения не додумался
0
LegionK
Че,пацаны,аниме?
218 / 162 / 146
Регистрация: 02.05.2017
Сообщений: 657
Завершенные тесты: 2
05.02.2019, 18:22 26
peoplep8,
Цитата Сообщение от peoplep8 Посмотреть сообщение
я хочу сначала сам додуматься до решения, а потом смотреть на решения остальных
Цитата Сообщение от peoplep8 Посмотреть сообщение
я посмотрел разбор, я до такого решения не додумался
Недолго вы ломались
0
peoplep8
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 37
05.02.2019, 18:24  [ТС] 27
LegionK, Спасибо. Хорошо, буду решать просто перебором
0
Azazel-San
Mental handicap
1079 / 537 / 154
Регистрация: 24.11.2015
Сообщений: 2,192
Завершенные тесты: 1
05.02.2019, 18:24 28
Цитата Сообщение от peoplep8 Посмотреть сообщение
Azazel-San, вроде эту использую http://www.cplusplus.com/reference/iterator/advance/
И забыл об этой функции.. Но довольно юзлесная, впрочем в вашем коде тоже.
Seg fault ошибка времени выполнения, кода вы пытаетесь получить доступ к памяти которая уже невалидная. Включаем дебаг и смотрим. У вас при вызове advance нету гарантии что смещение i будет в рамках диапазона вашего вектора.
1
peoplep8
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 37
05.02.2019, 18:28  [ТС] 29
LegionK, но я не сам код смотрел. Я все-таки отправлю Дейкстру сначала, просто посмотреть сколько тестов пройдет

Добавлено через 2 минуты
Azazel-San, Спасибо, чуть позже попробую
0
DrOffset
10915 / 5814 / 1432
Регистрация: 30.01.2014
Сообщений: 9,357
05.02.2019, 19:36 30
Лучший ответ Сообщение было отмечено peoplep8 как решение

Решение

Цитата Сообщение от peoplep8 Посмотреть сообщение
А все-таки, как же правильно удалить вершину из списка смежности графа средствами STL?
Если на примере вашего кода, то так:
C++
1
2
3
4
5
6
7
8
    for(auto i = g.begin(); i != g.end(); )
    {
        if(g[j].empty())
            i = g.erase(i);
        else
            ++i;
        ++j;
    }
А в вашем первоначальном коде у вектора нужен resize вместо reserve.
1
peoplep8
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 37
05.02.2019, 19:49  [ТС] 31
Спасибо, мне уже пришлось такую штуку сгородить

C++
1
2
3
4
5
6
7
8
9
10
11
12
void removeIsolatedVertices(vector<forward_list<Node> > &graph, int &nvertex)
{
    for(int i = 0; i < nvertex; ++i)
    {
        if(g[i].empty())
        {
            for(int j = i; j < nvertex-1; ++j)
                g[j] = g[j+1];
             --nvertex;
        }
    }
}
0
DrOffset
10915 / 5814 / 1432
Регистрация: 30.01.2014
Сообщений: 9,357
05.02.2019, 19:53 32
peoplep8, ваша ошибка была в том, что не учли, что итератор инвалидируется после erase и применение к нему инкремента приводит к UB (в данном случае оно проявилось как падение программы). Точно так же приводит к UB использование неинициализированной памяти после reserve - он только размечает память (resize размечает и создает объекты). Но в вашем случае это к падению не привело, хотя могло (это всегда лучше, пусть программа грохнется, чем молча неправильно вычисляет).
1
peoplep8
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 37
05.02.2019, 19:54  [ТС] 33
Да, я resize() и reserve() перепутал, видимо поэтому и g.begin() и не работал
0
DrOffset
10915 / 5814 / 1432
Регистрация: 30.01.2014
Сообщений: 9,357
05.02.2019, 20:21 34
peoplep8, нашел еще одну ошибку у вас.
Вывод после удаления должен быть таким:
C++
1
2
3
4
    for(int j = 0, s = g.size(); j < s; ++j)
    {
         //.....
    }
До nvertex считать нельзя, т.к. элементов в векторе теперь меньше.
Вообще старайтесь использовать инструменты единообразно. Или счетчик или итераторы, лучше не смешивать.
И получше изучите интерфейс используемых контейнеров, чтобы знать о граничных случаях.

Добавлено через 7 минут
И будет совсем хорошо, если вы nv1 и nv2 проверите перед использованием на принадлежность диапазону [0..nvertex), а то сейчас у вас можно ввести любые числа и тоже получить UB из-за выхода за пределы массива.
1
peoplep8
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 37
05.02.2019, 20:24  [ТС] 35
Да, согласен. Буду чаще STL использовать, чтобы бытрее изучить контейнеры

Добавлено через 1 минуту
Да, в любой программе следует проверять диапазоны
0
05.02.2019, 20:24
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.02.2019, 20:24

Ошибка "*.exe вызвал срабатывание точки останова" и "HEAP CORRUPTION" при вызове деструктора программой
Здравствуйте! Сделал простенькое упражнение на указатели, но программа выдает названные ошибки. ...

"Идентификатор не найден" при вызове метода void
Здравствуйте. Следующая проблема: при вызове метода void Math(t1, t2), выдает ошибку &quot;идентификатор...

Ошибка при вызове wstring.erase
форум глючит ... Добавлено через 1 минуту Почему erase ругается ? std::wstring testString...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
35
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.