Контейнер мультимножества, кажется, прекращает сортировать

Я ценил бы справку, отлаживающую некоторое странное поведение контейнером мультимножества. Иногда, контейнер, кажется, прекращает сортировать. Это - нечастая ошибка, очевидная только на некоторых моделированиях после долгого времени, и я короток на идеях. (Я - программист-любитель - предложения всех видов приветствуются.)

Мой контейнер является a 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 );

Даже если бы этот код смотрит хорошо, я хотел бы знать другие способы, которыми я могу исследовать то, что продолжается - я в настоящее время использую много из, утверждает () и суд <<проверки.

1
задан Sarah 17 May 2010 в 20:40
поделиться

3 ответа

В симуляции, где я прокомментировал

// Add some events to currentEvents

события добавлялись в currentEvents. (Надеюсь, это было понятно.) Если добавлялось событие, которое находилось в верхней части очереди, я полагаю, что это испортило итератор, указывающий на currentEvents.begin(). Я сбросил итератор непосредственно перед внутренним циклом while, и все заработало.

Я обновлю этот вопрос, если окажется, что это не решение, или если возникнут другие проблемы в том, что у меня здесь.

Спасибо всем, кто прокомментировал; это помогает мне узнать, как я должен подходить к решению этих проблем.

0
ответ дан 3 September 2019 в 00:29
поделиться

Ваш цикл обработки событий не может проверить, пуста ли очередь. В остальном все выглядит нормально (более-менее).

Но если в вашей очереди currentEvents заканчиваются события, поведение не определено. Вероятно, это могло проявиться как нечто, что выглядит как событие, обрабатываемое не по порядку.

Фактически, некоторые реализации ассоциативных контейнеров, которые я видел, представляли их «практически круговыми» структурами данных в том смысле, что если вы проигнорируете конец управляемой последовательности и продолжите итерацию, ваш итератор появится в начале последовательность. Может быть, что-то подобное происходит в вашем случае?

Другой вопрос, который сразу же возникает в связи с вашим кодом: что произойдет, если новое событие поступит в очередь с меньшим значением time чем "текущее" время? Я не вижу никаких проверок, которые могли бы зафиксировать эту ситуацию в вашем коде. Очевидно, что если это произойдет, то есть если некоторые события прибудут «слишком поздно», они могут быть легко обработаны не по порядку, независимо от того, как вы это реализуете.

1
ответ дан 3 September 2019 в 00:29
поделиться

Если это возможно, я бы посоветовал заменить double, который вы используете в качестве ключа, на какой-нибудь целочисленный тип. Ключ для множества или мультимножества требует строгого слабого упорядочения - а double не (обычно) удовлетворяет этому требованию (как и любой другой тип с плавающей запятой IEEE).

1
ответ дан 3 September 2019 в 00:29
поделиться
Другие вопросы по тегам:

Похожие вопросы: