Multiset récipient semble cesser de tri

Question

J'apprécierait l'aide de débogage un comportement étrange par un conteneur multiset. De temps en temps, le conteneur semble arrêter le tri. Ceci est une erreur peu fréquente, apparente seulement quelques simulations après une longue période, et je suis à court d'idées. (Je suis un programmeur amateur - suggestions de toutes sortes sont les bienvenus.)

Mon conteneur est un std::multiset qui détient structs Event:

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

avec les structs Event triée par leurs membres de double time:

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;
  ...
};

Le programme itère par des périodes de l'ajout d'événements avec des temps désordonnées à EventPQ currentEvents puis tirant sur les événements dans l'ordre. Rarement, après quelques événements ont été ajoutés (avec parfaitement temps « légal »), les événements commencent à s'exécuter hors service.

Que pourrait faire les événements jamais de ne pas se commander correctement? (Ou ce qui pourrait gâcher la iterator?) J'ai vérifié que tous les temps de l'événement ajoutés sont légitimes (c.-à-tout dépasser le temps de simulation en cours), et je l'ai également confirmé que l'erreur ne se produit pas parce que deux événements Il se trouve que ordonnancé pour en même temps.

J'adorerait des suggestions sur la façon de travailler grâce à cela.

Le code pour l'exécution et l'ajout d'événements ci-dessous pour les curieux:

  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 );
}

---

Je dois ajouter que, parfois, un événement, lorsqu'il est exécuté, effacera d'autres événements de currentEvents. Cela se fait avec

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 );

Même si ce code semble correct, je voudrais savoir d'autres façons d'examiner ce qui se passe -. Je utilise actuellement beaucoup d'affirme () et Cout << chèques

Answer 1

Dans la simulation, où je l'ai commenté

// Add some events to currentEvents

événements ont été ajouté à currentevents. (Hope qui était clair.) Si un événement a été ajouté qui est arrivé à appartenir au sommet de la file d'attente, je crois qu'il foiré le pointage iterator à currentEvents.begin (). Réinitialiser l'itérateur immédiatement avant la boucle while intérieure, et les choses semblent fonctionner.

Je mettrai à jour cette question si cela se révèle pas être la solution, ou s'il y a d'autres problèmes dans ce que j'ai ici.

Merci à tous ceux qui ont commenté; il me permet d'apprendre que je devrais aborder ces problèmes.

Answer 2

Votre cycle de traitement des événements ne vérifie pas si la file d'attente est vide. Dans le cas contraire, tout semble bien (plus ou moins).

Mais si vous manquez d'événements dans votre file d'attente currentEvents, le comportement est indéfini. Il pourrait probablement se manifester comme quelque chose apparaît comme l'événement en cours de traitement hors d'usage.

En fait, certaines implémentations de conteneurs associatifs je les ai vus Représenté par des structures de données « pratiquement circulaires », dans un sens que si vous ignorez la fin de la séquence contrôlée et continuer à itérer, votre iterator sortira au début de la séquence. Se pourrait-il que quelque chose comme ça se passe dans votre cas?

Une autre question qui se pose immédiatement dans le cadre de votre code: ce qui se passe si le nouvel événement arrive dans la file d'attente avec la valeur time qui est plus petit que le temps « courant »? Je ne vois pas de chèques qui capturerait cette situation dans votre code. De toute évidence, si cela se produit, à savoir si certains événements arrivent « trop tard », ils pourraient facilement se traiter hors service quelle que soit la façon dont vous le mettre en œuvre.

Answer 3

Si possible, je vous conseille de changer le double que vous utilisez comme une clé pour un type entier au lieu. La clé pour une set ou multiset nécessite une commande faible stricte - et un double fait pas (normalement) répondre à cette exigence (ni ne importe quel autre type de virgule flottante IEEE)

.