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

Вернее, не так.

Решение было стандартным: тот же линейный проход с заменой указателей в каждом узле, как и писали сотни тысяч людей до него. Ничего необычного или сложного, но при взгляде на него у меня возникло два вопроса:

• Почему по умолчанию все решают задачу именно так?
• Можно ли сделать лучше?

В данной статье хочу поднять несколько холиварную тему — тему безлоковых алгоритмов, а в частности реализации безлокового стека. Точнее, стек этот условно безлоковый, почему — будет ясно далее. Хочу сразу предупредить, что все примеры будут даны на языке C.

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

Хабр, это снова я, Алексей Рак (фото не мое). В прошлом году, помимо основной работы, мне довелось стать одним из авторов задач для кандидатов в Яндекс. Сегодня наша команда впервые за долгое время публикует на Хабре реальные задачи для разработчиков, которые устраиваются в компанию. Эти задачи использовались до февраля 2020 года при отборе на стажировку для бэкендеров. Решения проверял компьютер. Сейчас кандидатам достаются похожие задания.

Разборы и код сознательно спрятаны в спойлеры. Если вы готовитесь к собеседованиям в большие IT-компании, попробуйте решить одну или несколько задач, прежде чем смотреть разбор. Отправить решение для проверки можно на Codeforces — ответ придёт сразу же (ссылка на Codeforces и примечание). Код представлен на Python, C++ и Java. Важно: авторский «олимпиадный» код не предназначен для продакшена, он написан исходя из того, что система будет проверять его автоматически.

От переводчика

В мире победили языки высокого уровня и в мирах руби-питон-js разработчиков остается только разглагольствовать, что в плюсах не стоит использовать то или иное. Например, исключения, потому что они медленные и генерируют много лишнего кода. Стоило спросить "и какой же код он генерирует", как в ответ получил мямленье и мычание. А и правда — как же они работают? Ну что ж, компилируем в g++ с флагом -S, смотрим что получилось. Поверхностно разобраться не сложно, однако то, что остались недопонимания — не давали мне спать. К счастью, готовая статья нашлась.

На хабре есть несколько статей, подробных и не очень (при этом все равно хороших), посвященных тому, как работают exceptions в C++. Однако нет ни одной по-настоящему глубокой, поэтому я решил восполнить этот пробел, благо есть подходящий материал. Кому интересно как работают исключения в C++ на примере gcc — запаситесь pocket-ом или evernote, свободным временем и добро пожаловать под кат.

Автор материала, перевод которого мы сегодня публикуем, говорит, что C++, в его современном виде, если сравнивать его с тем, чем был этот язык несколько лет назад, значительно изменился в лучшую сторону. Конечно, эти изменения произошли далеко не сразу. Например, в былые времена C++ не хватало динамичности. Непросто было найти человека, который мог бы сказать, что он питает к этому языку нежные чувства. Всё изменилось тогда, когда те, кто отвечает за стандартизацию языка, решили дать ход новшествам. В 2011 году C++ стал динамическим языком, языком, который постоянно развивается и вызывает у программистов куда больше положительных эмоций.

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



Сегодня мы поговорим о некоторых новых возможностях языка (начиная с C++ 11, которому, кстати, уже 8 лет), знать о которых будет полезно любому программисту.

Привет, Хабр! Представляю вашему вниманию перевод статьи "Instructor’s Guide for Programming" автора Бьярне Страуструпа (дата последнего посещения: 20.12.2017).

От переводчика

Бьярн Страуструп известен как разработчик языка программирования C++. Книги его авторства лежат на столах многих маститых разработчиков.

Особенно стоит отметить учебник по основам программирования "Программирование: Принципы и практика с использованием C++". Бьярн написал его для студентов Техасского университета агрокультуры и машиностроения, в котором он долгое время преподавал курс для студентов. В дополнение к самому учебнику, на сайте www.stroustrup.com можно найти Руководство инструктора. Изложенный в нем опыт преподавания курса основ программирования может быть полезен не только для курса по C++. В руководстве можно найти ответы на типичные вопросы преподавателей: Как подавать материал? Как бороться с расслоением группы по навыкам? Насколько глубоко нужно погружаться в тему?

Мне не удалось найти русской версии Руководства инструктора к книге "Программирование: Принципы и практика с использованием C++", поэтому я решил перевести его и опубликовать.

Здравствуйте, уважаемые посетители Хабра!

В этой статье речь пойдёт о связном списке, многопоточности и С++. Сразу отмечу, что были все шансы положить эту работу «на полочку» и использовать в небольшом количестве личных проектов. Вместо этого я всё-таки решил выложить её на суд общественности – вдруг это действительно покажется кому-нибудь полезным или интересным. Более того, если окажется, что кто-нибудь когда-нибудь уже успел сделать что-нибудь подобное, укажите мне эти материалы, пожалуйста. Однако сколько я ни пытался гуглить на эту тему, все попытки были безуспешны.

Также отмечу, что речь пойдёт не о классическом связном списке, а о моём творческом переосмыслении использования этой структуры данных в многопоточном окружении. Я рассматривал сценарий неупорядоченного интенсивного многопоточного обращения к списку. Это означает, что любой поток в любой момент независимо от других может получить доступ к списку и произвести требуемые операции. Если он только добавляет или изменяет элементы, это ещё полбеды. Если же он ещё и удаляет элементы, могут возникнуть различные интересные особенности.

Этот проект, которым я занимался на правах хобби и саморазвития, по ряду причин растянулся на весьма длительный срок. Кроме того, по мере работы над ним я интенсивно учился: проект начинался без знания и понимания STL и проектировался соответственно, используя только внутренние средства собственно языка С++. Однако потом я весьма серьёзно его модифицировал с учётом STL и даже под STL. Что у меня из этого получилось, судить вам, уважаемые читатели.

Написал Стивен Тови в 2:29 утра по программированию (шутка юмора Google Translate)
Вступление от себя: эта заметка, прорекламированная Алёной C++, предназначена в основном разработчикам игр для консолей, но будет, наверное, полезна и всем, кому приходится сталкиваться с экстремальным аллоцированием динамической памяти. Возможно, любители посравнивать управление памятью в C++ и Java тоже найдут над чем задуматься.

Оригинал с небезынтересной дискуссией в комментариях: altdevblogaday.org/2011/02/12/alternatives-to-malloc-and-new

Обязательная вступительная басня

Мне очень нравятся суши. Это вкусно и удобно. Мне нравится, что можно с бухты-барахты, не тратя целый обеденный час, зайти в суши-ресторан с конвейером, занять место и взять что-то свежее и вкусное с ленты. Но при всём при этом, чего мне реально не хотелось бы, так это быть официантом в суши-ресторане, особенно если бы моей обязанностью было бы рассаживать посетителей по местам.

Всем привет! Думаю, у многих сразу возник другой вопрос — а зачем вообще нужна ещё одна статья про LLVM, ведь на хабре их и так больше сотни? Моей задачей было написать "введение в тему" for the rest of us — профессиональных разработчиков, не планирующих создавать компиляторы и совершенно не интересующихся особенностями устройства LLVM IR. Насколько я знаю, подобного ещё не было.

Главное, что интересует практически всех — и о чём я планирую рассказать — вынесено в заголовок статьи. Зачем нужен LLVM, когда есть GCC и Visual C++? А если вы не программируете на C++, вам стоит беспокоиться? И вообще, LLVM это Clang? Или нет? И что эти четыре буквы на самом деле означают?

Часть 1. Вступление
Часть 2. Заголовочные файлы
Часть 3. Область видимости
Часть 4. Классы
Часть 5. Функции
Часть 6. Специфика Google
Часть 7. Ещё возможности C++
Часть 8. Именование
Часть 9. Комментарии
Часть 10. Форматирование
Часть 11. Исключения из правил

---

Изменения 2019-2024


Все мы при написании кода пользуемся правилами оформления кода. Иногда изобретаются свои правила, в других случаях используются готовые стайлгайды. Хотя все C++ программисты читают на английском легче, чем на родном, приятнее иметь руководство на последнем.
Эта статья является переводом части руководства Google по стилю в C++ на русский язык.
Исходная статья (fork на github), обновляемый перевод.
Это вступительная часть руководства, в которой рассматриваются общие вопросы «Зачем?»
Также после перевода будет несколько ответов на возможные вопросы.

Добрый день, дорогой читатель!

Эта статья — первая в цикле статей-конспектов, которые я буду писать по ходу прочтения книги Скотта Мейерса "Эффективный и современный c++". Каждой из таких статей будет соответствовать отдельная директория в специально заведенном на github.com проекте с примерами использования описываемых возможностей и приемов.

Часть 1. Вступление
…
Часть 9. Комментарии
Часть 10. Форматирование
Часть 11. Исключения из правил


Эта статья является переводом части руководства Google по стилю в C++ на русский язык.
Исходная статья (fork на github), обновляемый перевод.

Здравствуйте!

Те, кто занимается программированием рано или поздно сталкивается с необходимостью прохождения технического собеседования у потенциального работодателя.

О том, что спрашивают на собеседовании у C++ программистов, а также об ответах на эти вопросы и пойдет речь в данном посте.

В сети огромное количество площадок формата Q&A где задаются вопросы из разряда:

• Предложите С++ логер? (C++ logging framework suggestions)
• Какой наиболее эффективный потоко-безопасный С++ логер? (What is the most efficient thread-safe C++ logger)
• Библиотека логирования для игр (Logging library for c games)
• Асинхронный потоко-безопасный С++ логер? (Asynchronous thread-safe logging in C++)

Люди делятся своим опытом и знаниями, но формат таких площадок позволяет лишь показать личные предпочтения отвечающего. К примеру, одним из самых производительных логеров чаще всего называют Pantheios, который даже по тестам производителя тратит больше 100 секунд на запись 1M строк лога, на современном железе это около 30 секунд, быстро ли это?

В этой статье я сравню наиболее известные и заслуженные логеры последних лет и несколько относительно молодых логеров по более чем 25 критериям.

Если вы знаете, что такое ICU, то, вероятно, вы не узнаете из этого поста ничего нового.

    Порой приходится слышать от товарищей, что на собеседовании их просили написать код, который бы обращал строку. И даже в Cracking the Coding Interview это второй вопрос в тестах. Однако, правильное, с моей точки зрения, решение выходит далеко за рамки библиотечного вызова или одного цикла while.

В этой главе сказа про дружбу C++ и Python будет на удивление мало использования Boost.Python. Передача исключений туда и обратно является по сути слабым местом данной библиотеки. Будем обходиться родным API языка Python, а где это возможно использовать Boost.Python.
Тем не менее Boost.Python создаёт окружение, в котором исключения из C++ попадают в Python в виде стандартного RuntimeError, а обратно из Python генерируется исключение C++ типа error_already_set, что означает «тебе что-то прилетело, сходи сам почитай что там». И вот здесь нам как раз будет не лишним использовать C-API языка Python, чтобы вычитать необходимую информацию об исключении и преобразовать в соответствующий класс сообразно логике приложения.
К чему такие сложности? — Дело в том, что в Python, в отличие от C++, кроме текста исключения и его типа приходит ещё и traceback — стек до места возникновения исключения. Давайте немного расширим стандартный std::exception дополнительным параметром для этого stacktrace, а заодно напишем конвертер исключений туда и обратно из классов C++ в классы исключений Python.

Данная статья не является продолжением повествования об обёртках C++ API. Никаких обёрток сегодня не будет. Хотя по логике это третья часть данного повествования.
Сегодня будет море крови, расчленение существующих типов и магическое превращение их в привычные аналоги в другом языке.
Речь не пойдёт о существующей конвертации между строками, нет, мы напишем свои конвертеры.
Мы превратим привычный datetime.datetime питона в boost::posix_time::ptime библиотеки Boost и обратно, да чёрт с ним, мы вообще всю библиотеку datetime превратим в бустовые типы! А чтобы не было скучно, принесём в жертву встроенный класс массива байт Python 3.x, для него как раз ещё нет конвертера в Boost.Python, а потом зверски используем конвертацию массива байт в новом конвертере питоновского uuid.UUID в boost::uuids::uuid. Да, конвертер можно использовать в конвертере!
Жаждешь крови, Колизей?!..

Данная статья является продолжением первой части.
Продолжаем мучить Boost.Python. В этот раз настала очередь класса, который нельзя ни создать, ни скопировать.
Обернём почти обычную сишную структуру с необычным конструктором.
И поработаем с возвращением ссылки на поле объекта C++, так чтобы сборщик мусора Python его не удалил ненароком. Ну и наоборот, сделаем альтернативный вариант, чтобы Python прибрал мусор после удаления того, что ему отдали на хранение.
Поехали…

Boost.Python во всех отношениях замечательная библиотека, выполняющая своё предназначение на 5+, хотите ли вы сделать модуль на С++ для Python либо хотите построить скриптовую обвязку на Python для нативного приложения написанного на С++.
Самое сложное в Boost.Python — это обилие тонкостей, поскольку и C++ и Python — два языка изобилующие возможностями, и потому на стыке их приходится учитывать все нюансы: передать объект по ссылке или по значению, отдать в Python копию объекта или существующий класс, преобразовать во внутренний тип Python или в обёртку написанного на C++, как передать конструктор объекта, перегрузить операторы, навесить несуществующие в C++, но нужные в Python методы.
Не обещаю, что в своих примерах опишу все тонкости взаимодействия этих фундаментальных языков, но постараюсь сразу охватить как можно больше частоиспользуемых примеров, чтобы вы не лазили за каждой мелочью в документацию, а увидели все необходимые основы здесь, или хотя бы получили о них базовое представление.

Хабра, привет!

Не так давно у со мной произошел довольно-таки интересный инцидент, в котором был замешан один из преподавателей одного колледжа информатики.

Разговор о программировании под Linux медленно перешел к тому, что этот человек стал утверждать, что сложность системного программирования на самом деле сильно преувеличена. Что язык Си прост как спичка, собственно как и ядро Linux (с его слов).

У меня был с собой ноутбук с Linux, на котором присутствовал джентльменский набор утилит для разработки на языке Си (gcc, vim, make, valgrind, gdb). Я уже не помню, какую цель мы тогда перед собой поставили, но через пару минут мой оппонент оказался за этим ноутбуком, полностью готовый решать задачу.

И буквально на первых же строках он допустил серьезную ошибку при аллоцировании памяти под… строку.

char *str = (char *)malloc(sizeof(char) * strlen(buffer));

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

Я думаю, определенно найдутся люди, которые спросят: «Разве что-то тут может быть не так?».
Поверьте, может.

А что именно — читайте по катом.