Связный список — классическая структура данных, которая позволяет быстрые вставки/удаления, но при этом просаживает другие операции (случайный доступ к элементу). Мы пройдёмся от базовой реализации до других возможных вариаций этой структуры данных и, надеюсь, вместе узнаем что‑то новое. Краем глаза увидим возможные применения связных списков. И в конце, для любителей C++, бонус: использование связного списка для сбора диагностики выделений динамической памяти в вашем коде.

Когда-то я писал пост про различные интересные структуры данных. Среди них был т.н. sparse set. Там мы описали его в общих чертах, опустив некоторые детали (которыми позже статья была дополнена). Но кроме sparse set существуют и другие разреженные структуры данных! На них сегодня и посмотрим : )

Лавка — сервис быстрой доставки продуктов. Один из важнейших сценариев использования сервиса для покупателя — это поиск. Примерно 30% товаров добавляются в корзину именно из его результатов. А ещё, если в пользовательской сессии был успешный запрос в поиск, вероятность совершения заказа вырастает на 10–15%. То есть, если клиенту нужен конкретный продукт и он его быстро находит через поиск, вероятность совершения заказа становится выше.

Корректная и качественная организация поиска — нетривиальная задача, поэтому иногда приходится придумывать нестандартные решения, чтобы всё работало как нужно. В этой статье я расскажу историю развития поиска в Лавке от самого начала до текущего момента. Нам пришлось объединить всю силу и мощь целых трёх движков, чтобы пользователи получали точный и актуальный результат. Параллельно погрузимся в различные технические детали, проблемы и прочие нюансы.

О чём тут не будет: напоминания базовых конструкций языка и основных моментов о том, как с ними работать; подробного разбора, как работают исключения (писали тут и тут); как грамотно спроектировать ваш класс/программу, чтобы не наломать дров в будущем с гарантией исключений (разве что совсем чуть-чуть, хотя я сам и не очень-то тук-тук).

О чём будет: разные способы обработки ошибок в C++, несколько советов от сообщества и немного заметок о различных жизненных (и не очень) ситуациях.

В процессе изучения разных алгоритмов и структур данных приходит понимание, что не все они применимы в прикладных задачах (в отличие от задач про Васю и Петю/Алису и Боба). Но тот факт, что алгоритм/структура данных не является полезной на практике не означает, что идеи в них содержащиеся не привлекают пытливые умы даже из чистого любопытства. Потому речь пойдёт о красивых (субъективно) и, что важно, простых с точки зрения концепции структурах данных. 

Помните: если что-то не компилируется, это псевдокод. 

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

Находясь в поисках какой-то агрегированной информации о стандартных приёмах, используемых при проектировании кастомных аллокаторов, я обнаружил, что существует достаточное количество статей о том, как аллокаторы работают в C++, каких-то базовых вариантах или наоборот очень специфических версиях, но ничего достаточно общего. Попался только замечательный доклад замечательного Андрея Александреску про неправильную архитектуру std::allocator и собственно базовые концепции построения своего нового самого крутого в мире аллокатора. Эта статья является довольно вольным переводом второй части его выступления с моими небольшими дополнениями. Конечно же, категорически рекомендую посмотреть оригинальный доклад, но, если вы любитель текстовых версий, прошу под кат.