يبدو أن الحاوية المتعددة تتوقف عن الفرز

Question

سأكون ممتنا للمساعدة في تصحيح بعض السلوك الغريب من قبل حاوية متعددة المدى. في بعض الأحيان ، يبدو أن الحاوية تتوقف عن الفرز. هذا خطأ نادر ، واضح فقط في بعض عمليات المحاكاة بعد وقت طويل ، وأنا قصير في الأفكار. (أنا مبرمج للهواة-نرحب بجميع الأنواع.)

حاوية بلدي std::multiset الذي يحمل Event الهياكل:

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

مع ال Event الهياكل المرتبة من قبلهم 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;
  ...
};

يتكرر البرنامج خلال فترات إضافة الأحداث بأوقات غير مرتبة إلى EventPQ currentEvents ثم سحب الأحداث بالترتيب. نادراً ما يتم إضافة بعض الأحداث (بأوقات قانونية تمامًا) ، تبدأ الأحداث في تنفيذها.

ما الذي يمكن أن يجعل الأحداث لا يتم طلبها بشكل صحيح؟ (أو ماذا يمكن أن يفسد التكرار؟) لقد راجعت أن جميع أوقات الأحداث المضافة مشروعة (أي ، كلها تتجاوز وقت المحاكاة الحالي) ، وقد أكدت أيضًا أن الخطأ لا يحدث لأن حدثين يحدثان في نفس الوقت.

أحب الاقتراحات حول كيفية العمل من خلال هذا.

رمز التنفيذ وإضافة الأحداث أدناه للفضول:

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

---

يجب أن أضيف ذلك من حين لآخر حدثًا ، عند تنفيذه ، سيحذف أحداث أخرى من currentEvents. يتم ذلك مع

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

حتى لو كان هذا الرمز على ما يرام ، أود أن أعرف طرقًا أخرى يمكنني من خلالها دراسة ما يجري-أنا أستخدم حاليًا الكثير من التأكيدات () و cout << الشيكات.

Answer 1

في المحاكاة ، حيث علقت

// Add some events to currentEvents

تمت إضافة الأحداث إلى Currentevents. (نأمل أن يكون ذلك واضحًا.) إذا تمت إضافة حدث ما حدث في الجزء العلوي من قائمة الانتظار ، أعتقد أنه أفسد التكرار الذي يشير إلى currentevents.begin (). أقوم بإعادة ضبط التكرار مباشرة قبل الداخلية أثناء الحلقة ، ويبدو أن الأمور تعمل.

سأقوم بتحديث هذا السؤال ما إذا كان هذا لا يكون الحل ، أو إذا كانت هناك مشاكل أخرى في ما لدي هنا.

شكرا لجميع الذين علقوا ؛ يساعدني ذلك على تعلم كيف يجب أن أقترب من هذه المشكلات.

Answer 2

تفشل دورة معالجة الحدث الخاصة بك في التحقق مما إذا كانت قائمة الانتظار فارغة. خلاف ذلك ، يبدو كل شيء على ما يرام (أكثر أو أقل).

ولكن إذا نفدت الأحداث في currentEvents قائمة الانتظار ، السلوك غير محدد. ربما يمكن أن تظهر نفسها كشيء يظهر كحدث يتم معالجته خارج الترتيب.

في الواقع ، بعض تطبيقات الحاويات الترابطية التي رأيتها تمثلها بهياكل بيانات "دائرية تقريبًا" ، بمعنى أنه إذا تجاهلت نهاية التسلسل المتحكم فيه واستمرت في التكرار ، فسوف يظهر مؤلفك في بداية التسلسل. هل يمكن أن يحدث شيء من هذا القبيل في قضيتك؟

سؤال آخر ينشأ على الفور فيما يتعلق بالرمز الخاص بك: ماذا يحدث إذا وصل الحدث الجديد إلى قائمة الانتظار مع time القيمة الأصغر من الوقت "الحالي"؟ لا أرى أي شيكات من شأنها أن تلتقط هذا الموقف في الكود الخاص بك. من الواضح ، إذا حدث هذا ، أي إذا وصلت بعض الأحداث "بعد فوات الأوان" ، فقد يتم معالجتها بسهولة من الترتيب بغض النظر عن كيفية تنفيذها.

Answer 3

إذا كان ذلك ممكنًا ، أنصح بتغيير double أنت تستخدم كمفتاح لبعض النوع الصحيح بدلاً من ذلك. مفتاح أ set أو multiset يتطلب ترتيب ضعيف صارم - و double يفعل ليس (عادة) تلبية هذا الشرط (ولا أي نوع آخر من نقطة العائمة).