Le conteneur multiset semble arrêter le tri

Question

J'apprécierais l'aide pour déboguer un comportement étrange par un conteneur multiset. Parfois, le conteneur semble arrêter le tri. C'est une erreur peu fréquente, apparente dans 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 Event struct:

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

avec les Event struct triés par double time membres:

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 parcourt des périodes d'ajout d'événements avec des temps non ordonnés à EventPQ currentEvents, puis d'extraction des événements dans l'ordre. Rarement, après que certains événements ont été ajoutés (avec des temps parfaitement «légaux»), les événements commencent à être exécutés dans le désordre.

Qu'est-ce qui pourrait rendre les événements jamais correctement ordonnés? (Ou qu'est-ce qui pourrait gâcher l'itérateur?) J'ai vérifié que tous les temps d'événements ajoutés sont légitimes (ie, tous dépassent le temps de simulation actuel), et j'ai également confirmé que l'erreur ne se produisait pas parce que deux événements prévu pour le même temps.

J'aimerais des suggestions sur la façon de travailler à travers 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 de temps en temps 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 < < vérifications.

Answer 1

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

// Add some events to currentEvents 

événements ont été ajoutés à currentevents. (Espérons que c'était clair.) Si un événement qui s'est avéré être en haut de la file d'attente a été ajouté, je crois qu'il a foiré l'itérateur pointant vers currentEvents.begin(). J'ai réinitialisé l'itérateur immédiatement avant la boucle while interne, et les choses semblent fonctionner.

Je vais mettre à jour cette question si cela ne s'avère 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é; cela m'aide à apprendre comment 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. Sinon, tout va bien (plus ou moins). Mais si vous n'avez plus d'événements dans votre file d'attente currentEvents, le comportement n'est pas défini.

Il pourrait probablement se manifester comme quelque chose qui apparaît comme un événement en cours de traitement. En fait, certaines implémentations de conteneurs associatifs que je voyais les représentaient par des structures de données "pratiquement circulaires", en ce sens que si vous ignorez la fin de la séquence contrôlée et continuez à itérer, votre itérateur apparaîtra 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 en rapport avec votre code: que se passe-t-il si le nouvel événement arrive dans la file d'attente avec la valeur time qui est inférieure à l'heure "actuelle"? Je ne vois pas de contrôles qui captureraient cette situation dans votre code. Evidemment, si cela se produit, c'est-à-dire si certains événements arrivent "trop ​​tard", ils peuvent facilement être traités dans le désordre, quelle que soit la façon dont vous l'implémentez.

Answer 3

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