c++ - 复制STL:删除元素，用户定义的函数作为参数和事件队列

Question

复制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”的情况下，新创建的事件会使旧事件无效，因此，旧事件需要从事件que和新事件中删除一个需要补充。 “条件2”是新事件不会使任何旧事件无效，因为新事件发生在任何涉及相同粒子的现有事件之后。

事件解释

用事件填充事件队列后，将处理最高优先级的事件。这是最快发生的事件。事件队列始终包含事件，这些事件根据事件发生的时间进行排序-优先顺序。

处理事件时，可能会发生几件事：

1 ：）什么都没有发生：处理该事件，因此不会创建任何新事件。因此，无需执行任何操作。

2 ：)在一个刚刚涉及到该事件的粒子（称为粒子Y）和另一个粒子（称为粒子Z）之间创建了一个新事件。但是，新事件是在粒子Y与另一个粒子（称为粒子U）参与另一个事件之后发生的：因此，粒子Y和粒子U在粒子Y与粒子Z发生相互作用之前发生了相互作用，因此，Y和U之间的事件可能会使Y和Z之间的事件无效，因此我们不再执行任何操作。

3 ：）将与2 ：）一样创建一个新事件，但是新创建的事件在事件队列中的另一个事件之前发生，因此使队列中当前的后一个事件无效。这很有趣，因为必须从事件队列中删除无效事件，并且必须将新创建的事件插入正确的位置。这引起了对operator<的要求，这是class Event的友好功能。这也有连锁反应的结果，好像新创建的事件在队列中的许多其他事件之前发生一样，对该事件的处理可能会使以后发生的其他事件无效，但这并不重要。

Answer 1

我不清楚为什么_external_element的声明中_e和Event &的类型都是remove_if。似乎您期望容器为EventQueue<Event>-为什么不能像T&那样将它们声明为_element类型？

如果缺少某些内容，似乎另一个选择是向EventQueue添加第二个模板参数。例如，如果T不是Event，但是您仍然需要将T类型的对象与Event类型的对象进行比较，并且想要通用地执行此操作，则可以将EventQueue声明为：

template <typename T, typename CompT>
class EventQueue
{
    void remove_if(bool (*_func_p)(T& _element, CompT& _external_element), CompT& _e);
    ...
};

如果这还不够，因为有几种类型不是T而是与T相关，那么第二个参数可能是特征类型，就像您在标准库中有时看到的那样：

template <typename T, typename T_Traits>
class EventQueue
{
    void remove_if(bool (*_func_p)(T& _element, typename T_Traits::CompT& _external_element), typename T_Traits::CompT& _e);
};

struct Foo_Traits
{
    typedef Bar CompT;
    typedef Bar2 OtherT;
};

EventQueue<Foo, Foo_Traits> e;

这样，您就可以在发现新的相关类型时添加它们，而无需每次都添加新的模板参数。当然，如果较早的选项之一可以胜任，那只是太过分了。