Why is this code resulting in a segmentation fault?

Question

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>

using namespace std;

int n = 17;
vector < string > ports (n, "");
vector < string > checked (ports);
multimap < string, string > routes;

void check_routes (string x)
{
//  checked.erase (std::remove (checked.begin (), checked.end (), x));

    for (vector < string >::iterator it1 = checked.begin ();it1 != checked.end (); it1++)
    {
        if (*it1 == x)
        {
            checked.erase (it1);
        }
    }

    for (multimap < string, string >::iterator it = routes.begin ();
       it != routes.end (); it++)
    {
        if (it->first == x)
        {
            check_routes (it->second);
        }
    }
}

int main ()
{
  int ans = 0;
  ports.push_back ("BUD");
  ports.push_back ("BGI");
  ports.push_back ("DEL");
  ports.push_back ("DOH");
  ports.push_back ("DSM");
  ports.push_back ("EWR");
  ports.push_back ("EYW");
  ports.push_back ("HND");
  ports.push_back ("ICN");
  ports.push_back ("JFK");
  ports.push_back ("LGA");
  ports.push_back ("LHR");
  ports.push_back ("ORD");
  ports.push_back ("BSAN");
  ports.push_back ("SFO");
  ports.push_back ("SIN");
  ports.push_back ("TLV");
  routes.insert (make_pair ("DMS", "ORD"));
  routes.insert (make_pair ("ORD", "BGI"));
  routes.insert (make_pair ("BGI", "LGA"));
  routes.insert (make_pair ("SIN", "CDG"));
  routes.insert (make_pair ("CDG", "SIN"));
  routes.insert (make_pair ("CDG", "BUD"));
  routes.insert (make_pair ("DEL", "DOH"));
  routes.insert (make_pair ("DEL", "CDG"));
  routes.insert (make_pair ("TLV", "DEL"));
  routes.insert (make_pair ("EWR", "HND"));
  routes.insert (make_pair ("HND", "ICN"));
  routes.insert (make_pair ("HND", "JFK"));
  routes.insert (make_pair ("ICN", "JFK"));
  routes.insert (make_pair ("JFK", "LGA"));
  routes.insert (make_pair ("EYW", "LHR"));
  routes.insert (make_pair ("LHR", "SFO"));
  routes.insert (make_pair ("SFO", "SAN"));
  routes.insert (make_pair ("SFO", "DSM"));
  routes.insert (make_pair ("SAN", "EYW"));
  for (int i = 0; !(checked.empty ()); i++)
    {
      check_routes (checked[i]);
      ans++;
    }
  cout << ans;
  return 0;
}

So I was trying to solve the airport connections problem I found online and this is my take on it. But I cannot figure out where the fault in the code lies. I'd be grateful if someone could help me with that. (P.S. The problem goes like this - I have list of airports(vector ports) and another one of one way connections between these ports(multimap routes) and I need to find out the minimum number of connections I need to make so as to connect all the ports(length of the connection does not matter)..................... What this code is supposed to do is find the number of individual chains/networks of interconnected ports, which, I believe, will give me the required answer since all I need to do is connect one node from each of those chains)

Why won't you just use a debugger and trace with breakpoints the exact line with segmentation fault? — Alexey S. Larionov, May 09 '20 at 11:07
Your for loop uses i, but it's conditional on checked not being empty, so you can easily go off the end of the vector. — Ian4264, May 09 '20 at 11:08
@Evg yep, got it.... thank you so much.... and pardon me, if you will, for the rookie mistake.... I'm just a beginner and am just trying to know STL a bit better. — , May 09 '20 at 11:40

score 2 · Answer 1 · answered May 09 '20 at 11:17

2

As Evg says, the problem is here:

for (vector < string >::iterator it1 = checked.begin ();it1 != checked.end (); it1++)
{
    if (*it1 == x)
    {
        checked.erase (it1);
    }
}

erase invalidates all iterators in vector from the element erased onwards, so, next time round the loop, what the program does is undefined (in your case it segfaults, probably when it runs off the end of the array).

The usual solution is to use the erase remove idiom with help from the algorithm library as follows:

checked.erase (std::remove (checked.begin (), checked.end (), x));

Then, it works.

Live demo

answered May 09 '20 at 11:17

Paul Sanders

24,133
4
26
48

Great solution, I see now where I went wrong..... You mean that in my solution, it1 is just left dangling, right ? – May 09 '20 at 11:25
Pretty much, yes, see: https://en.cppreference.com/w/cpp/container/vector/erase – Paul Sanders May 09 '20 at 11:26

score 0 · Answer 2 · answered May 09 '20 at 11:07

0

This is a common problem of modifying a list while traversing it. You erase or move elements from the list which means that the list becomes another list that needs another behaviour from you. At the end, you'll find that you access elements or positions that are out of bound. In my opinion, you need to change your thinking about this problem.

answered May 09 '20 at 11:07

Mohammed Deifallah

1,290
1
10
25

Yeah, I may just have to do that.... Although do you think the whole logic of the solution is wrong ? Or is it just the implementation ? – May 09 '20 at 11:37
It's an implementation problem. Please note that if my answer sounds good, upvote it. – Mohammed Deifallah May 09 '20 at 14:08

Why is this code resulting in a segmentation fault?

2 Answers2