t
Я правильно понимаю, что при сортировке вектора или дэка элементы в памяти никуда не сдвигаются, а только меняются ссылки между ними? Т.е. грубо говоря сортировка строк займет то же время, что и сортировка указателей на строки?
Size: a a a
2020 July 22
AS
Я правильно понимаю, что при сортировке вектора или дэка элементы в памяти никуда не сдвигаются, а только меняются ссылки между ними? Т.е. грубо говоря сортировка строк займет то же время, что и сортировка указателей на строки?
неправильно понимаешь, именно объекты перемещаются при сортировке вектора и деки
t
неправильно понимаешь, именно объекты перемещаются при сортировке вектора и деки
Т.е., чтобы ускорить процесс нужно перегнать коллекцию в коллекцию указателей и их уже отсортировать, т.к. указатели весят меньше чем сами объекты?
AS
Т.е., чтобы ускорить процесс нужно перегнать коллекцию в коллекцию указателей и их уже отсортировать, т.к. указатели весят меньше чем сами объекты?
откуда такие выводы?
AS
цепочка должна быть такой: для решения задачи вектор должен быть отсортирован, сортирую.
AS
и никаких других вопросов пока не должно возникать
AS
а вот когда к вам придут и скажут, что сортировка жутко тормозит, вот тогда вы возьмете профилировщик и найдете хотпоинты и будете думать как это оптимизировать
t
откуда такие выводы?
Если элементы перемещаются в памяти, то затраты на копирование тяжелых элементов будут больше чем на копирование легких указателей
AS
Если элементы перемещаются в памяти, то затраты на копирование тяжелых элементов будут больше чем на копирование легких указателей
почему копирование а не обмен?
AS
если объект поддерживает обмен состоянием (swap), то это очень эффективно
t
почему копирование а не обмен?
именно объекты перемещаются при сортировке вектора и декиПереместить значит удалить со старого места и вставить на новое. Иначе менялись бы просто ссылки на объекты во внутренней структуре вектора
AS
именно объекты перемещаются при сортировке вектора и декиПереместить значит удалить со старого места и вставить на новое. Иначе менялись бы просто ссылки на объекты во внутренней структуре вектора
так, мне кажется я сказал все.
AS
у объекта есть состояние, если в классе объекта поддерживается обмен состоянием, то это очень эффективно и безопасно по отношению к исключениям:
struct myobject {
std::string state;
void swap(myobject& other) {
std::swap(state, other.state);
}
};t
у объекта есть состояние, если в классе объекта поддерживается обмен состоянием, то это очень эффективно и безопасно по отношению к исключениям:
struct myobject {
std::string state;
void swap(myobject& other) {
std::swap(state, other.state);
}
};Ок. Тогда перепишу сортировку указателей на сортировку самого объекта
ПК
именно объекты перемещаются при сортировке вектора и декиПереместить значит удалить со старого места и вставить на новое. Иначе менялись бы просто ссылки на объекты во внутренней структуре вектора
перемещение строк > ~15 символов дешевле копирования в несколько раз
ПК
сравнимо с копированием указателя вернее
t
перемещение строк > ~15 символов дешевле копирования в несколько раз
Строки для примера взяты. Там тяжелые структуры будут
ПК
Строки для примера взяты. Там тяжелые структуры будут
Главное чтобы они поддерживали move семантику, тогда проблем быть не должно.
TS
а сортировка данных по указателям повлечет за собой кэшмиссы, имхо