редактировать: я специально сравниваюstd::vector«sлинейный поисковые операции наstd::map двоичный поисковые операции, потому что это то, к чему, по-видимому, относится требование Херба. Я знаю, что использование бинарного поиска переместит производительность с O (N) на O (log N), но это не будет проверкой утверждения Херба

Бьярн Страуструп и Херб Саттер оба недавно говорили о том, как здоровоstd::vector в ситуациях, которые можно было бы ожидатьstd::list использовать из-за затрат на кеш при обходе связанного списка. (увидетьhttp://channel9.msdn.com/Events/Build/2014/2-661 на отметке 48 минут)

Херб сделал дальнейшее заявление, однако, что операции над упорядоченным вектором были даже быстрее, чемstd::map, (увидетьhttp://i.imgur.com/zX07TZR.png взято из отметки 51:30 вышеупомянутого видео на 9 канале), которое мне было трудно понять. Поэтому я создал небольшой тест, чтобы продемонстрировать это, и мне было трудно воспроизвести эти результаты: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);
  }
}

// output:
// testing vector...99.189ms
// testing deque...120.848ms
// testing set...4.077ms

Обратите внимание, какstd::vector выполняет на порядок медленнее, чемstd::set , Конечно, это результат, которого я ожидал, но я смущен заявлением, которое Херб пытался сделать.

Что я делаю неправильно? Или я неправильно понимаю утверждение Херба?

Примечания к моему тестовому приложению:

он должен использовать линейные операции - весь смысл упражнения в том, чтобы продемонстрировать магию кеша процессора, это ограничения, которые Херб и Бьярне накладывают на упражнениеЯ не пытался распутать петли для своей векторной итерации, но я считаю, что итерация не сильно влияет на производительностьЯ ограничил цикл до 10 тыс. Элементов, потому что время ожидания идеально подходит для больших наборов, но увеличение размера не меняет результатов

редактировать: см.https://ideone.com/916fVd для измененного примера, который сравнивает только производительность поисков. Линейный поиск демонстрирует ту же производительность.