Multiset container appears to stop sorting

Question

I would appreciate help debugging some strange behavior by a multiset container. Occasionally, the container appears to stop sorting. This is an infrequent error, apparent in only some simulations after a long time, and I'm short on ideas. (I'm an amateur programmer--suggestions of all kinds are welcome.)

My container is a std::multiset that holds Event structs:

typedef std::multiset< Event, std::less< Event > > EventPQ;

with the Event structs sorted by their double time members:

struct Event {

 public:
explicit Event(double t) : time(t), eventID(), hostID(), s() {}
Event(double t, int eid, int hid, int stype) : time(t), eventID( eid ), hostID( hid ), s(stype) {}

  bool operator < ( const Event & rhs ) const {
    return ( time < rhs.time );
  }

  double time;
  ...
};

The program iterates through periods of adding events with unordered times to EventPQ currentEvents and then pulling off events in order. Rarely, after some events have been added (with perfectly 'legal' times), events start getting executed out of order.

What could make the events ever not get ordered properly? (Or what could mess up the iterator?) I have checked that all the added event times are legitimate (i.e., all exceed the current simulation time), and I have also confirmed that the error does not occur because two events happen to get scheduled for the same time.

I'd love suggestions on how to work through this.

The code for executing and adding events is below for the curious:

  double t = 0.0;
  double nextTimeStep = t + EPID_DELTA_T;
  EventPQ::iterator eventIter = currentEvents.begin();

while ( t < EPID_SIM_LENGTH ) {

     // Add some events to currentEvents

     while ( ( *eventIter ).time < nextTimeStep ) { 

         Event thisEvent = *eventIter;
     t = thisEvent.time;
     executeEvent( thisEvent );
     eventCtr++;
     currentEvents.erase( eventIter );
     eventIter = currentEvents.begin();

  }

  t = nextTimeStep;
  nextTimeStep += EPID_DELTA_T;
}


void Simulation::addEvent( double et, int eid, int hid, int s ) {
  assert( currentEvents.find( Event(et) ) == currentEvents.end() );

  Event thisEvent( et, eid, hid, s ); 
  currentEvents.insert( thisEvent );
}

---

I should add that occasionally an event, when executed, will delete other events from currentEvents. This is done with

double oldRecTime = 10.0; // gets defined legitimately in simulation
EventPQ::iterator epqItr = currentEvents.find( Event(oldRecTime) );
assert( currentEvents.count( Event(oldRecTime) ) == 1 );
currentEvents.erase( epqItr );

Even if this code looks okay, I'd like to know other ways I can examine what's going on--I'm currently using a lot of asserts() and cout << checks.

Answer 1

In the simulation, where I have commented

// Add some events to currentEvents

events were being added to currentEvents. (Hope that was clear.) If an event was added that happened to belong at the top of the queue, I believe it messed up the iterator pointing to currentEvents.begin(). I reset the iterator immediately before the inner while loop, and things appear to work.

I will update this question if this turns out not to be the solution, or if there are other problems in what I have here.

Thanks to all those who commented; it helps me learn how I should be approaching these problems.

Answer 2

Your event processing cycle fails to check whether the queue is empty. Otherwise, everything looks fine (more or less).

But if you run out of events in your currentEvents queue, the behavior is undefined. It could probably manifest itself as something the appears as event being processed out of order.

In fact, some implementations of associative containers I saw represented them by "virtually circular" data structures, in a sense that if you ignore the end of the controlled sequence and continue to iterate, your iterator will emerge at the beginning of the sequence. Could it be that something like that is happening in your case?

Another question that immediately arises in connection with your code: what happens if the new event arrives into the queue with the time value that is smaller than the "current" time? I don't see any checks that would capture this situation in your code. Obviously, if this happens, i.e. if some events arrive "too late", they might easily get processed out of order regardless of how you implement it.

Answer 3

If at all possible, I'd advise changing the double you're using as a key to some integer type instead. The key for a set or multiset requires a strict weak ordering -- and a double does not (normally) meet that requirement (nor does any other IEEE floating point type).