Используя вектор или массив?

Question

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

vector<string> vec;
string str[20];

Какая из следующих операций подкачки будет быстрее или они эквивалентны?

vector[i].swap(vector[j]);
str[i].swap(str[j]);

Answer 1

Они эквивалентны.На самом деле, они не только эквивалентны, они идентичны , потому что в каждом случае вы вызываете одну и ту же функцию:

basic_string::swap()

Но, по большому вопросувы используете массив или вы должны использовать vector.Как общее практическое правило, которое, я думаю, мне было бы трудно найти множество законных исключений - вы всегда должны использовать vector по умолчанию в C ++, если у вас нет особых причин не делать этого.Скорость не будет одной из этих причин, за исключением исключительно редких обстоятельств.

Answer 2

Операция подкачки должна быть более или менее одинаковой скорости, возможно Массив пренебрежимо быстрее, но не сама операция свопинга, а способ доступа к элементам через vector.

Вероятно, вам следует искать здесь критерии, не связанные с производительностью.

Answer 3

Доступ к элементам в массиве будет иметь немного лучшую локальность, потому что при доступе к элементу в массиве вы будете применять смещение к адресу первого элемента. При доступе к элементу в векторе вы будете применять два смещения - одно для получения указателя на массив, сохраненный в векторном классе, а затем другое смещение для получения элемента в этом массиве. Но это совсем не важно, и компилятор может (или даже должен) оптимизировать это по-другому.

Что теоретически может замедлить вас - это сравнение строк и доступ к содержимому этих строк. Видите ли, std::string распределяет свои данные в куче, и если вам не повезет, данные каждой строки будут указывать на области памяти слишком далеко друг от друга. Учитывая, что содержимое строк не может поместиться в кэш-памяти L1 и случайных местах памяти, средство предварительной выборки не сможет сделать данные доступными для вашего кода, а ЦП просто застревает в ожидании шины памяти.

Я бы начал с более высокого уровня оптимизации. Сначала запустите профилировщик, чтобы увидеть, что именно является узким местом в вашей программе. Если это окажется сортировкой, я посмотрю, смогу ли я использовать другие алгоритмы сортировки (то есть частичную сортировку вместо полной сортировки). Затем попробуйте оптимизировать доступ к памяти. И только потом подумайте, стоит ли мне использовать std :: vector или нет. То, что вы делаете здесь, я думаю, является преждевременной оптимизацией, которая не годится.