Find all trains which overtake another train

My task: find all trains, which overtake another train and return their trainId.

Implementation-suggestion:

for all trains B
    for all trains A
        find station C, where A departs and B later departs than A (the earliest one)
            if there is such one
                for all stations D, where A stops after C and B also stops
                    if B stops at D earlier than A, then B is a overtaker!

I implemented the algorithm, but it is very very slow, I need some help to improve this code. I have 3 input (.dat) files, where I build of each a Object which is like a list (StationList, TrainList, Schedule) and of each line (in this files) a own Object (Train, Station, Entry) which are all entries of the respective "list".

train.h

#ifndef TRAIN_H
#define TRAIN_H

#include 
#include 

using namespace std;

class Train{
public:
  Train(string s);
  Train(int pId);     //for comparisons

  bool operator trains;
};

#endif

train.cc

#include 
#include 
#include 
#include 
#include "train.h"

using namespace std;

Train::Train(string s) {
  stringstream ss(s);
  ss >> id >> numberOfWaggons;
}

Train::Train(int pId) {
  id = pId;
}

TrainList::TrainList(char const *filename){
  ifstream input(filename);
  string line;

  while(getline(input,line))
    trains.push_back(Train(line));

  sort(trains.begin(), trains.end());
}

bool Train::operator< (const Train &t) const {
  return id < t.id;
}

station.h

#ifndef STATION_H
#define STATION_H

#include 
#include 

using namespace std;

class Station {
public:
  Station(string s);
  Station(int pId);   // for comparisons

  string getName();
  bool operator stations;
};

#endif

station.cc

```
#include
#include
#include
#include
#include "station.h"

using namespace std;

Station::Station(string s) {
stringstream ss(s);
ss >> id >> name;
}

Station::Station(int pId) {
id = pId;
}

StationList::StationList(char const *filename){
ifstream input(filename);
string line;

The algorithm is not ugly. Every step is necessary, but it can be tweaked to avoid doing unnecessary work.

1. Speed up by skipping instructions

The easiest way to speed up algorithms with nested loops is to bail out of each loop as quickly as possible. For example:

int departureA = schedule.lookup(trains.give(a).getId(), stations.give(c).getId(), 1);
    int departureB = schedule.lookup(trains.give(b).getId(), stations.give(c).getId(), 1);

    if(departureA == -1 || departureB == -1)
      continue;

If the first schedule.lookup(...) for departureA returns -1, then you don't need to do the second lookup.

int departureA = schedule.lookup(trains.give(a).getId(), stations.give(c).getId(), 1);
    if(departureA == -1)
      continue;

    int departureB = schedule.lookup(trains.give(b).getId(), stations.give(c).getId(), 1);
    if(departureB == -1)
      continue;

Do the same in the inner loop for arrivalA and arrivalB.

Even earlier:

for(int b = 0; b < trains.length(); b++){
  for(int a = 0; a < trains.length(); a++){
    if(a == b) { continue; } // A train can't overtake itself.

1. Speed up by using the structure of the data

You can quickly find a name in a large phone book because the names are sorted. You sort TrainList, StationList, and the Entrys in Schedule, but don't make use of the fact that the lists are sorted. C++'s std::find searches through the entire list and does not stop when it has passed where an entry should be if it existed. So, write your own search routine that stops if it reaches an Entry that is larger than the search item (as defined by operator



• Entry::parameter is never used.






• There are two types of Entrys: one that contains the schedule information, and one that just contains train and station IDs. I see how you're using it in the Schedule::lookup(...) method to find the Entry with the complete data, but it's a bit confusing at first to see an Entry be created in order to search for it. You already have the Entry, why are you looking for it?






• The output of main()` does not actually identify the overtaken trains.

StackExchange Code Review Q#151880, answer score: 2