Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.73/15: Рейтинг темы: голосов - 15, средняя оценка - 4.73
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 49

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

05.02.2019, 16:28. Показов 3570. Ответов 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)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
05.02.2019, 16:28
Ответы с готовыми решениями:

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

Segmentation fault при вызове std::vector::insert
Создаю вектор, резервирую память, пробую вставить число 42, получаю segmentation fault. std::vector&lt;int&gt; vec; ...

libcUrl: segmentation fault при вызове метода curl_easy_init()
Всем доброго времени суток! Ситуация следующая. Писал небольшую программку для работы через интернет(в Dev-cpp). изначально интерфейс был...

34
 Аватар для LegionK
393 / 263 / 193
Регистрация: 02.05.2017
Сообщений: 1,003
05.02.2019, 16:43
А само задание какое? Что в коде происходит?
0
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 49
05.02.2019, 17:16  [ТС]
Задание вот https://codeforces.com/problem... ?locale=ru
Пробовал решить представляя граф матрицей смежности, но граф занимал лимит памяти на большом числе вершин.
Теперь вот решил использовать список смежности, чтобы память сэкономить

Из решения задачки я вытащил кусок кода
Сначала в строках 15-56 я считываю граф и заношу его в вектор однонаправленных списков, эта часть кода правильна (но возможно не эффективна)
В строках 58-66 в первый раз вывожу граф на экран
В строках 68-78 избавляюсь от изолированных вершин (если в векторе есть пустой список, то этот элемент вектора следует удалить)
В строках 80-88 второй раз вывожу граф на экран

Меня интересует вот этот кусочек кода, строки 68-78
C++
1
2
3
4
5
6
7
8
9
10
11
// пытаюсь коряво убрать изолированные вершины
    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;
        }
    }
Я что-то делаю не так, ибо опыта с STL у меня мало

Добавлено через 3 минуты
Хочу задачку с использованием STL решить, нужно же все таки начинать пользоваться благами, которые C++ предоставляет

Добавлено через 44 секунды
Думаю, что итератор неправильно сдвигаю

Добавлено через 1 минуту
Саму задачку решаю алгоритмом Дейкстры
0
 Аватар для LegionK
393 / 263 / 193
Регистрация: 02.05.2017
Сообщений: 1,003
05.02.2019, 17:29
peoplep8, интересная задача, а как именно вы Дейкстрой решаете? Он вроде находит кратчайшее расстояние между двумя вершинами? И если для каждого города в котором нету склада вызывать алгоритм и конечной вершиной выбирать все города в которых склад есть - я думаю оно по времени не пройдет

Добавлено через 16 секунд
peoplep8, или вы как-то по другому делаете?
0
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 49
05.02.2019, 17:29  [ТС]
Пробовал вот так, но даже в цикл не заходит
C++
1
2
3
4
5
6
for(auto i = g.begin(); i != g.end(); ++i)
{
    if(g[j].empty())
        g.erase(i);
    ++j;
}
0
Mental handicap
 Аватар для Azazel-San
1246 / 624 / 171
Регистрация: 24.11.2015
Сообщений: 2,429
05.02.2019, 17:29
Цитата Сообщение от peoplep8 Посмотреть сообщение
пытаюсь коряво убрать изолированные вершины
Вершина хранится в forward_list. Вы проверяете пустой ли ваш список, если это так, вы пытаетесь удалить весь ваш список из вектора, не похоже на удаление вершины.
Цитата Сообщение от peoplep8 Посмотреть сообщение
C++
1
vector<forward_list<Node> >::iterator
Всегда auto в приоритете.
Цитата Сообщение от peoplep8 Посмотреть сообщение
C++
1
g[i]
Нету проверки за выход массива, если nvertex != vector.size имеем выход за границы.
1
 Аватар для LegionK
393 / 263 / 193
Регистрация: 02.05.2017
Сообщений: 1,003
05.02.2019, 17:32
peoplep8, Хотя вообще, я думаю это задание именно на алгоритм Флойда-Уоршелла
Хотя я могу и ошибаться, пройдет ли n^3 для 10^5?
1
Mental handicap
 Аватар для Azazel-San
1246 / 624 / 171
Регистрация: 24.11.2015
Сообщений: 2,429
05.02.2019, 17:32
Цитата Сообщение от peoplep8 Посмотреть сообщение
На строке 75 выдает "Segmentation fault"
Цитата Сообщение от peoplep8 Посмотреть сообщение
g.erase(bi);
Ну офк.. Вы все время пытаетесь удалить первый список из вашего вектора, nvertex-1 раз.
1
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 49
05.02.2019, 17:43  [ТС]
Дейкстра находит кратчайшие расстояния от одной начальной вершины до всех остальных.
Я делаю так:
для каждого склада с мукой нахожу путь до всех остальных вершин
потом в массиве weights (он содержит пути до всех остальных вершин) исключаю расстояния до складов с мукой (мне не нужно знать расстояние от одного склада с мукой для другого)
нахожу минимальный элемен min в weights
заношу min в массив минимальных расстояний mins для каждого склада
выбираю минимальный элемент из mins - это и будет минимальная сумма которую должна Маша заплатить

Добавлено через 7 минут
Azazel-San, если i-й список в векторе g пуст, то я сдвигаю итератор на i и удаляю этот список. Функция advance же сдвигает итератор...
0
 Аватар для LegionK
393 / 263 / 193
Регистрация: 02.05.2017
Сообщений: 1,003
05.02.2019, 17:48
peoplep8, Можно вопрос пожалуйста?
Допустим вы посчитали расстояния для всех складов с мукой ( k* асимптотику Дейкстры(n^2 + m, m можно опустить) т.е у вас n^3 в худшем случае) ,потом вам необходимо я полагаю n^2 * k операций для того,чтобы исключить все склады с мукой из ответов. Зачем же вам удалять изолированные вершины в конце? Если можно на этапе исключения складов с мукой выбрать минимальное растояние?
Ну и n^3 вы уверены что будет работать для 2 сек и n = 10^5 ?
0
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 49
05.02.2019, 17:49  [ТС]
LegionK, возможно, что Флойдом — Уоршеллом проще решить, но Дейкстрой у меня работал для n = 450; m = 20; k = 163; но на n= 10000; m = 5054; k = 3791 получалось MEMORY_LIMIT_EXCEEDED. Я все таки хочу попробовать отослать решение с Дейкстрой. но представляя граф списком смежности, а потом уже разберусь Флойдом — Уоршеллом
0
Mental handicap
 Аватар для Azazel-San
1246 / 624 / 171
Регистрация: 24.11.2015
Сообщений: 2,429
05.02.2019, 17:50
Цитата Сообщение от peoplep8 Посмотреть сообщение
Функция advance же сдвигает итератор...
Та вы шо, жаль в коде который вы нам скинули ее там не существует..
0
 Аватар для LegionK
393 / 263 / 193
Регистрация: 02.05.2017
Сообщений: 1,003
05.02.2019, 17:50
peoplep8, нет,нет, вы неправильно меня поняли, Флойд_Уоршелл имеет такую же асимптотику, т.е n^3
Я намекнул,что возможно там немного другое решение?
Но главная мысль была о том,зачем же вам в конце удалять изолированные вершины?
0
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 49
05.02.2019, 17:57  [ТС]
Azazel-San, я до этого скидывал этот код
C++
1
2
3
4
5
6
7
8
9
10
11
// пытаюсь коряво убрать изолированные вершины
    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;
        }
    }
Но он тоже не верен

Добавлено через 58 секунд
LegionK, я их удаляю не в конце, а в начале, перед работой Дейкстры

Добавлено через 1 минуту
LegionK, Потому что с изолированными вершинами алгоритм Дейкстры путается (вроде входит в бесконечный цикл)

Добавлено через 2 минуты
Вот код полностью, если интересно
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <iostream>
#include <vector>
#include <algorithm>
#include <forward_list>
#include <limits>
 
using namespace std;
 
struct Node
{
    int weight;
    int vertex;
};
 
int main()
{
    vector<forward_list<Node> > g;
    int nvertex, nedges, nFlourWarehouse;
    cin >> nvertex >> nedges >> nFlourWarehouse;
    vector<int> flourWarehouse(nFlourWarehouse);
    g.reserve(nvertex);
    int nv1, nv2, edgeWeight;
    Node *inode = new Node;
    for(int i = 0; i < nedges; i++)
    {
        cin >> nv1 >> nv2 >> edgeWeight;
        --nv1;
        --nv2;
        bool isVertexUnique = true;
        for(forward_list<Node>::iterator itv1 = g[nv1].begin(); itv1 != g[nv1].end(); ++itv1)
        {
            if(itv1->vertex == nv2)
            {
                isVertexUnique = 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(isVertexUnique)
        {
            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;
    
    // уберем изолированные вершины
    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;
        }
    }
    
    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 << ":" << it->weight;
        cout << endl;
    }
    
    int numHouse;
    for(int ihouse = 0; ihouse < nFlourWarehouse; ihouse++)
    {
        cin >> numHouse;
        --numHouse;
        flourWarehouse[ihouse] = numHouse;
    }
    
    vector<int> mins;
    for(int indHouse = 0; indHouse < nFlourWarehouse; indHouse++)
    {
        int dist;
        int v = flourWarehouse[indHouse];
        bool *intree = new bool [nvertex];
        for(int i = 0; i < nvertex; i++)
            intree[i] = false;
        vector<int> weights(nvertex, numeric_limits<int>::max());
        weights[v] = 0;
        vector<int> parent(nvertex, -1);
        while(intree[v] == false)
        {
            intree[v] = true;
            for(forward_list<Node>::iterator ind = g[v].begin(); ind != g[v].end(); ++ind)
            {
                if(weights[v] + ind->weight < weights[ind->vertex])
                {
                    weights[ind->vertex] = weights[v] + ind->weight;
                    parent[ind->vertex] = v;
                }
            }
            v = 1;
            dist = numeric_limits<int>::max();
            for(int j = 0; j < nvertex; j++)
            {
                if((intree[j] == false) && (weights[j] < dist))
                {
                    dist = weights[j];
                    v = j;
                }
            }
        }
        delete [] intree;
        intree = 0;
        
        for(int i = 0; i < nFlourWarehouse; ++i)
        {
            vector<int>::iterator it = weights.begin();
            it += flourWarehouse[i];
            weights.erase(it);
        }
        
        vector<int>::iterator begZero = remove(weights.begin(), weights.end(), 0);
        weights.erase(begZero, weights.end());
        
        int minElem = weights[0];
        for(int j = 1; j < nvertex; ++j)
            if(weights[j] < minElem)
                minElem = weights[j];
        
        mins.push_back(minElem);
    }
    
    vector<int>::iterator sum = min_element(mins.begin(), mins.end());
    cout << *sum;
    
    return 0;
}
0
 Аватар для LegionK
393 / 263 / 193
Регистрация: 02.05.2017
Сообщений: 1,003
05.02.2019, 17:57
peoplep8, дико извиняюсь, но полагаю,что после строки 68 идет только вывод вашего графа (возможно проверка корректности удаления вершин), но ,извиняюсь за нескомный вопрос, зачем же вам удалять вершины из графа? Если вершина изолированна путь в неё так и не будет найден, а асимптотику это не улучшит и не ухудшит в среднем случае. Нет,конечно, есть случаи когда это повлияет в лучшую сторону, но может быть и наоборот.
0
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 49
05.02.2019, 18:01  [ТС]
А все-таки, как же правильно удалить вершину из списка смежности графа средствами STL?
0
 Аватар для LegionK
393 / 263 / 193
Регистрация: 02.05.2017
Сообщений: 1,003
05.02.2019, 18:03
peoplep8, нет,конечно это замечательно, но,вы,наверное не прочитали разбор задания,верно? Конечно,это практика решения задач,это хорошо и замечательно, но там имеется более красивое решение, которое почти не требовательно к памяти и времени выполнения
Так что,если возможно,ваш код, как я предполагаю, не пройдет ряд тестов из-за большой временной сложности, советую посидеть за чашкой чая и подумать над парой моментов в этой задаче, а флойдов и дийкстр оставить на потом)
0
Mental handicap
 Аватар для Azazel-San
1246 / 624 / 171
Регистрация: 24.11.2015
Сообщений: 2,429
05.02.2019, 18:03
Цитата Сообщение от peoplep8 Посмотреть сообщение
Azazel-San, я до этого скидывал этот код
Не вижу в упор, потрохов или хотя б объявления вашей функции advance.
0
9 / 6 / 3
Регистрация: 01.07.2018
Сообщений: 49
05.02.2019, 18:04  [ТС]
LegionK, да, возможно их и не нужно удалять
0
Mental handicap
 Аватар для Azazel-San
1246 / 624 / 171
Регистрация: 24.11.2015
Сообщений: 2,429
05.02.2019, 18:05
Цитата Сообщение от peoplep8 Посмотреть сообщение
Вот код полностью, если интересно
И здесь не вижу.. Правьте код, это невозможно читать. Процедурное программирование уже давно придумали.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
05.02.2019, 18:05
Помогаю со студенческими работами здесь

Ошибка Segmentation fault при вызове glGenBuffers()
Ошибка Segmentation fault (core dumped) в RunTime методом дебагинга понял что падает на glGenBuffers(1, &amp;triangleVBO); помогите...

Segmentation fault при вызове функции
Недавно изучаю си. Пытаюсь скопировать массив параметров argv в новую функцию. Передается 9 параметров по 9 чаров. При входе в...

Segmentation fault при вызове malloc
Щас создавал модуль на Си для работы со списком, думал минутное дело, за 40 мин накатал и уже почти час не могу понять почему выдает...

Segmentation fault при использовании метода show()
Добрый день! После разрешения вопроса, обсуждаемого в форуме https://www.cyberforum.ru/qt/thread2796765.html, вставил в код другие...

Массив указателей, segmentation fault при использовании чистого виртуального метода getvalue()
Проблема с выведением значения в строчке 162. Изначально задача состояла в том, чтобы реализовать базовый класс Item с чистой виртуальной...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer
8Observer8 08.02.2026
Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств
8Observer8 07.02.2026
Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 01.02.2026
Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли
8Observer8 30.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm
8Observer8 30.01.2026
Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru