Всеобъемлющий векторный и связанный контрольный список для рандомизированных вставок/удалений

Итак, я знаю об этом вопросе и других на SO, которые касаются проблемы, но большинство из них имеют дело со сложностями структур данных (просто скопирую сюда, связано это теоретически имеет O (

Я понимаю, что сложность, по-видимому, указывает на то, что список был бы лучше, но меня больше волнует реальная производительность.

Примечание:Этот вопрос был навеян слайдами 45 и 46 из Презентация Бьярна Страуструпа на Going Native 2012, где он говорит о том, что кэширование процессора и локальность ссылок действительно помогают с векторами, но совсем не (или недостаточно) со списками

Вопрос:Есть ли хороший способ проверить это, используя процессорное время, а не время стены, и получить приличный способ «случайной» вставки и удаления элементов, которые можно сделать заранее, чтобы это не влияло на тайминги?

В качестве бонуса было бы неплохо иметь возможность применить это к двум произвольным структурам данных (скажем, к векторным и хеш-картам или к чему-то вроде t шляпу), чтобы найти «реальную производительность» на некотором оборудовании.