Ответ 1
Я нашел слайды для упрощения ссылки (я не вижу графиков, но я предполагаю, что это может быть из-за запатентованного формата файла), Соответствующим слайдом является номер 39, который описывает проблему, которая решается:
§ Генерировать N случайных целых чисел и вставлять их в последовательность, чтобы каждый был вставлен в свое правильное положение в числовом порядке.
§ Удалите элементы по одному, выбирая случайную позицию в последовательности и удаляя там элемент.
Теперь, должно быть довольно очевидно, что связанный список не является хорошим выбором для этой проблемы. Несмотря на то, что список намного лучше, чем вектор для вставки/удаления в начале или в середине, это не очень удобно для вставки/удаления в случайной позиции из-за необходимости линейного поиска. И линейный поиск намного быстрее с векторами из-за лучшей эффективности кеширования.
Саттер предлагает, чтобы карта (или дерево вообще) казалось естественным выбором для этого алгоритма, потому что вы получаете поиск O (log n). И действительно, он довольно легко разбивает вектор для больших значений N в части вставки.
Здесь идет, но. Вам нужно удалить n-й элемент (для случайного n). Вот где я считаю, что ваш код обманывает. Вы удаляете элементы в том порядке, в котором они были вставлены, эффективно используя вектор ввода в качестве справочной таблицы для поиска значения элемента в "случайной" позиции, чтобы вы могли искать его в O (log n). Таким образом, вы действительно используете комбинацию set и vector для решения проблемы.
Обычное двоичное дерево поиска, например, используемое для std::map или std::set (которое, как я полагаю, использует Sutter), не имеет быстрого алгоритма для нахождения n-го элемента. Здесь один, который, как утверждается, является O (log n) в среднем и O (n) в худшем случае. Но std::map и std::set не предоставляют доступ к базовой структуре дерева, поэтому для тех, с которыми вы застряли в обходном порядке (исправьте меня, если я ошибаюсь), который является линейным поиском снова! Я действительно удивлен, что версия карты является конкурентоспособной с векторной в результатах Sutter.
Для сложности log (n) вам нужна структура, такая как Заказать дерево статистики, которая, к сожалению, не предоставляется стандартной библиотекой. Там GNU на основе политик STL MAP, как показано здесь.
Вот быстрый тестовый код, который я сделал для вектора vs set vs ost (vs vector с бинарным поиском для хорошей оценки) https://ideone.com/DoqL4H Набор намного медленнее, тогда как другая структура на основе дерева быстрее, чем вектор, что не соответствует результатам Sutter.
order statistics tree: 15.958ms
vector binary search: 99.661ms
vector linear search: 282.032ms
set: 2004.04ms
(N = 20000, разница только будет больше в пользу ost с большими значениями)
Короче говоря, я пришел к такому же выводу, что исходные результаты Саттера кажутся странными, но по несколько иной причине. Мне кажется, что лучшая асимптотическая сложность на этот раз выигрывает на более низких постоянных множителях.
Обратите внимание, что описание проблемы не исключает возможности дублирования случайных значений, поэтому использование map/set вместо multimap/multiset немного изменяет предпочтение карты/набора, но я предполагаю, что иметь только небольшое значение когда область значений намного больше, чем N. Кроме того, предварительное резервирование вектора существенно не улучшает производительность (около 1% при N = 20000).