使用 list::size() 后运行时间显着增加

Question

我的代码量很大。我最近添加了一些新代码，在我添加一个新的简单 if 语句之前它工作正常。添加此添加语句后，运行时间增加了 100 倍，这是无稽之谈。

下面是我的部分代码。在 terminate_ongoing 函数中添加了 if 语句，即使我删除了 if 语句中的所有内容，程序仍然很慢。但是如果我评论这个 if 语句，它又变快了。

if 语句是

if ( emitted_vulnerable_list.size() > 100000 ){
}

如您所见，我把if里面的都去掉了，但是问题并没有解决。能否请您提供一些提示来找到问题的根源并解决问题。

class flip_flop_vulnerable_time{
public:
   list <vulnerable_time> emitted_vulnerable_list;
   list <vulnerable_time> ongoing_vulnerable_list;


   void terminate_ongoing(int PO, int minimum_delay , int cycle, long long elimination_time){
     for (list<vulnerable_time>::iterator it=ongoing_vulnerable_list.begin(); it!=ongoing_vulnerable_list.end(); it++){
       if ( it-> PO_signal_number == PO && it->cycles_passed == cycle && it->min_delay == minimum_delay ){
         it-> elimination_time = elimination_time;
         if ( cycle == 0 && elimination_time - it->appearance_time < 500 )
           ongoing_vulnerable_list.erase(it);
         else{
           emitted_vulnerable_list.splice(emitted_vulnerable_list.end(),ongoing_vulnerable_list, it);
           if ( emitted_vulnerable_list.size() > 100000 ){
           }
         }
         return;
       }
     }
     cout<<"\tError: can't find the following ongoing vulnerable_time object"<<endl;
     exit(0);
   }

   // Some other functions here
};

Answer 1

gcc 中的 list::size() 实现复杂度为 O(n)，在巨大的列表中，多次调用此函数可能会非常耗时。

Answer 2

list::size() 的问题在于您使用的是 list::splice()，除非计算移动的项目，否则无法跟踪列表大小。但是使用两个变量手动跟踪尺寸看起来并不难。

使用 list::size() 后运行时间显着增加

Significant runtime increase after employing list::size()

c++

list