相关疑难解决方法(0)

编辑:我特别比较std::vector的线性搜索操作的std::map 二进制搜索行动,因为这是香草的要求似乎涉及到.我知道使用二进制搜索会将性能从O(N)移到O(log N),但这不会测试Herb的声明

Bjarne Stroustrup和Herb Sutter最近都谈到了std::vector在人们期望std::list使用的情况下有多棒,这是由于链表遍历期间缓存未命中的代价.(见48分钟后http://channel9.msdn.com/Events/Build/2014/2-661)

Herb做了进一步的声明,然而对有序矢量的操作甚至更快std::map(参见http://i.imgur.com/zX07TZR.png取自上述channel9视频的51:30标记),我发现很难捉摸.所以我创建了一个小测试来证明这一点并且很难再现这些结果:https://ideone.com/MN7DYK

这是测试代码:

template <typename C>
void test(std::string name, std::vector<int> shuffledInputValues, C & c)
{
   // fill container 'c' with values from 'shuffledInputValues' then erase them all
   {
      std::cout << "testing " << name << "..." << std::endl;
      timer t;

      for (auto val : shuffledInputValues) insert(c, val);
      for (auto val : shuffledInputValues) remove(c, val);
  }
} …