仅在 C++ 列表的一部分上约束 remove_if

Question

我有一个 C++11 复杂元素列表，这些元素由结构 node_info 定义。特别是，node_info 元素包含一个字段 time，并根据其 time 字段值以有序方式插入到列表中。也就是说，该列表包含 node_info 个 time 有序的元素。我想从此列表中删除验证 coincidence_detect 指定的某些特定条件的所有节点，我目前将其作为 remove_if 操作的谓词来实现。

由于我的列表可能非常大（100k - 10M 个元素），并且对于我构建列表的方式，此 coincidence_detect 条件仅由接近"lower" 列表末尾——即包含 time 值小于某些 t_xv 的元素的那个，我认为为了提高我的代码速度我不需要运行 remove_if遍历整个列表，但仅将其限制为列表中 time < t_xv 的所有元素。

remove_if() 虽然似乎不允许用户控制我可以遍历列表的哪一点。

我当前的代码。列表元素：

struct node_info {
char   *type = "x";
int    ID    = -1;
double time  = 0.0;
bool   spk   = true;
};

predicate/condition 为 remove_if:

// Remove all events occurring at t_event
class coincident_events {
double t_event; // Event time
bool   spk;     // Spike condition
public:
    coincident_events(double time,bool spk_) : t_event(time), spk(spk_){}
    bool operator()(node_info node_event){
        return ((node_event.time==t_event)&&(node_event.spk==spk)&&(strcmp(node_event.type,"x")!=0));
    }
};

实际从列表中删除：

void remove_from_list(double t_event, bool spk_){
// Remove all events occurring at t_event
coincident_events coincidence(t_event,spk_);
event_heap.remove_if(coincidence);
}

伪主：

int main(){
    // My list
    std::list<node_info> event_heap;

    ...
    // Populate list with elements with random time values, yet ordered in ascending order
    ...

    remove_from_list(0.5, true);

    return 1;
}

似乎 remove_if 在这种情况下可能并不理想。我是否应该考虑实例化一个迭代器和运行一个显式的 for 循环，例如 this post?

中的建议

Answer 1

It seems that remove_if may not be ideal in this context. Should I consider instead instantiating an iterator and run an explicit for loop?

是的，是的。不要为使用阻碍您实现目标的代码而战。把事情简单化。循环在 C++ 中没有什么可耻的。

Answer 2

首先，完全比较 double 不是一个好主意，因为您容易出现浮点错误。

您始终可以使用 lower_bound 搜索到您想搜索的位置（我假设您的列表已正确排序）。

您可以使用自由函数算法 std::remove_if 后跟 std::erase 来删除 remove_if 返回的迭代器和 lower_bound 返回的迭代器之间的项目。

但是，这样做会多次传递数据，并且会移动节点，这会影响性能。

另请参阅：https://en.cppreference.com/w/cpp/algorithm/remove

所以最后，最好在整个容器上执行自己的循环，并针对每个检查是否需要删除它。如果不是，则检查是否应该跳出循环。

for (auto it = event_heap.begin(); it != event_heap.end(); )
{
    if (coincidence(*it))
    {
        auto itErase = it;
        ++it;
        event_heap.erase(itErase)
    }
    else if (it->time < t_xv)
    {
        ++it;
    }
    else
    {
        break;
    }
}

如您所见，对于本应简单的代码，代码很容易变得很长。因此，如果您需要经常执行此类算法，请考虑编写您自己的通用算法。

此外，如果您按递增的时间顺序处理数据，实际上您可能不需要使用第一个解决方案对结尾进行完整搜索。

最后，您可以考虑使用 std::set。它可以导致更简单和更优化的代码。

Answer 3

谢谢。我参考了您的意见并提出了这个解决方案，它似乎将速度提高了 5 到 10 倍。

void remove_from_list(double t_event,bool spk_){
    coincident_events coincidence(t_event,spk_);
    for(auto it=event_heap.begin();it!=event_heap.end();){
        if(t_event>=it->time){
            if(coincidence(*it)) {
                it = event_heap.erase(it);
            }
            else
                ++it;
        }
        else
            break;
        }
}

制作 erase return it（已经 ++it）的想法是由 this other post 提出的。请注意，在这个实现中，我实际上擦除了所有列表元素，直到 t_event 值（意思是，我为 t_xv 传递了我想要的任何内容）。

仅在 C++ 列表的一部分上约束 remove_if

Constraining remove_if on only part of a C++ list

iteration

list

remove-if

listiterator

c++11