c++ - 为什么这段代码运行这么慢？

Question

我被这段代码严重难住了，我运行了 gprof 并发现该程序在 contains() 函数中花费了 40% 的时间，该函数运行了大约 8000 次。该程序本身总共需要 15 秒才能运行。有谁知道为什么需要这么长时间，或者它可能是什么？

// Check a list to see if it contains a tile object at x,y
bool contains(std::list<struct Tile>* list, int x, int y){
  std::list<struct Tile>::iterator it;
  for(it = list->begin(); it != list->end(); it++){
    if((*it).x == x && (*it).y == y){
      return true;
    }
  }
  return false;
}

Answer 1

使用std::vector ，它的遍历速度快了大约 100 倍，因为它是缓存友好的。 vector push_back 具有 O(1) 摊销难度，就像列表一样。无论如何， vector 对于中间插入是不利的。 还有 std::map和 std::unordered_map专为快速搜索而设计。