Что нужно учитывать, используя std::vector?
Основные плюсы и минусы происходят от линейного расположения элементов в памяти и ограничений, которые это расположение накладывает. std::vector имеет:
[+] Доступ к произвольному элементу за
O(1).[-] Проблема: При превышении capacity - долгая вставка нового элемента (даже в конец), тербующая поэлементного копирования.
Решение: С этим можно побороться, если зарезервировать заранее всю нужную память под все элементы, но мы редко знаем каким будет максимальное количество элементов. И памяти на все процессы так не напасёшься, даже учитывая оптимизацию современных ОС: когда ОС физически выделяет память только когда процесс начинает её использовать.Хороший cache coherence:
[+] В общем случае это означает более быстрый обход контейнера
vectorпо сравнению с контейнерами а-ляlist(map,set,forward_listetc.).[-] Проблема: В частности, нужно разбиратсья с cache sharing.
Еслиvectorпараллельно обходят два потока и каждый из них модифицирует его содержимое, то вероятно кэши этих потоков будет смотеть на смежную область памятиvector-а. Тогда каждая из записей будет инвалидировать содержимое кеша ядра другого потока, тем самым приводя к регулярному refetch-у. В некоторых корнер кейсах заменаvectorнаlistможет внезапно привести к улучшению перфоманса.
Решение: Лечится такая проблема обычно увеличением размера элемента до размера кэшлайна. Либо же выдачей каждому потоку поNэлементов, где(N * sizeof(ElementT)) == cacheline size.
