C++ geek

🔧 Что делать, если std::sort тормозит?

Привет! Сегодня хочу поделиться с вами одной типичной ситуацией, с которой сталкивался не раз — сортировка больших контейнеров через std::sort, которая неожиданно начинает тормозить. Вызываешь вроде обычную сортировку, а работает медленно. Почему так?

🔍 Проблема — не std::sort, а компаратор!

В 90% случаев проблема не в std::sort, а в лямбде или компараторе, который вы передаёте. Особенно если он:

1. Вызывает копирование: вы сравниваете по значениям, а не по ссылке.
2. Делает что-то тяжёлое внутри: например, вызывает метод, делает std::string копию, обращается к БД (да, и такое видел!).
3. Некеширует результат: например, каждый раз считает длину строки.

✅ Как ускорить сортировку:
- Передавайте данные по ссылке, особенно если у вас вектор структур:

  std::sort(vec.begin(), vec.end(), [](const MyStruct& a, const MyStruct& b) {
      return a.key < b.key;
  });
  

- Если у вас есть вычисление ключа — используйте схему "decorate-sort-undecorate":

  std::vector<std::pair<int, size_t>> temp;
  for (size_t i = 0; i < vec.size(); ++i)
      temp.emplace_back(compute_key(vec[i]), i);

  std::sort(temp.begin(), temp.end());
  std::vector<MyStruct> result;
  for (const auto& [_, i] : temp)
      result.push_back(vec[i]);
  

🧠 Мораль: Если std::sort "медленный", не спешите винить алгоритм. Лучше проверьте, что вы передаёте ему на вход.

➡️ @cpp_geek

www.tg-me.com/no/telegram/com.cpp_geek/302

1.4K viewsApr 11 at 09:12

🔧 Что делать, если std::sort тормозит?

Привет! Сегодня хочу поделиться с вами одной типичной ситуацией, с которой сталкивался не раз — сортировка больших контейнеров через std::sort, которая неожиданно начинает тормозить. Вызываешь вроде обычную сортировку, а работает медленно. Почему так?

🔍 Проблема — не std::sort, а компаратор!

В 90% случаев проблема не в std::sort, а в лямбде или компараторе, который вы передаёте. Особенно если он:

1. Вызывает копирование: вы сравниваете по значениям, а не по ссылке.
2. Делает что-то тяжёлое внутри: например, вызывает метод, делает std::string копию, обращается к БД (да, и такое видел!).
3. Некеширует результат: например, каждый раз считает длину строки.

✅ Как ускорить сортировку:
- Передавайте данные по ссылке, особенно если у вас вектор структур:

  std::sort(vec.begin(), vec.end(), [](const MyStruct& a, const MyStruct& b) {
      return a.key < b.key;
  });
  

  std::vector<std::pair<int, size_t>> temp;
  for (size_t i = 0; i < vec.size(); ++i)
      temp.emplace_back(compute_key(vec[i]), i);

  std::sort(temp.begin(), temp.end());
  std::vector<MyStruct> result;
  for (const auto& [_, i] : temp)
      result.push_back(vec[i]);
  

BY C++ geek