Подходит ли C++ для структур данных и алгоритмов?
C++ чаще всего выбирают для спортивного программирования, и для собеседований он тоже сильный выбор: быстрый, со стандартной библиотекой, которая покрывает почти любую нужную структуру. Цена за это: больше кода и больше способов ошибиться, от висячих указателей до инвалидированных итераторов. Если сначала написать структуры самому, как на этом пути, всё это перестаёт быть сюрпризом.
Какие контейнеры STL каким структурам данных соответствуют?
std::vector реализует динамический массив, std::stack и std::queue по умолчанию являются адаптерами над std::deque, std::list устроен как двусвязный список, std::unordered_map и std::unordered_set построены на хеш-таблицах, std::priority_queue реализует двоичную кучу (по умолчанию max-кучу, в отличие от Python и Java), а std::map и std::set устроены как сбалансированные двоичные деревья поиска, на практике красно-чёрные. Контейнера для префиксного дерева или графа нет: их вы пишете сами.
Писать структуры данных самому или просто пользоваться STL?
И то и другое, именно в таком порядке. Реализуйте каждую структуру один раз, чтобы понимать, почему поиск в std::unordered_map в среднем занимает константное время и почему std::map хранит ключи отсортированными, а после этого везде пользуйтесь STL. На соревновании или собеседовании никто не ждёт написанного вручную красно-чёрного дерева; от вас ждут, что вы выберете правильный контейнер и будете знать его стоимость.
C++ или Python для DSA?
C++, если вы собираетесь заниматься спортивным программированием или проходить собеседования там, где его ждут; Python, если вам нужен кратчайший путь от идеи до работающего кода. Алгоритмы одинаковые, поэтому многие учатся на одном языке, а соревнуются на другом. Каждый курс по структурам данных на этом пути преподаётся на обоих.
Какие курсы этого пути не преподаются на C++?
Два: динамическое программирование и серия по интервью на Python, оба преподаются на Python. Они перечислены после шагов со ссылкой, которая открывает их на Python. Идеи переносятся без изменений: в C++ таблица мемоизации становится std::vector или std::unordered_map.
Нужно ли знать C++, прежде чем начинать этот путь?
Как минимум классы, указатели, ссылки и std::vector. Если это для вас новое, курс C++ от Coddy сначала бесплатно разберёт эти темы, а этот путь начинается там, где он заканчивается.
