复制 STL
标准模板库包括许多不同类型的容器。所有容器都是通用的，因为模板参数允许我们创建任何类型对象的容器。我正在编写一个容器包装类，我的目标是保留这个选区。我喜欢将此视为我的第一个约束。
需要注意的其他限制是： 容器始终包含按优先级顺序排列的事件。（按照它们应该发生的时间顺序。）此外，与事件相关联的任何粒子仅在事件队列中出现一次。想象一个有 3 个粒子的世界，粒子 M、N 和 O。如果检测到粒子 M 和 N 在未来有一个事件，并且该事件已经在事件队列中，那么粒子 M 和粒子 N 都不会在与不同事件关联的事件队列。这意味着如果粒子 N 和粒子 O 也被检测到有一个事件，它不会存储在队列中，因为粒子 N 已经与粒子 M 发生了一个事件，该事件已经在队列中。这两个约束并不重要，但了解它们可能对您有用。
事件队列
为了帮助理解，我们现在将绕道这个问题背后的背景。
我正在尝试实现类似于优先队列的东西，除了我需要能够访问随机元素和删除元素。为什么我需要这样做，稍后会解释。
我正在编写一个涉及粒子的模拟，以及在未来可计算时间发生在粒子对之间的事件。下面是粒子类的代码。
// particle.hpp
class Particle
{
};
这里的所有都是它的。在另一个项目中，我有一个完整的粒子实现。在这个项目中还有一个函数，它实现了一种算法，该算法检测粒子对之间的事件并计算这些事件发生的时间。我希望你能欣赏我在这里尽可能地简化一切。
所以，一个向量中存在着无数个粒子，一对粒子可能会在未来的某个时间产生一个事件，这个事件是可以计算的。现在让我们看一下包含有关这些事件的关键数据的事件类。
// event.hpp
class Event
{
/* Event contains a variable to hold the time at which it occurs, and
* two pointers which point to the two particles which are associated
* with the event. */
// Construct events with time and associated particles
Event(double _time, Particle* _a, Particle* _b);
// Other Methods to return the time of the event, and pointers
// to each of the particles involved in the event
double time()
{
return m_time;
}
Particle* particleA()
{
return m_particle_a;
}
// Member data
double m_time;
Particle* m_particle_a, m_particle_b;
};
// Event needs an `operator<` for comparing event times, which I have not shown.
好的，因此您可以看到如何在粒子对之间检测到事件时，有关事件时间以及涉及哪些粒子的数据可以存储在此事件类中。然后将多个事件打包到一个类似于优先级队列的容器中，该队列允许随机访问元素并删除容器内的任何元素。请记住，我正在尝试复制 STL 的想法，以使该容器通用以供将来使用。这就是问题开始出现的地方。现在让我们看一下容器类。（为冲击做好准备？）
// eventqueue.hpp
template<typename T> // Allow this container be a container of `Event`'s
class EventQueue
{
void push(const T& _elem); // Function to insert element into correct position
// This requires use of the `operator<`, which compares
// `_elem < m_container[i]`
// and depending on the result of said comparison will
// insert the `_elem` into the correct place according
// to priority. (Remember `operator<` is overloaded to
// compare event times.
// Below is the problem function.
// This function is supposed to take a user defined function, `_func_p`, which
// compares an element `_e`, which is also the argument to the function,
// `_external_element`, and returns a boolean signifying if the element is to be
// removed or not. I have included the implementation to show you in more detail.
// The problem is obvious: `Event&` means this container is not general!
// It will only work for the type `Event`
void remove_if(bool (*_func_p)(T& _element, Event& _external_element), Event& _e)
{
for(int i = 0; i != m_container.size(); i ++)
{
if((*_func_p)(m_container[i], _e))
{
m_container.erase(m_container.begin() + i);
break; // Pairs of events means at maximum, one item is to be removed.
}
}
}
const T& at(int _index); // Function to return element at position `_index`
// Other functions not included here are functions to peak() top element
// and pop elements. Also stuff like `size()` `empty()` and `clear()`.
// Member data
vector<T> m_container;
};
好的，这是相当大的，但重点是用户应该能够定义一个函数来true决定false是否应该删除一个事件。要了解为什么需要这样做，请参阅事件说明部分。
这是做出该决定的功能。
bool remove_if_event_is_invalidated(Event& _event_a, Event& _event_b)
{
Particle* A = _event_a.particleA();
Particle* B = _event_a.particleB();
Particle* C = _event_b.particleA();
Particle* D = _event_b.particleB();
return (A == C || A == D || B == C || B == D) && (_event_a.time() < _event_b.time());
}
本质上，它检查是否有任何参与新事件的粒子_event_a已经参与了另一个事件_event_b。如果您已经阅读了最后一节，那么您可能会明白，在满足“条件 3”的情况下，新创建的事件会使旧事件无效，因此旧的事件需要从事件队列中移除，新的事件一个需要添加。“条件2”是新事件不会使任何旧事件无效，因为新事件发生在任何现有事件涉及相同粒子之后。
事件解释
一旦事件队列被事件填充，最高优先级的事件就会被处理。这是最快发生的事件。事件队列始终包含根据事件发生的时间排序的事件 - 以优先级顺序。
处理事件时，可能会发生几件事：
1:) 什么都没有发生：事件被处理，结果没有新的事件被创建。因此，无需做任何事情。
2:) 在刚刚处理的事件中涉及的一个粒子（称为粒子 Y）和另一个粒子（称为粒子 Z）之间创建一个新事件。然而，新事件发生在粒子 Y 与另一个粒子（称为粒子 U）参与另一个事件之后的时间：因此，粒子 Y 和粒子 U 在粒子 Y 与粒子 Z 相互作用之前相互作用，因此 Y 和 U 之间的事件很可能使 Y 和 Z 之间的事件无效，因此我们不再做任何事情。
3:) 创建了一个新事件，与 2:) 完全相同，但是新创建的事件发生在事件队列中的另一个事件之前，因此使队列中的当前事件无效。这很有趣，因为失效的事件必须从事件队列中移除，而新创建的事件必须插入到正确的位置。这就产生了对 的要求operator<，这是对 的友好函数class Event。这也有连锁反应，好像新创建的事件发生在队列中的许多其他事件之前，该事件的处理可能会使稍后发生的其他事件无效，但这并不重要。